[AtCoder Grand Contest 016] D: Xor Replace (agc016d)

118 阅读 0 评论 78 点赞

我是靠谱客的博主孝顺哈密瓜，这篇文章主要介绍[AtCoder Grand Contest 016] D: Xor Replace (agc016d)，现在分享给大家，希望可以做个参考。

原题链接
https://agc016.contest.atcoder.jp/tasks/agc016_d

Description

给出一个n个数的序列a，每次操作可以将一个数变成整个序列的值的异或
求最少需要多少次才能将a变成目标序列b
无法完成输出-1

n<=100000

Solution

考虑操作的本质

只要按位稍微分析一下，就可以发现，题目相当于一开始手里抓着整个序列a的异或，一次操作可以将手上的数与序列中的某个数换过来

知道操作的本质就简单许多
如果能够完成，方便起见将a的异或和b的异或分别加到序列末，排序后两个序列显然完全相同

这样就把-1判掉了

只有a[i]!=b[i]的位置我们是需要调整的
那么将a,b离散化，a[i]与b[i]连边

将一个联通块内操作所需要的次数就是联通块大小

而联通块之间跳需要1的代价
此时由于我们一开始手上抓着的是a的异或和
如果它刚好在某一个联通块里面就不用考虑了，否则就必须将它自己看做一个大小为0的联通块

最后-1是在联通块之间跳的次数是联通块个数-1
联通块可以用并查集维护，离散化我实在懒惰了用了map

Code

复制代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int a[N],b[N],n,m,d[N],c[N],n1,f[N];
map <int,int> h;
bool bz[N];
int getf(int k)
{
    if(f[k]==0||f[k]==k) return k;
    return (f[k]=getf(f[k])); 
}
int main()
{
    cin>>n;
    int v=0;
    fo(i,1,n) scanf("%d",&a[i]),v^=a[i],c[i]=a[i];
    a[n+1]=c[n+1]=v;
    bool pd=0;
    v=0;
    fo(i,1,n) scanf("%d",&b[i]),d[i]=b[i],v^=b[i];
    b[++n]=d[n]=v;
    sort(c+1,c+n+1),sort(d+1,d+n+1);
    n1=0;
    fo(i,1,n) 
    {
        if(c[i]!=d[i]) 
        {
            printf("-1n");
            return 0;
        }
        if(h.count(c[i])==0) h[c[i]]=++n1;
        if(h.count(d[i])==0) h[d[i]]=++n1; 
    }
    int ans=0;
    fo(i,1,n) 
    {
        a[i]=h[a[i]],b[i]=h[b[i]];
        if(a[i]!=b[i]) 
        {
            if(i<n) ans++;
            int fx=getf(a[i]),fy=getf(b[i]);
            f[fx]=fy;
            bz[fx]=1,bz[fy]=1;
        }
    }
    if(ans==0) printf("0n");
    else
    {
        bz[a[n]]=bz[b[n]]=1;
        fo(i,1,n1) if(bz[i]&&getf(i)==i) ans++;
        printf("%dn",ans-1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int a[N],b[N],n,m,d[N],c[N],n1,f[N];
map <int,int> h;
bool bz[N];
int getf(int k)
{
    if(f[k]==0||f[k]==k) return k;
    return (f[k]=getf(f[k])); 
}
int main()
{
    cin>>n;
    int v=0;
    fo(i,1,n) scanf("%d",&a[i]),v^=a[i],c[i]=a[i];
    a[n+1]=c[n+1]=v;
    bool pd=0;
    v=0;
    fo(i,1,n) scanf("%d",&b[i]),d[i]=b[i],v^=b[i];
    b[++n]=d[n]=v;
    sort(c+1,c+n+1),sort(d+1,d+n+1);
    n1=0;
    fo(i,1,n) 
    {
        if(c[i]!=d[i]) 
        {
            printf("-1n");
            return 0;
        }
        if(h.count(c[i])==0) h[c[i]]=++n1;
        if(h.count(d[i])==0) h[d[i]]=++n1; 
    }
    int ans=0;
    fo(i,1,n) 
    {
        a[i]=h[a[i]],b[i]=h[b[i]];
        if(a[i]!=b[i]) 
        {
            if(i<n) ans++;
            int fx=getf(a[i]),fy=getf(b[i]);
            f[fx]=fy;
            bz[fx]=1,bz[fy]=1;
        }
    }
    if(ans==0) printf("0n");
    else
    {
        bz[a[n]]=bz[b[n]]=1;
        fo(i,1,n1) if(bz[i]&&getf(i)==i) ans++;
        printf("%dn",ans-1);
    }
}