AcWing 143. 最大异或对
原题链接
简单
作者:
心之所向_7
,
2023-01-11 16:12:09
,
所有人可见
,
阅读 97
#include<iostream>
using namespace std;
const int N=100010,M=3000000;//M表示节点个数最多有31*100000
int n,son[M][2],idx;
int a[N];
void insert(int x)
{
int p=0;//当前节点为零
for(int i=30;~i;i--)//~i相当于i>=0;这里获取每一个二进制位创建trie
{
int &s=son[p][x>>i&1];//因为后面还需要用到s,这里用引用;获取x的每一位二进制数并存在s中
if(!s)s=++idx;//如果不存在子节点,则创造一个新节点
p=s;//当前节点指向新节点
}
}
int query(int x)//查询每个x在trie中最大异或值
{
int res=0,p=0;
for(int i=30;~i;i--)
{
int s=x>>i&1;
if(son[p][!s])//如果找到一个子节点与x的二进制不同
{
res=res*2+1;//相当于将res左移1加上1
p=son[p][!s];//p指向该子节点
}
else
{
res=res*2+0;//相当于将res左移1加上0
p=son[p][s];//找不到指向与x相同的子节点
}
}
return res;
}
int main()
{
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]));//找到当前异或的最大值
cout<<res<<endl;//将res以默认十进制格式输出
return 0;
}