最大异或对

Trie树的应用

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N * 31][2];
int idx;
int a[N];
void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(!son[p][u])son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int qurry(int x)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(son[p][!u]){
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        insert(a[i]);//因为题目只需要枚举两个数之间异或的结果，异或具有交换律,所以可以先插入在做
        
        int t = qurry(a[i]);
        
        ans = max(a[i] ^ t, ans);
    }
    cout << ans<<endl;
    return 0;
}

链接