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

· · 题解

先不考虑集合的这个什么“不可重”性质，直接去做，就是让每个 a 和每个 b 一一对应上，然后按照某种顺序（比如每次修改有差别的位置的 \text{lowbit}）递推直至 a' = b。

但是现在有重合了，怎么办呢？很简单：譬如集合 A 中的元素 sx 要变到 B 中的 ex，在变化的过程中撞上 A 中另一元素 sy，这个时候 sx 过不去了，我们便考虑让 sy 代替 sx 变 ex，暂存 sx，等 sy 走完后面一程之后再回过头来让 sx 变到 sy。这样就完美解决了重合的问题。

于是思路就很清晰了：考虑每次取出一组需要匹配的 a 和 b（a \not= b），然后不断沿两数二进制位差别的 \text{lowbit} 变化，没重合就正常走，重合了则开一个栈 stack 暂存这一步，然后让重合的那位帮着继续走——当然这里并不需要真的去交换什么。a' = b 了，我们需要做的只剩把暂存的清了。由于开的是栈，越后进的反而越先处理，要是先处理前面的怕中途又撞上。

代码里还加了些许注释辅助理解。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
int n;
set<int> A,B,P;
vector<pii> Ans;
stack<pii> st;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void calc(int x,int y){
    if(A.count(y))st.push({x,y});//暂存
    else A.erase(x),A.insert(y),Ans.pb({x,y});//改变值并存储步骤
    return;
}
void Sol(int x,int y){
    while(x!=y){
        int di=x^y;di&=(-di);//找到需要变化的位置
        calc(x,x^di);x^=di;//处理可能的重合情况并变化
    }while(!st.empty())
        calc(st.top().fr,st.top().se),st.pop();
    //把前面暂存的解决掉
    return;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        A.insert(x),P.insert(x);
        //A 就表示当前的 A 集合
        //P 里面的元素都是 A 里面还没配对上的
    }for(int i=1;i<=n;i++){
        int x=read();
        B.insert(x);
        //B 里的元素是 B 里还没配对上的
    }while(!B.empty()){
        int num=(*B.begin());
        if(A.count(num))
            {P.erase(num),B.erase(num);continue;}
        //有相同的不需要变化
        int pip=(*P.begin());Sol(pip,num);
        P.erase(pip),B.erase(num);
        //否则变化并删掉集合中的值
    }cout<<Ans.size()<<"\n";
    for(auto [x,y]:Ans)cout<<x<<" "<<y<<"\n";
    //输出答案
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！