题解：P10258 [COCI 2023/2024 #5] Bitovi

DeaphetS · 2025-06-18 19:59:57 · 题解

小清新构造题。

首先如果不考虑每次修改操作中 y\notin A 的限制，那么是容易的。这时我们只需要解决 N 个形如将 a_i 通过若干次操作修改为 b_i 的子问题，可以有如下代码。

void gao(int x,int y){
    Ans.push_back(make_pair(x,y));
}
void cg(int x,int y){//将 x 变成 y
    while(x!=y){
        int dif=x^y;//得出在二进制上有哪些位不同
        dif=dif&(-dif);//取出其中一位
        gao(x,x^dif);//记录下将 x 变成 (x xor dif) 的操作
        x^=dif;//进行修改
    }
}

现在我们要考虑如何保证 y\notin A。一个 naive 的想法是当我们发现 y 已经在集合 A 中时，直接不进行这次操作，这样后续的修改还能继续进行。但这么做可能会使一些已经变成 B 中元素的数字被改掉，导致之前的修改操作被破坏。

于是我们可以记录这些产生破坏的操作，在一轮修改结束之后逐步还原他们即可，这里举个例子：

• 进行模拟操作，首先 0\to 1 时发现 1\in A，那么先不进行这个操作，把他暂存下来。既然 A 中有 1 那么我们可以接着进行后面的 1\to 3\to 7\to 15\to 31 的操作；
• 尝试执行 1\to 3，发现 3\in A，继续暂存；
• 尝试执行 3\to 7，此时 7\notin A，将这个操作计入答案；
• 尝试执行 7\to 15，发现 15\in A，暂存；
• 尝试执行 15\to 31，此时 31\notin A，将这个操作计入答案。这时 A=\{0,1,7,31\}；
• 逐步倒着还原之前被暂缓的操作，依次执行 7\to 15、1\to 3、0\to 1，A 变为 \{1,3,15,31\}，完成修改。

最终代码如下：

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,x;
set<int>A,B,C;
vector<pair<int,int>>d;
stack<pair<int,int>>s; 
void gao(int x,int y){
    if(A.count(y)){//暂缓操作
        s.push(make_pair(x,y));
        return;
    }
    A.erase(x),A.insert(y);
    d.push_back(make_pair(x,y));
}
void cg(int x,int y){
    while(x!=y){
        int dif=x^y;
        dif=dif&(-dif);
        gao(x,x^dif);
        x^=dif;
    }
    while(!s.empty()){//逐步还原
        auto pi=s.top();
        s.pop();
        gao(pi.first,pi.second);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x,A.insert(x),C.insert(x);
//A 用来记录当前的集合 A，C 则记录 A 中还没完成配对的所有元素
    for(int i=1;i<=n;i++)cin>>x,B.insert(x);
    while(!B.empty()){
        auto y=*B.begin();
        if(A.count(y)){
            C.erase(y);
            B.erase(y);
            continue;
        }
        auto x=*C.begin();
        cg(x,y);
        B.erase(y);
        C.erase(x);
    }
    cout<<d.size()<<endl;
    for(auto pi:d)cout<<pi.first<<" "<<pi.second<<endl;
}