P10258 题解

qwer6 · 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;
}