什么是异或_异或运算及异或运算的作用_cxu123321的博客-CSDN博客_异或
题目:
暴力做法(会超时):
先固定其中一个数Ai,然后从A1~An中选出一个值Aj,使得Ai^Aj最大,枚举Ai
#include<iostream>
using namespace std;
const int N=10e5+10;
int n,a[N];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
res=max(res,a[i]^a[j]);
}
}
cout<<res;
return 0;
}
优化:trie
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int const N=100010,M=31*N;
int n;
int a[N];
int son[M][2],idx; //M代表一个数字串二进制可以到多长
void insert(int x)
{
int p=0; //根节点
for(int i=30;~i;i--) //从最高位开始枚举,i>=0等价于~i
{
int &s=son[p][x >> i & 1]; //看一下x的二进制表示中第i位是0还是1
if(!s) s = ++ idx; //如果插入中发现没有该子节点,就创建新节点,idx是下一个点的下标
p = s; //p走到s的位置,指针指向下一层
}
}
int query(int x) //把每一个整数看出一个31位长度的二进制数
{
int p=0;int res=0; //p是在树上遍历的指针
for(int i=30;i>=0;i--)
{
int s = x >> i & 1;
if(son[p][!s]) //和当前不一样的分支存在时
{
p=son[p][!s]; //p指针就走到这个不一样的分支上
res=res*2+1; //等价于res+=1<<i;
}
else //否则就往当前分支走
{
p=son[p][s];
res=res*2+0; //等价于res+=0<<i;此步可以省略
}
}
return res;
}
int main(void)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]); //建索引
}
int res=0;
for(int i=0;i<n;i++)
{
res=max(res,query(a[i])); //query(a[i])查找的与当前这个数异或值最大的结果
}
cout<<res<<endl;
}