题解：AT_agc016_d [AGC016D] XOR Replace

本文作者 @tanglb，是校内模拟赛 T2 题解，经过作者同意后代为交到原题 AT_agc016_d 题解区。有修改。

先模拟一下这个操作：

设

k=\bigoplus_{i=1}^n a_i

，当对

a_i

操作时，

k'\gets k \oplus (\bigoplus_{j=1(j \neq i)}^n a_j)=a_i

。

由此发现，每次对

a_i

进行操作，等价于交换

a_i

和

k

。而交换不会有新的数产生，操作后

a

中的数只能是

\{a_i\}

和

k

这

n+1

个数中的

n

个，且每种排列顺序都能取到。那么无解的情况就很好分辨了，直接判断

b

数组是否包含于这

n+1

个数组成的可重集中即可。

现在我们保证有解，如何确定最小步数？

贪心的想，每一次交换都应尽量匹配一组

(a_i,b_i)

。当

k=b_i

时交换

a_i

和

k

，

a_i=b_j

时再交换

a_i

和

a_j

，如此往复，我们就能匹配若干对

(a_i,b_i)

并且每一步都不浪费。

上面不断交换的过程中，

a_i

决定了下一次交换的位置，不妨让每个

a_i

向

b_i

建边，将交换过程转化为图上的 dfs，交换次数就为走过的边数，所有

a_i=b_i

仅当图上每一条边都走过。

建出的图可能不连通，当我们要从一个连通块跳到另一个连通块时，可以通过加一条边来实现。例如从

a_i

到

a_j

没有边，交换

a_i

与

a_j

等价于建

a_j

到

a_i

的边，并跳到

a_j

的位置。每跳一次边数就加一。

根据上文结论，最小操作次数等价于边数，设连通块数为

d

，则答案为

n + d - 1

。维护连通块可以建边后 dfs 或者使用并查集，注意特判图上的自环，这些自环不用走，不需要算入操作次数。

这里放一个并查集做法的代码。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int b[200005];
int ans;
map<int,int>mp;
map<int,int>fa;
int find(int x){
	if(fa[x]==0)return fa[x]=x;
	return(x==fa[x]?x:fa[x]=find(fa[x]));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(),cout.tie();
	int n;
	cin>>n;
	int flc=0;
	for(int i=1;i<=n;i++)
	cin>>a[i],mp[a[i]]++,a[n+1]^=a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i],mp[b[i]]--;
	mp[a[n+1]]++;
	int sum=0;
	for(auto i:mp)
	if(i.second)sum++;
	if(sum!=1){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
	if(a[i]==b[i])flc--;
	for(int i=1;i<=n+1;i++)a[i]++;
	for(int i=1;i<=n;i++)b[i]++;
	for(int i=1;i<=n;i++)
	fa[find(a[i])]=find(b[i]);
	sum=0;
	mp.clear();
	for(int i=1;i<=n;i++){
		if(a[i]==b[i])continue;
		if(find(b[i])==b[i]&&!mp[b[i]])sum++,mp[b[i]]=1;
	}
    for(int i=1;i<=n;i++)
	if(b[i]==a[n+1]&&a[i]!=b[i]){
        sum--;
        break;
    }
	cout<<n+sum+flc;
	return 0;
}
// 关注 fish_love_cat (uid=754021) 谢谢喵

题解：AT_agc016_d [AGC016D] XOR Replace

文章操作

相关推荐

评论

题解：AT_agc016_d [AGC016D] XOR Replace