提交: 3 解决: 2
[提交] [状态] [命题人:admin]
题目描述
There is a sequence of length N: a=(a1,a2,…,aN). Here, each ai is a non-negative integer.Snuke can repeatedly perform the following operation:
Let the XOR of all the elements in a be x. Select an integer i (1≤i≤N) and replace ai with x.
Snuke's objective is to match a with another sequence b=(b1,b2,…,bN). Here, each bi is a non-negative integer.
Determine whether the objective is achievable, and find the minimum necessary number of operations if the answer is positive.
Constraints
2≤N≤105
ai and bi are integers.
0≤ai,bi<230
输入
Input is given from Standard Input in the following format:N
a1 a2 … aN
b1 b2 … bN
输出
If the objective is achievable, print the minimum necessary number of operations. Otherwise, print -1 instead.
样例输入
3 0 1 2 3 1 0
样例输出
2
来源/分类
操作为选择一个数，把这个数的值换为整个序列的异或和，交换之后整个序列的异或和就变为这个数的值。 求出a和b中所有数的异或和,存在a[0],b[0]，这n+1个数如果不相同，那a就不可能与b相同。 如果两个序列中的数是相同的，那么当a[i]!=b[i]时，在a[i]与b[i]之间建一条边。这样最后就会得到一个图，把图中一个联通块的数换为与b相同花费的次数与联通块的大小相同，从一个联通块跳至另一个联通块需花费1。由于一开始我们可以移动的是a[0],如果a[0]不属于任何联通块，那么从a[0]跳至别的联通块需花费1。#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e5 + 100;
int a[maxn], b[maxn];
int vis[maxn];
map<int, int> mp;
vector<int> e[maxn];
void dfs(int now) {
vis[now] = 1;
for (auto p:e[now]) {
if (!vis[p])
dfs(p);
}
}
int main() {
freopen("input.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[0] ^= a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
b[0] ^= b[i];
}
for (int i = 0; i <= n; i++) {
mp[a[i]]++;
mp[b[i]]--;
}
for (auto p:mp) {
if (p.second != 0) {
cout << -1 << endl;
return 0;
}
}
int id = 0;
int ans = 0;
for (int i = 0; i <= n; i++) {
if (!mp[a[i]]) mp[a[i]] = ++id;
}
for (int i = 0; i <= n; i++) {
if (a[i] != b[i]) {
e[mp[a[i]]].push_back(mp[b[i]]), ans++;
}
}
for (int i = 1; i <= id; i++) {
if (!vis[i] && !e[i].empty()) {
ans++;
dfs(i);
}
}
if (a[0] != b[0]) ans--;//a[0]和b[0]是不用花费一次交换使他们一样的，因为他们最终会变得一样
if (!e[mp[a[0]]].empty()) ans--;
cout << ans << endl;
return 0;
}