The XOR Largest Pair

The XOR Largest Pair

分析

• 一道模板题，先将所有的数按数位从高到低加入到字典树中，从最高位到最低位贪心

代码

/*
(写点什么吧...)
*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=1e5+10;

int n,tot;
int a[N],tr[2][N*20];

inline void insert(int x)
{
    int rt=0;
    for (int i=30;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(!tr[c][rt]) tr[c][rt]=++tot;
        rt=tr[c][rt];
    }
}

inline int find(int x)
{
    int ret=0,rt=0;
    for (int i=30;i>=0;i--)
    {
        bool c=((x>>i)&1);
        if(tr[c^1][rt])
            ret+=(1<<i),rt=tr[c^1][rt];
        else rt=tr[c][rt];
    }

    return ret;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        insert(a[i]);
    }

    int ans=0;
    for (int i=1;i<=n;i++)
        ans=max(ans,find(a[i]));

    printf("%d\n",ans);

    return 0;
}