自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:27:40，当前版本为作者最后更新于2021-06-20 16:56:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先题目已经给出了结论，就是对于任意 $N,M$ 均有解。

所以如果 $A$ 中后 $x$ 个数和 $B$ 中前 $x$ 个数两两配对，就可以转化为 $N-x,M+x$ 的子问题。

所以对于 $A$ 中最后一个数 $n-1$ ，在 $B$ 中至少存在一个数 $x$ 使得 $x\ \&\ (n-1) = n-1$ 。我们只记录 $B$ 中最小的 $x$ 。

关键结论：$\forall k\in[0,x-m]\ ,\ (x-k)\ \&\ (n-1-k)=(n-1-k)$ 。

说人话，就是将 $A$ 后面这一段和 $B$ 前面这一段按顺序两两配对一定是合法解。

感性理解以下，因为在 $[m,x)$ 区间内的数和 $n-1$ 配对都不合法，而 $x$ 是第一个合法的，所以 $x$ 和 $n-1$ 最后几位相同，而这包括了区间 $[m,x]$ 。

理性分析以下，我们令 $n-1$ 中为 $1$ ，而 $m$ 中为 $0$ 的最高位为第 $i$ 位，那么枚举 $x$ 的过程就是将最低的 $i$ 位一直加到后 $i$ 位和 $n-1$ 完全相同。那么再减回去也一定完全相同。

#include<cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=n-1,j=m;~i;){
		int k=j;
		while((k&i)!=i)k++;
		rep(r,0,k-j)printf("%d %d\n",i--,k-r);
		j=k+1;
	}return 0;
}