agc016d

题目大意

现在一共有n个数，每一次你可以把其中一个数换成整个序列的抑或和，有一个目标序列，问最少多少步可以转化成目标序列，若无解输出-1

题解

这一题的操作本质上就是一开始序列中有n个数，然后你手上有这n个数的抑或和，每一次你可以把手上的数和序列中的一个数交换

那么我们实际上就是要求有多少个置换，答案就是置换个数加上每一个置换的大小，如果某一个置换的其中一个目标值为一开始的抑或和，那么答案还会减一，因为我们最后就不用再换这个了

为了方便我们把两个序列的抑或和放在第n+1位

对于每一个值我们都建立一个节点，然后对于a[i]，b[i]不同的位置，我们在它们之间连一条边，然后我们求联通块就可以了

最后答案还要减一，因为如果n+1对应的节点在某一个大联通块中，那么一定可以最后少换一次，如果自成一个联通块，那么就相当于把多加的一个联通块减回来

贴代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#define fo(i,a,b) for(i=a;i<=b;i++)

using namespace std;

const int maxn=1e5+5;

int a[maxn],b[maxn],c[maxn],d[maxn],fa[maxn];
int i,j,k,l,m,n,x,y,ans,p;
map<int,int> f;

int getfather(int x){
    if (fa[x]==x) return x; else fa[x]=getfather(fa[x]);
    return fa[x];
}
int main(){
//  freopen("016d.in","r",stdin);
    scanf("%d",&n);
    l=0;
    fo(i,1,n){
        scanf("%d",&a[i]);
        l^=a[i];
    }
    a[n+1]=l; l=0;
    fo(i,1,n){
        scanf("%d",&b[i]);
        l^=b[i];
    }
    b[++n]=l;
    fo(i,1,n){
        c[i]=a[i]; d[i]=b[i];
    }
    sort(c+1,c+n+1); sort(d+1,d+n+1);
    fo(i,1,n-1) if (c[i]!=d[i]) break;
    if (i<n){
        printf("-1n");
        return 0;
    }
    fo(i,1,n){
        if (a[i]!=b[i] && i!=n) ans++;
        if (i==n && ans==0){
            printf("0n"); return 0;
        }
        if (a[i]!=b[i] || i==n){
            if (!f[a[i]]) f[a[i]]=++p;
            if (!f[b[i]]) f[b[i]]=++p;
        }
    }
    fo(i,1,p) fa[i]=i;
    fo(i,1,n) if (a[i]!=b[i]) fa[getfather(f[a[i]])]=getfather(f[b[i]]);
    fo(i,1,p) if (getfather(i)==i) ans++;
    printf("%dn",ans-1);
    return 0;
}

最后

以上就是霸气指甲油为你收集整理的agc016d的全部内容，希望文章能够帮你解决agc016d所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。