The XOR Largest Pair（01字典树）

题目：

在给定的N个整数中选出两个进行运算，得到的结果最大是多少？

做法：

经典套路，字典树处理2个数的最值。其本质是一个贪心，高位若值为必定优于低位。我们把个整数依次插入字典树，每次插入前在字典树上跑一个贪心就能得到：前个数中选某个和第个数的最大值是多少。个数跑完取，最优解肯定在其中。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
struct Trie{
    static const int N = 5e6 + 7;
    int tot, ch[N][2];
    void insert(int x){
        int now = 0;
        for (int i = 30; i >= 0; --i){
            int b = (x>>i)&1;
            if (!ch[now][b]) ch[now][b] = ++tot;
            now = ch[now][b];
        }
    }
    int ask(int x){
        int now = 0, ans = 0;
        for (int i = 30; i >= 0; --i){
            int b = (x>>i)&1;
            if (ch[now][b^1]) now = ch[now][b^1], ans |= (1<<i);
            else now = ch[now][b];
        }
        return ans;
    }
}trie;
int main(void){
    IOS;
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        int x; cin >> x;
        if (i > 1) ans = max(ans, trie.ask(x));
        trie.insert(x);
    }
    cout << ans << endl;
    return 0;
}