题目大意
给你两个长度为n的序列a,b，要你进行尽量少的操作，把a序列换成b序列，并输出最少操作数，不行就-1。 操作：设x为a的异或和，你可以把a[i]替换成x，i=1~n. n≤1e5
解题思路
稍微分析一下，可以发现除了一开始的异或和是新的数，每次你操作之后，异或和会变成替换的那个数。 为了方便，我们把a和b的异或和都添加在各自的末尾。 那么就相当于置换了。每次换一轮，假设有k个数，要操作k+1次，而如果x恰好为a序列不满足条件的某个数，次数为k。 乱操作是不优的，我们考虑怎样搞尽量少的轮数。 假设a[x]需要变成b[x]，我们连边(a[x],b[x])，容易发现同一个联通块的点，我们总有办法弄成一个环，不然就-1了。 考虑到我们要把所有联通块都搞掉，那么我们在联通块之间转移还要花1的时间，所以答案还要加上联通块个数-1。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=
1e6+
5,M=
2e6+
5,mo=
1e9+
7;
map<int,int> Ref;
int n,i,x,a[N],b[N],c[N],d[N],pp,ans,y,fa[N],tt,act[N];
int get(
int x)
{
if (fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
int main()
{
freopen(
"t5.in",
"r",stdin);
scanf(
"%d",&n);
fo(i,
1,n)
{
scanf(
"%d",a+i);
x^=a[i];
}
a[n+
1]=x;x=
0;
fo(i,
1,n)
{
scanf(
"%d",b+i);
x^=b[i];
}
b[++n]=x;
fo(i,
1,n) c[i]=a[i],d[i]=b[i];
sort(c+
1,c+
1+n);
sort(d+
1,d+
1+n);
pp=
1;
fo(i,
1,n)
if (c[i]!=d[i])
break;
if (i<=n)
printf(
"-1\n");
else
{
c[
0]=-
1;
fo(i,
1,n)
{
if (c[i]!=c[i-
1]) tt++;
Ref[c[i]]=tt;
}
fo(i,
1,tt) fa[i]=i;
fo(i,
1,n)
if (a[i]!=b[i]||i==n)
{
ans+=(i<n);
act[Ref[a[i]]]=act[Ref[b[i]]]=
1;
fa[get(Ref[a[i]])]=get(Ref[b[i]]);
}
if (ans)
{
fo(i,
1,tt)
if (act[i]&&fa[i]==i)
ans++;
ans--;
}
printf(
"%d\n",ans);
}
}
