[AGC016D] XOR Replace 题解

[AGC016D] XOR Replace

来自 @qzmoot 同一机房的同学的题解。

模拟赛用不同的思路场切了。

题面大意：一个序列，一次操作可以将某个位置变成整个序列的异或和。问最少几步到达目标序列。

来自梦熊的题面：

有一个长度为 $n$ 的序列 $a$ ，有以下函数:

void update(int u){
	int w=0;
	for(int i=1;i<=n;i++) w^=a[i];
	a[u]=w;
}

你可以执行这个函数若干次，其中参数 $u$ 由你指定，请问将序列 $a$ 修改为序列 $b$ 的最小调用次数是多少。

分析：

操作逻辑简化

我们先要知道这个操作在干什么。

如果你指定一个 $u$ ，使 $w = a_u$ 、 $a_u = \oplus_{i = 1}^n a_i$ ，

那么当你再指定一个 $u^{\prime}$ 时， $a_{u^{\prime}} = \oplus_{i = 1}^n a_i = w$ 。

这是由于异或具有自反性。

那么，这个操作就相当于你有一个初始为 $a$ 的序列，同时手里还纂着一个 $⊕i=1nai \oplus_{i = 1}^n a_i$ ，你每次可将手中的数和序列中的数交换，直到序列 $a$ 变成序列 $b$ 。

合法情况判断

接下来判断的是怎样才是合法的局面。

根据上面的分析，容易发现这个序列 $a$ 有两种情况：

序列 $a$ 和序列 $b$ 的数种类相同，且每种种类的数的个数相同。
序列 $a$ 和序列 $b$ 的数种类只有一种不同，该种类数的个数是 $1$ ，且该数为初始的 $⊕i=1nai \oplus_{i = 1}^n a_i$ 。

最小操作数

接下来是最小操作数的分析。

我们的操作肯定是取出一个数，直接放进与 $b$ 对应的位置。

因为只有合法局面（序列中的数一定是一一对应的）才会计算最小操作数，所以这样做一定是最优的。

并且 $a$ 和 $b$ 已经匹配上的位置可以不用考虑。

那么，你会发现我们的拿取操作形成了一个环或链。

因此，我们可以将 $a$ 和 $b$ 中的对应位置的数连边。

其必然形成若干简单环和链，如图：

对于链，其中必定有 $⊕i=1nai \oplus_{i = 1}^n a_i$ ，这时最小操作数为链的边数个数。

对于环，其中必定没有 $⊕i=1nai \oplus_{i = 1}^n a_i$ ，这时我们会先将 $⊕i=1nai \oplus_{i = 1}^n a_i$ 放到任意一个位置，最后将所有环中数字位置调整完后取出来，最小操作数为环的边数 + 1。

用并查集统计答案就可以过了。

最后由于 $a_i,b_i < 2^{30}$ ，所以用并查集计算答案之前需要离散化。

这种方法好像不需要判孤立点（大概吧，本人没有仔细研究）。

AC-code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}
void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
signed main() {
	int n = rd(),top = 0;
	vector<int> a(n),b(n),c(n * 2),s(n * 2),siz(n * 2),t(n * 2);
	vector<bool> bok(n * 2),ext(n * 2);
	vector<int> in(n * 2);
	for(int i = 0;i<n;i++) a[i] = rd();
	for(int i = 0;i<n;i++) b[i] = rd();
	for(int i = 0;i<n;i++) c[top++] = a[i],c[top++] = b[i];
	int w = 0;
	for(int i = 0;i<n;i++) w ^= a[i];
	c.emplace_back(w);	
	sort(c.begin(),c.end());
	top = unique(c.begin(),c.end()) - c.begin() - 1;
	for(int i = 0;i<n;i++) 
		a[i] = lower_bound(c.begin(),c.begin() + top + 1,a[i]) - c.begin(),
		b[i] = lower_bound(c.begin(),c.begin() + top + 1,b[i]) - c.begin();
	w = lower_bound(c.begin(),c.begin() + top + 1,w) - c.begin();
	for(int i = 0;i<n;i++) t[a[i]]++;
	t[w]++;
	for(int i = 0;i<n;i++) {
		t[b[i]]--;
		if(t[b[i]] < 0) {puts("-1");return 0;}
	}
	bool flag = false;
	for(int i = 0;i<n;i++) 
		if(a[i] != b[i]) {flag = true;break;}
	if(!flag) {wt(0);return 0;}
	for(int i = 0;i<n * 2;i++) {s[i] = i;ext[i] = 0;siz[i] = 0;bok[i] = 0;}
	for(int i = 0;i<n;i++) {
		if(a[i] == b[i]) continue;
		bok[a[i]] = bok[b[i]] = true;
		siz[b[i]]++;
		if(w == b[i]) ext[b[i]] = true; 
	}
	auto find = [&](auto self,int x) -> int {
		if(s[x] ^ x) 
			s[x] = self(self,s[x]);
		return s[x];
	};
	for(int i = 0;i<n;i++) {
		if(a[i] == b[i]) continue;
		int fa = find(find,a[i]),fb = find(find,b[i]);
		if(fa != fb) {
			s[fa] = fb;
			siz[fb] += siz[fa];
			ext[fb] = ext[fb] | ext[fa];
		}
	}
	int ans = 0;
	for(int i = 0;i<n * 2;i++) {
		if(bok[i] && find(find,i) == i) {
			if(ext[find(find,i)]) ans += siz[find(find,i)];
			else ans += siz[find(find,i)] + 1;
		}
	}
	wt(ans);
	return 0;
}