自动搬运

查看原文

来自洛谷，原作者为

	qwer6 “向我们曾迷惘的路致敬！”

搬运于2025-08-24 22:56:16，当前版本为作者最后更新于2025-07-01 13:59:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

1. Description

给定两个集合 $A,B$，称 $x$ 变化为 $y$ 为一次操作，要求 $x\in A$ 且 $y\notin A$ 且 $x$ 与 $y$ 在二进制下只有一位不同。

现在构造一种操作方案，使得所有操作合法且所有操作完成后 $A$ 集合和 $B$ 集合相等。

2. Solution

构造题，首先将 $A$ 集合和 $B$ 集合中相同的排除在考虑范围之外，然后我们随便选择 $A$ 中的一个数 $x$，让他变成一个 $B$ 中还没有在 $A$ 中出现的数。

然后修改的方式也十分简单，直接一位位的修改过来，如果出现重复的……

你先拿重复的那个继续往后变，然后变完之后在把原来的变成重复的那个即可。

例如第一个样例，我们将 $0$ 变成 $3$，第一步需要将 $0$ 变成 $1$，但是原来已经有 $1$ 了，我们从 $1$ 往后变，$1$ 变成 $3$，然后再将 $0$ 变成 $1$ 即可。

但是变化途中可能多次重复，我们拿个栈存一下，倒序储存即可。

整体过程有点像玩华容道，这么理解一下就可以了，具体的实现可以看代码。

3. Code

/*by qwer6*/
/*略去缺省源与快读快写*/
const int N=(1<<15)+5;
int n,m,tmpa,tmpb,top;
int a[N],b[N];
bool visa[N],visb[N];
pii ans[N<<2],st[N<<2];
signed main(){
	read(n);
	for(int i=1;i<=n;i++)read(a[i]),visa[a[i]]=1;
	for(int i=1;i<=n;i++)read(b[i]),visb[b[i]]=1;
	for(int i=1;i<=n;i++){
		if(visb[a[i]])continue;
		a[++tmpa]=a[i];
	}
	for(int i=1;i<=n;i++){
		if(visa[b[i]])continue;
		b[++tmpb]=b[i];
	}
	n=tmpa;
	for(int i=1;i<=n;i++){
		for(int j=0,now=a[i],d=a[i]^b[i];j<15;j++){
			if(d&1<<j){
				if(visa[now^1<<j])st[++top]={now,now^1<<j};
				else ans[++m]={now,now^1<<j};
				now=now^1<<j;
			}
		}
		visa[a[i]]=0,visa[b[i]]=1;
		while(top)
			ans[++m]=st[top--];
	}
	write(m),Nxt;
	for(int i=1;i<=m;i++)write(ans[i].first),Spa,write(ans[i].second),Nxt;
}