[agc016d]xor replace题意：题解：代码：

80 阅读 0 评论 53 点赞

我是靠谱客的博主魁梧紫菜，这篇文章主要介绍[agc016d]xor replace题意：题解：代码：，现在分享给大家，希望可以做个参考。

题意：

题解：

棒棒的神仙题。。。这题只是D题？？？（myh：看题五分钟，讨论两小时）

首先这个异或和是假的，比如我现在有$a=(a_1,a_2,a_3,a_4)$，操作一下$a_2$，就变成了$a=(a_1,a_1oplus a_2oplus a_3oplus a_4,a_3,a_4)$；

再操作一下$a_3$，因为$a_ioplus a_i=0$，它就变回了$a=(a_1,a_1oplus a_2oplus a_3oplus a_4,a_2,a_4)$。

所以这个操作只是第一次把一个位置变成全体的异或和，后面就是在交换两个数的位置。。。

可以考虑把多出来的这个全体异或和放到$N+1$的位置，然后就变成了一次操作是交换$1$到$N$中的一个位置的数和第$N+1$个位置的数，求要多少次操作把数组a变成数组b。

无解的情况显然：如果两个数组排序后有位置不同则必定无解，先判掉；

把数组离散化，然后对于位置$i$，若$a_ineq b_i$则从$a_i$到$b_i$连一条边；

这样子对于每个联通块，设其大小为$S$，则必定可以用$S-1$次操作使其中的位置全部满足条件（感性理解一下？）；

在每个联通块之间，需要额外的一次操作使$N+1$的位置在两个块之间转换；

最后要特殊考虑$N+1$这个位置，如果它已经在某个联通块内则没有影响，否则要单独作为一个联通块考虑，答案++；

所以最后的答案就是边数+联通块数-1，用并查集xjb维护一下即可。

代码：

复制代码

1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 #define inf 2147483647
 9 #define eps 1e-9
10 using namespace std;
11 typedef long long ll;
12 int n,ans=0,ta=0,tb=0,cnt=0,fa[100001],a[100001],b[100001],aa[100001],bb[100001],lsh[200001];
13 map<int,bool>mp;
14 int ff(int u){
15     return fa[u]==u?u:fa[u]=ff(fa[u]);
16 }
17 int main(){
18     scanf("%d",&n);
19     for(int i=1;i<=n;i++){
20         scanf("%d",&a[i]);
21         ta^=a[i];
22         aa[i]=a[i];
23     }
24     for(int i=1;i<=n;i++){
25         scanf("%d",&b[i]);
26         tb^=b[i];
27         bb[i]=b[i];
28     }
29     n++;
30     a[n]=aa[n]=ta,b[n]=bb[n]=tb;
31     sort(aa+1,aa+n+1);
32     sort(bb+1,bb+n+1);
33     for(int i=1;i<n;i++){
34         if(aa[i]!=bb[i])return puts("-1"),0;
35     }
36     for(int i=1;i<n;i++){
37         if(a[i]!=b[i]){
38             lsh[++cnt]=a[i];
39             lsh[++cnt]=b[i];
40             ans++;
41         }
42     }
43     lsh[++cnt]=ta;
44     lsh[++cnt]=tb;
45     if(!ans)return puts("0"),0;
46     sort(lsh+1,lsh+cnt+1);
47     cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
48     for(int i=1;i<=cnt;i++)fa[i]=i;
49     for(int i=1;i<=n;i++){
50         if(a[i]!=b[i]){
51             a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
52             b[i]=lower_bound(lsh+1,lsh+cnt+1,b[i])-lsh;
53             if(!mp[a[i]])mp[a[i]]=true;
54             if(!mp[b[i]])mp[b[i]]=true;
55             int f1=ff(a[i]),f2=ff(b[i]);
56             fa[f1]=f2;
57         }
58     }
59     for(int i=1;i<=cnt;i++){
60         if(fa[i]==i)ans++;
61     }
62     printf("%d",ans-1);
63     return 0;
64 }

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
62
63
64
 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 #define inf 2147483647
 9 #define eps 1e-9
10 using namespace std;
11 typedef long long ll;
12 int n,ans=0,ta=0,tb=0,cnt=0,fa[100001],a[100001],b[100001],aa[100001],bb[100001],lsh[200001];
13 map<int,bool>mp;
14 int ff(int u){
15     return fa[u]==u?u:fa[u]=ff(fa[u]);
16 }
17 int main(){
18     scanf("%d",&n);
19     for(int i=1;i<=n;i++){
20         scanf("%d",&a[i]);
21         ta^=a[i];
22         aa[i]=a[i];
23     }
24     for(int i=1;i<=n;i++){
25         scanf("%d",&b[i]);
26         tb^=b[i];
27         bb[i]=b[i];
28     }
29     n++;
30     a[n]=aa[n]=ta,b[n]=bb[n]=tb;
31     sort(aa+1,aa+n+1);
32     sort(bb+1,bb+n+1);
33     for(int i=1;i<n;i++){
34         if(aa[i]!=bb[i])return puts("-1"),0;
35     }
36     for(int i=1;i<n;i++){
37         if(a[i]!=b[i]){
38             lsh[++cnt]=a[i];
39             lsh[++cnt]=b[i];
40             ans++;
41         }
42     }
43     lsh[++cnt]=ta;
44     lsh[++cnt]=tb;
45     if(!ans)return puts("0"),0;
46     sort(lsh+1,lsh+cnt+1);
47     cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
48     for(int i=1;i<=cnt;i++)fa[i]=i;
49     for(int i=1;i<=n;i++){
50         if(a[i]!=b[i]){
51             a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
52             b[i]=lower_bound(lsh+1,lsh+cnt+1,b[i])-lsh;
53             if(!mp[a[i]])mp[a[i]]=true;
54             if(!mp[b[i]])mp[b[i]]=true;
55             int f1=ff(a[i]),f2=ff(b[i]);
56             fa[f1]=f2;
57         }
58     }
59     for(int i=1;i<=cnt;i++){
60         if(fa[i]==i)ans++;
61     }
62     printf("%d",ans-1);
63     return 0;
64 }