目录

最大抑或对

目录

最大抑或对

#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