Atcoder Grand Contest 016 D XOR Replace

80 阅读 0 评论 53 点赞

我是靠谱客的博主苗条电话，最近开发中收集的这篇文章主要介绍Atcoder Grand Contest 016 D XOR Replace，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

XOR Replace

Problem Statement

分别给出两个长度为 $n$ 的数组 $a$ , $b$ ，你可以进行若干次操作，每次操作你可以把序列中的某个数变成整个序列的异或和，问用最少的操作数把 $a$ 变成 $b$ 序列，若不能则输出- $1$ 。
$2$ ≤ $n$ ≤ $10^5$
$0$ ≤ $a_i$ , $b_i$ < $2^{30}$

Solution

不难发现操作的实质是把某个数变成整个序列的异或和，接着这个序列的异或和就变成了被换掉的那个数。
我们把整个序列的异或和放在第 $n$ + $1$ 个位置，所以问题就转换成了每次把第 $1$ ~ $n$ 中的某个数与第 $n$ + $1$ 个数交换，问最小的步数换成 $b$ 。

我们考虑如果某个位置上的 $a$ 最后要变成 $b$ $(a!=b)$ ，那么我们连边 $(a,b)$ ，不难发现，对于一个连通块我们可以弄成一个环的形式，那么交换的最小次数为连通块大小+ $1$ ，若其中包含了第 $n$ + 1 <script type="math/tex" id="MathJax-Element-2018">1</script>个位置，则最小的交换次数为连通块的大小。

Code

#include<bits/stdc++.h>
#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll N=11e4;
map<int,int> cha;

int n,m,j,k,l,i,o;
int fa[N],a[N],b[N],aa[N],bb[N],done[N];

inline int gf(int o)
{return fa[o]==o?o:fa[o]=gf(fa[o]);}

int main()
{
    cin>>n;
    fo(i,1,n)scanf("%d",&a[i]),a[n+1]^=a[i],aa[i]=a[i];
    fo(i,1,n)scanf("%d",&b[i]),b[n+1]^=b[i],bb[i]=b[i];
    ++n; aa[n]=a[n]; bb[n]=b[n];
    sort(aa+1,aa+n+1); sort(bb+1,bb+n+1);
    fo(i,1,n)if(aa[i]!=bb[i]){
        puts("-1"); return 0;
    }
    int t=0; aa[0]=bb[0]=-1;
    fo(i,1,n)t+=(aa[i]!=aa[i-1]),cha[aa[i]]=t;
    fo(i,1,t)fa[i]=i;
    int ans=-1;
    fo(i,1,n)if(i==n||a[i]!=b[i]){
        ans+=(i<n);
        int x=cha[a[i]],y=cha[b[i]];
        fa[gf(x)]=gf(y);
        done[x]=done[y]=1;
    }
    fo(i,1,n)if(gf(i)==i&&done[i])++ans;
    cout<<(ans<0?0:ans);
}