题意：
一个序列 \(a\)，一次操作可以将某个位置变成整个序列的异或和。 求最少几步到达目标序列 \(b\)。
\(n \le 10^5\)
思路：
见到这种题，第一步要去尝试把操作转化。
稍微推一下可以发现，如果 \(\oplus_{i=1}^n a_i = s\)，则相当于一个 \(n + 1\) 长序列，\(a_{n+1}=s\)，每次可以交换 \(a_i\) 与 \(a_{n+1}\)，求最少几次交换使得 \(a_1 \sim a_n\) 等于 \(b_1 \sim b_n\)。
无解说明又不包含的元素，这个可以直接判断。
考虑最终的答案，肯定是从 \(b_i \to x_1 \to x_2 \to \dots x_k \to a_i\) 的一条路径，所以我们不妨尝试将 \(b_i \to a_i\) 视作一条边。
所以我们要找的便是这张图中的一条从 \(s\) 出发的一条最短欧拉路径，如果这张图联通，因为我们现在是已经有解了，所以最短长度等于边数。
如果图不连通，则说明我们需要额外新增一下边使得图联通且存在欧拉路径，假设有 \(c\) 个联通分支，我们先弄 \(s\) 在的那个，然后是第二个，第三个以此类推，每次只需要多增加一条边即可。
假设我们连了 \(m\) 条边，则答案就是 \(m + e - 1\)。
为何是最小？首先，对于连通块内部的路径已经是最短的了，其次，将 \(c\) 个连通块变成一个也至少要 \(c - 1\) 条边，所以这个就是最优解。
点击查看代码
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, a[N] = {0}, b[N] = {0};
map<int, int> mp;
vector<int> e[N];
bool vis[N] = {false};
void dfs(int x) {
vis[x] = true;
for (auto i: e[x])
if (!vis[i])
dfs(i);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], mp[a[i]]++, a[0] ^= a[i];
for (int j = 1; j <= n; j++)
cin >> b[j], mp[b[j]]--;
mp[a[0]]++;
for (auto i: mp)
if (i.second < 0) {
cout << -1;
return 0;
}
int cur = 0;
for (auto &i: mp)
i.second = ++cur;
a[0] = mp[a[0]];
int ed = 0;
for (int i = 1; i <= n; i++) {
a[i] = mp[a[i]];
b[i] = mp[b[i]];
if (a[i] != b[i]) {
e[b[i]].push_back(a[i]);
e[a[i]].push_back(b[i]);
ed++;
}
}
int cnt = 0;
for (int i = 1; i <= cur; i++)
if (!vis[i] && (int)e[i].size() > 0)
dfs(i), ++cnt;
if ((int)e[a[0]].size() > 0)
cnt--;
cout << ed + cnt << endl;
return 0;
}