最大抑或对
目录
最大抑或对
#include<bits/stdc++.h>
using namespace std;
int idx=0;
const int maxn=1e5+100;
int ch[maxn*31][2];
int a[maxn];
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int j=x>>i&1;
if(!ch[p][j]){
ch[p][j]=++idx;
}
p=ch[p][j];
}
}
int query(int x)
{
int sum=0;
int p=0;
for(int i=30;i>=0;i--)
{
int j=x>>i&1;
if(ch[p][!j]){
sum+=1<<i;
p=ch[p][!j];
}
else p=ch[p][j];
}
return sum;
}
int main(){
int n;
cin>>n;
int maxx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
insert(a[i]);
}
for(int i=1;i<=n;i++){
maxx=max(maxx,query(a[i]));
}
cout<<maxx<<"\n";
}
就是说,给你一个数组,然后让你在数组中找到两个数字,求得他们的最大异或值。
我们如果暴力算,可以清晰的发现,就是外层从头遍历一遍找到第一个数字,内层同样遍历一遍,是第二个数字。这样是n2的复杂度,这样是肯定不行的。那么我可以换个角度想。
构建一个树。
这棵树就是从上到小,每一个结点存储的就是0或者1.异或就是相同为0不同为1.那么我们可以这样做,从根节点开始遍历,我们去找同层是否与当前节点不同的下一个边,如果存在,说明可以走。那么我们就可以加上当前的值(1«i)然后就这样一直走下去,直到走到最后的叶子节点。过程记录的答案,就是我们最后的答案。
外层是每一个数字,下面就是遍历树深度。最后的复杂度就是31n