AcWing 143. 最大异或对
原题链接
简单
作者:
腾杨天下
,
2021-04-06 01:41:09
,
所有人可见
,
阅读 342
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int tr[32*N][2];//小心数组爆堆,本题用了14m内存,计算内存的方法,int数组:4*数组数量/1024/1024(MB)
int a[N];
int idx;
//bool st[32*N]; 这一个判断函数不需要了,之前在字符串那题我们需要一个cnt函数是用来计数,
//并且标记存在这样一个字符串,但是现在我们直到我们如果要搜索一个数,一定会搜索到深度为31(从0深度开始)的
//节点也就是一定会搜索31次,每一个节点都互不相干,不存在数串与数串之间的包含关系,所以搜索31次之后我们一定
//会得到一个唯一的数字,所以我们不需要这样的一个判断函数了
void insert(int x)
{
int p=0;
for(int i=30;i>=0;i--)//一共要做31次位运算,把整数x以32位存到Trie树当中去
{
int u=x>>i&1;
if(!tr[p][u])tr[p][u]=++idx;
p=tr[p][u];
}
//st[p]=true;//每一位数串之间都不存在包含关系,且每一位数串都是唯一的,深度相同的(指31深度)
}
int search(int x)
//因为不太好直接找到数组当中高位异位最多的两个整数,所以我们可以查找某一个整数的最大异或值是多少
//最后我们只需要在每一个a[i]的最大异或值当中取一个最大值即可
{
int p=0,ret=0;
for(int i=30;i>=0;i--)
{
int u=x>>i&1;
if(tr[p][!u])//搜索当前节点的子结点中是否存在与x的第i位不同的数
{
p=tr[p][!u];//如果有,我们把p指到这个有的节点去
ret=(ret<<1)+1;//ret左移一位并+1,这个左移的过程我们会做31次,最高可以使ret达到2^31-1
}
else
{
p=tr[p][u];
ret=ret<<1;//不管有没有搜索到这个节点,我们都要让ret左移,如果没搜索到那么我们就只左移不+1
}
}
return ret;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];//存到数组里面
insert(a[i]);//以二进制存到Trie树里面
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,search(a[i));//寻找所有a[i]的异或值当中的最大值
cout<<ans;
return 0;
}