| 数论中的异或 | ||||||
| ||||||
| Description | ||||||
| 给出两集合A和B, 找出最小的非负整数x使得A⊕x=B. 假设A={a1,a2,…,an}, A⊕x={a1⊕x,a2⊕x,…,an⊕x}.⊕代表异或操作 | ||||||
| Input | ||||||
| 输入的第一行是一个整数T，表示一共有T组测试数据； 对于每组测试数据，第一行是一个整数n代表集合A和B的大小 第二行包含n个整数a1,a2,a3,....an，代表集合A的元素。 第三行包含n个整数b1,b2,b3,....bn，代表集合B的元素。 (1<=n<=100000，n是奇数，0<=ai<2^30) | ||||||
| Output | ||||||
| 如果存在x就输出最小的x，如果不存在就输出-1。 | ||||||
| Sample Input | ||||||
| 1 3 0 1 3 1 2 3 | ||||||
| Sample Output | ||||||
| 2 |
不知道是不是数据太水了，我写的AC代码过不了队友写的样例，但是交上后竟然过了。
我的思路：因为数组a和b的数为n个，且n为奇数，那么就去找a和b里面不同的数个数，如果不同数的个数为1，那么结果就是这两个数异或的值，如果超过一个，则输出-1 。
因为数组的元素个数均为奇数，那么两数组去掉非公共数之后肯定能有一个数x，a异或x可以得到b里面的数，而数x就是这两个不相同的数异或得到的。
感觉这样写漏洞好多，比如：如果a，b中有三个不相同的数，但是可以通过a异或数x得到b，这种情况在我的代码里输出是-1，但是应该是存在数x的（没有验证，不知道是不是真的存在）。
欢迎各位大佬留言找到的错误数据
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=1e6+3;
ll a[maxn],b[maxn];
int main()
{
int n,t;
scanf("%d",&t);
while(t--)
{
int sum=0;
map<int,int>p;
ll sum1=0;
ll sum2=0;
ll sum3=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
sum1+=a[i];
p[a[i]]=1;
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
sum2+=b[i];
if(p[b[i]]==0) sum+=1;
else sum3+=b[i];
}
if(sum>1) printf("-1\n");
else
printf("%lld\n",(sum1-sum3)^(sum2-sum3));
}
return 0;
}