【agc016D】XOR Replace

Portal --> agc016D

Description

​　　一个序列，一次操作将某个位置变成整个序列的异或和，现在给定一个目标序列，问最少几步可以得到目标序列

​　　

Solution

​　　翀哥神仙！（守恒什么的哈哈哈哈哈哈哈==）

​​　　首先当然是要快乐手玩样例啊然后就发现这个异或是假的，比如说手头上有四个元素({a,b,c,d})，比如说我们现在用异或和替掉(b)（用(oplus)表示异或），那就是({a,aoplus boplus coplus d,c,d})，然后这个时候我们再用异或和替换掉(a)，那么我们就得到了({b,aoplus boplus coplus d,c,d})，类似地，我们下一步对哪个位置操作，那个位置就会变成(a)，（具体为什么的话就是因为。。异或同一个数两次影响会抵消）所以实际上我们这个异或操作就是一个换位操作

​　　然后我们来判一下无解的情况：注意到因为这个操作其实是一个换位操作，所以目标序列中的组成元素如果与原序列中的组成元素，要么都相同，要么只能差一个，并且这差的一个必须是原序列中所有数的异或和（因为你不可能搞出其他新的元素了）

​​　　在实现上我们可以将两个序列的异或和（目标序列的异或和必定是缺的那个数具体为什么的话。。手玩一下就比较清晰了）也当做一个元素丢进序列末尾，对两个序列分别排序之后，如果说有一个位置元素不相同那就凉凉

​　　

​　　接下来看有解的情况，如何保证操作次数最小

​　　首先对于那些两个序列中值相等的位置，不操作是最优的，那么接下来只考虑那些不相等的位置

​​　　重新看一下上面手玩的那个过程，我们可以直观一点把它想象成：你从序列里面拿出来一个数，然后用异或和填上它的空缺，然后你开始拿这个数去换别的数，交换的具体过程就是你把另一个数从它的位置上面拿出来，然后把手头上这个数放到那个位置上，再拿这个新换来的数去继续交换，直到换到目标序列

​　　因为要让交换的次数最小，我们希望每次交换都能满足一个位置的目标要求，再具体一点就是每一步我们都希望将手头上拿的着的数放到它的目标位置，那么考虑这样一种建图方式：将相同的值（包括两个序列的异或和）看成一个点，对于每个位置(x)（我们只考虑那些值不相等的位置），原序列中的值向目标序列中的值连一条边（对于原序列的异或和的话，我们也是正常连就好了），我们的交换要从原序列的异或和开始，沿着边走，把所有的边都走一遍（一条边代表一次操作）

​​　　那所以我们现在得到了一个有若干个连通块的图，而每一个连通块其实应该是一个环，因为考虑每个点的入度和出度，如果说一个值在原序列中出现过，那么必定有(1)的出度，而如果一个值在目标序列中出现过，必定有(1)的入度，由于原序列和目标序列的组成元素相同，所以每个元素都有(1)的入度和(1)的出度，所以必定每个连通块都是一个环

​​　　那么现在记不相等的位置数量为(m)，我们手头上的图总共有(m+1)条边（还有一条异或和连出来的边），我们要从原序列异或和对应的点开始把每条边走一遍，遍历一条边需要(1)的代价，从一个环跳到另一个环的话也是需要(1)的代价（要先拿一个出来才能开始新的交换），那么总的代价就是(m+)环数(-1)，并且，如果说异或和所处的是一个大小为(1)的连通块，那么一开始还需要跳出来，所以这种情况下答案还要再(+1)

​　　

​​　　代码大概长这个样子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],a1[N],b1[N],f[N],sz[N];
int n,m,xsuma,xsumb,Cnt,ans;
void prework(){
    a1[0]=unique(a1+1,a1+1+n)-a1-1;
    for (int i=1;i<=n;++i){
        a[i]=lower_bound(a1+1,a1+1+a1[0],a[i])-a1;
        b[i]=lower_bound(a1+1,a1+1+a1[0],b[i])-a1;
    }
    for (int i=1;i<=a1[0];++i) f[i]=i,sz[i]=1;
}
int get_f(int x){return f[x]=f[x]==x?x:get_f(f[x]);}
void link(int x,int y){
    get_f(x); get_f(y);
    if (f[x]==f[y]) return;
    sz[f[y]]+=sz[f[x]];
    f[f[x]]=f[y];
}
void solve(){
    for (int i=1;i<=n;++i){
        if (a[i]==b[i]&&i!=n) continue;
        ans+=(i<n);
        link(a[i],b[i]);
    }
    if (f[a[n]]==a[n]&&sz[a[n]]==1) ++ans;
    for (int i=1;i<=a1[0];++i)
        if (f[i]==i&&sz[i]>1)
            ++ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
#endif
    int tmp;
    bool flag=true;
    scanf("%d",&n);
    xsuma=0; xsumb=0;
    for (int i=1;i<=n;++i) scanf("%d",a+i),a1[i]=a[i],xsuma^=a[i];
    for (int i=1;i<=n;++i) scanf("%d",b+i),b1[i]=b[i],xsumb^=b[i];
    a[++n]=a1[n]=xsuma;
    b[n]=b1[n]=xsumb;
    sort(a1+1,a1+1+n);
    sort(b1+1,b1+1+n);
    for (int i=1;i<=n;++i)
        if (a1[i]!=b1[i]){printf("-1n"); return 0;}
    Cnt=0;
    for (int i=1;i<=n;++i)
        if (a[i]!=b[i]) ++Cnt;
    if (Cnt==0){
        printf("0n"); return 0;
    }
    prework();
    solve();
    printf("%dn",ans-1);
}