Statement

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

Solution

建立 0-1 Trie。

0-1 Trie 是一类特殊的字典树，之所以特殊，在于其的字符集为 。

由于二进制中数码也只有 ，所以 0-1 Trie 上的一条路径可以看做一个数的二进制位。

考虑如何在 0-1 Trie 上求异或最大值。

假定我们已经确定了第一个数为 ， 的某一位为 ，那么我们在 Trie 树上就要尽可能往 走，反之亦然。

因此，我们每读入一个数，先查询，后插入即可。

Code

#include<bits/stdc++.h>
using namespace std;

template < typename Tp >
inline void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

template < typename Tp >
inline void biread(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 2 + ch - '0', ch = getchar();
    x *= fh;
}

int ch[5000000][2], cnt = 1;

inline void insert(int x) {
    int p = 1;
    for(int i = 30; i >= 0; i--) {
        int q = ((x >> i) & 1);
        if(!ch[p][q]) ch[p][q] = ++cnt;
        p = ch[p][q];
    }
}

inline int query(int x) {
    int p = 1, res = 0;
    for(int i = 30; i >= 0; i--) {
        int q = ((x >> i) & 1);
        if(ch[p][q ^ 1]) {
            res += (1 << i);
            p = ch[p][q ^ 1];
        }
        else if(ch[p][q]) p = ch[p][q];
        else break;
    }
    return res;
}

int n, ans;

inline void Init(void) {
    read(n);
    for(int i = 1, x; i <= n; i++) {
        read(x); ans = max(ans, query(x));
        insert(x);
    }
    printf("%d\n", ans);
}

inline void Work(void) {

}

signed main(void) {
    Init();
    Work();
    return 0;
}