【题解】数组Xor
题意
给你一个数组和
，你可以将数组中的元素变为其与
的异或值，问你最少操作多少次使得数组中能有两个相同值，无解输出
题解
答案只会是。根据异或的性质，
时表示
，所以不会出现需要数组中两个元素异或过后相等的情况，这说明数组原本就有两个元素相等了，不需要异或操作，所以答案是
。若原数组中没有两个元素相等，我们先将数组中元素进行记录一下，然后依次对数组元素与
的异或值进行判断是否在字典中出现过。若出现过那么答案就是
，若整个数组都处理完了也没有答案，说明无解输出
复杂度
时间复杂度
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int vis[N];
int main()
{
int n,x;
scanf("%d%d",&n,&x);
int flag=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
vis[a[i]]++;
if(vis[a[i]]>1)
{
flag=1;
}
}
if(flag)
{
printf("0\n");
return 0;
}
for(int i=0;i<n;i++)
{
if(vis[a[i]^x]==1)
{
printf("1\n");
return 0;
}
}
printf("-1\n");
return 0;
}
查看30道真题和解析
腾讯公司福利 867人发布