【AtCoder Grand Contest 016 D】XOR Replace | Mrsrz's blog

图论，位运算。

题目大意：

给定两个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$ 和 $b_1,b_2,b_3,\ldots,b_n$。

每次可以把 $a$ 中的一个元素变为 $a$ 中所有元素的 xor 和。

问至少要操作多少次，才能使 $a$ 和 $b$ 相等。

无解输出 $-1$。

题解：

令 $a_{n+1}$ 和 $b_{n+1}$ 分别表示 $a$ 和 $b$ 所有元素的 xor 和。那么一次操作相当于交换 $a_i$ 和 $a_{n+1}$。

如果 $a$ 和 $b$ 排序后不完全相等则无解。

我们令值代表点，对于 $i$，若 $a_i\neq b_i$，则我们令 $a_i$ 向 $b_i$ 连一条有向边。

我们假设 $a_{n+1}$ 在一个连通块里面，那么经过边数次移动可以使这个连通块对应好。从一个连通块到另一个连通块需要额外花费 $1$ 次，所以还需要连通块个数 $-1$ 次。

若 $a_{n+1}=b_{n+1}$，我们要单独给它计算成一个连通块。若其已经在连通块中则可以不用管。

Code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
using namespace std;
const int N=1e5+5;
int a[N],b[N],n,X,Y,cnt,tot,head[N],ans;
bool vis[N];
map<int,int>id;
vector<int>va,vb;
struct edge{
    int to,nxt;
}e[N];
inline int get(int x){return id.count(x)?id[x]:id[x]=++tot;}
void dfs(int u){
    vis[u]=1;for(int i=head[u];i;i=e[i].nxt)if(!vis[e[i].to])dfs(e[i].to);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i],X^=a[i],va.push_back(a[i]);
    for(int i=0;i<n;++i)cin>>b[i],Y^=b[i],vb.push_back(b[i]);
    va.push_back(X),vb.push_back(Y);
    sort(va.begin(),va.end()),sort(vb.begin(),vb.end());
    if(va!=vb){cout<<"-1\n";return 0;}
    for(int i=0;i<n;++i)
    if(a[i]!=b[i]){
        int A=get(a[i]),B=get(b[i]);
        e[++cnt]=(edge){B,head[A]},head[A]=cnt;
        ++ans;
    }
    if(!id.count(X))++ans;else
    if(X!=Y){
        int A=get(X),B=get(Y);
        e[++cnt]=(edge){B,head[A]},head[A]=cnt;
    }
    for(int i=1;i<=tot;++i)if(!vis[i])++ans,dfs(i);
    cout<<ans-1<<'\n';
    return 0;
}