「LOJ 10050」The XOR Largest Pair

Description

在给定的 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 中选出两个进行异或运算，得到的结果最大是多少？$(1 \leq n \leq 10^5,0 \leq a_i \leq 2^{31})$

Source

[LOJ]10050

Solution

转化问题：对于每个 $i\ (1 \leq i \leq n)$，我们需要找到一个 $j\ (1 \leq j < i)$，使得 $a_i \oplus a_j$ 的值最大（$\oplus $ 表示异或）。

我们可以建一棵 0-1 Trie 。

把每个数二进制分解，从高位到低位依次插入到 Trie 中（注意这道题中的二进制位不超过 $30$，高位补 $0$ ）。

在插入第 $i$ 个数之前，我们要先找到前 $i - 1$ 个数与 $a_i$ 异或的最大值来更新答案。

怎么找呢？我们从最高位开始，如果 $a_i$ 二进制下某一位是 $1$，就选择走 Trie 对应深度的 $0$ 的子树，反之则走 $1$ 的子树。这是根据异或运算的性质来使异或后的值这一位为 $1$，最大化答案。若不能取相反，则只能取相同，异或后这一位将为 $0$ 。

举例分析。假如我们已经在 Trie 中插入了 $5$ 个数：$1,2,4,5,7$，转化为二进制分别对应 $001,010,100,101,111$ 。（如图）

若我们要求 $3(011)$ 与这 $5$ 个数的最大异或值，则考虑走 $1-0-0$ 这一条路线，因为这样能使每一位都是 $1$ 。

若我们要求 $4(100)$ 与这 $5$ 个数的最大异或值，则考虑走 $0-1-0$ 这一条路线，本来选 $0-1-1$ 这条路线能得到异或最大值，但是在第 $2$ 个 $1$ 的位置时发现没有 $1$ 这条路，所以只能走 $0$ 。

对于每一个数我们都需要 $O(\log n)$ 的时间计算它与前面的数的最大异或值，所以时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n \log n)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
int n, ans;
struct Trie {
    int tot, ch[MAXN * 30 + 5][2];
    
    inline void insert(int x) {
        int u = 1;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v]) ch[u][v] = ++tot;//新建节点 
            u = ch[u][v];
        }
    }
    inline int find(int x) {
        int u = 1, res = 0;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v ^ 1]) u = ch[u][v];//如果没有相反的路，则沿相同的路走 
            else {
                u = ch[u][v ^ 1];//走相反的路
                res += 1 << i;//这一位为 1，累加答案 
            }
        }
        return res;
    }
} tr;

int main() {
    read(n);
    tr.tot = 1;
    for (int x, i = 1; i <= n; ++i) {
        read(x);
        ans = max(ans, tr.find(x));//查找 x 与 Trie 中已有数的异或最大值 
        tr.insert(x);//把 x 插入到 Trie 中 
    }
    write(ans);
    putchar('\n');
    return 0;
}