The XOR Largest Pair

前言：暑假集训时学的字典树orz 太弱了www
模板用的是wiki上用一个结构体封装的模板（当时就是看wiki学的字典树
链接：https://oi-wiki.org/string/trie/

做法：01字典树

思路：

• 一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串.
• 每一次检索的时候,我们都走与当前这一位相反的位置走,也就是让异或值最大,如果说没有路可以走的话,那么就走相同的路.

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;

int ans,a[N];
struct Trie {
    int nex[N*32][2],cnt=0;

    void insert(int x) {  
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt;  
            p = nex[p][c];
        }
    }
    int find(int x) { 
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(nex[p][c^1]) p=nex[p][c^1],res|=(1<<i);
            else p=nex[p][c];
        }
        return res;
    }
} t;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    int n;
    cin>>n;
    _for(i,n){
        cin>>a[i];
        t.insert(a[i]);
    }
    _for(i,n){
        ans=max(ans,t.find(a[i]));
    }
    cout<<ans;
    return 0;
}