题解：AT_agc016_d [AGC016D] XOR Replace

· · 题解

本文作者 @tanglb，是校内模拟赛 T2 题解，经过作者同意后代为交到原题 AT_agc016_d 题解区。有修改。

先模拟一下这个操作：

设 k=\bigoplus_{i=1}^n a_i，当对 a_i 操作时，k'\gets k \oplus (\bigoplus_{j=1(j \neq i)}^n a_j)=a_i。

由此发现，每次对 a_i 进行操作，等价于交换 a_i 和 k。而交换不会有新的数产生，操作后 a 中的数只能是 \{a_i\} 和 k 这 n+1 个数中的 n 个，且每种排列顺序都能取到。那么无解的情况就很好分辨了，直接判断 b 数组是否包含于这 n+1 个数组成的可重集中即可。

现在我们保证有解，如何确定最小步数？

贪心的想，每一次交换都应尽量匹配一组 (a_i,b_i)。当 k=b_i 时交换 a_i 和 k，a_i=b_j 时再交换 a_i 和 a_j，如此往复，我们就能匹配若干对 (a_i,b_i) 并且每一步都不浪费。

上面不断交换的过程中，a_i 决定了下一次交换的位置，不妨让每个 a_i 向 b_i 建边，将交换过程转化为图上的 dfs，交换次数就为走过的边数，所有 a_i=b_i 仅当图上每一条边都走过。

建出的图可能不连通，当我们要从一个连通块跳到另一个连通块时，可以通过加一条边来实现。例如从 a_i 到 a_j 没有边，交换 a_i 与 a_j 等价于建 a_j 到 a_i 的边，并跳到 a_j 的位置。每跳一次边数就加一。

根据上文结论，最小操作次数等价于边数，设连通块数为 d，则答案为 n + d - 1。维护连通块可以建边后 dfs 或者使用并查集，注意特判图上的自环，这些自环不用走，不需要算入操作次数。

这里放一个并查集做法的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int b[200005];
int ans;
map<int,int>mp;
map<int,int>fa;
int find(int x){
    if(fa[x]==0)return fa[x]=x;
    return(x==fa[x]?x:fa[x]=find(fa[x]));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    int n;
    cin>>n;
    int flc=0;
    for(int i=1;i<=n;i++)
    cin>>a[i],mp[a[i]]++,a[n+1]^=a[i];
    for(int i=1;i<=n;i++)
    cin>>b[i],mp[b[i]]--;
    mp[a[n+1]]++;
    int sum=0;
    for(auto i:mp)
    if(i.second)sum++;
    if(sum!=1){
        puts("-1");
        return 0;
    }
    for(int i=1;i<=n;i++)
    if(a[i]==b[i])flc--;
    for(int i=1;i<=n+1;i++)a[i]++;
    for(int i=1;i<=n;i++)b[i]++;
    for(int i=1;i<=n;i++)
    fa[find(a[i])]=find(b[i]);
    sum=0;
    mp.clear();
    for(int i=1;i<=n;i++){
        if(a[i]==b[i])continue;
        if(find(b[i])==b[i]&&!mp[b[i]])sum++,mp[b[i]]=1;
    }
    for(int i=1;i<=n;i++)
    if(b[i]==a[n+1]&&a[i]!=b[i]){
        sum--;
        break;
    }
    cout<<n+sum+flc;
    return 0;
}
// 关注 fish_love_cat (uid=754021) 谢谢喵