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

小清新构造题。

首先如果不考虑每次修改操作中

y\notin A

的限制，那么是容易的。这时我们只需要解决

N

个形如将

a_i

通过若干次操作修改为

b_i

的子问题，可以有如下代码。

CPP

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

中元素的数字被改掉，导致之前的修改操作被破坏。

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

A=\{0,1,3,15\},B=\{1,3,15,31\}

，现在考虑将

0

变为

31

。

如果按照之前的做法，修改过程会是 $0\to 1\to 3\to 7\to 15\to 31$
进行模拟操作，首先 $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\}$ ，完成修改。

最终代码如下：

CPP

#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;
}

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

文章操作

相关推荐

评论

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