VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第二讲-数据结构-Trie AcWing 143. 最大异或对

Posted on Edited on In , , , ,

摘要：
Trie字典树不仅可以存储字符串，也可以存储二进制数，所以理论上Trie可以存储任意信息。

题目

在给定的 $N$ 个整数 $A_1，A_2……A_N$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

输入格式
第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1～A_N$。

输出格式
输出一个整数表示答案。

数据范围
$1≤N≤10^5$,

$0≤A_i<2^{31}$

输入样例：

3
1 2 3

输出样例：

3

Trie

暴力做法是遍历数组，对每个数，在剩余数中遍历找到和它异或最大的值。

可以对遍历找到最大异或值的步骤进行优化。

如果不考虑最大异或值的取值范围，某个数最大异或值，一定是其二进制每一位都不同的数。然而在这里取值范围是所有其他的数。

对该数二进制从左到右，我们在剩余数中找到一个数，使得其对应位的二进制值不同，如果没有则取相同。

可以使用 Trie 实现。构建 Trie 时，将每个数的二进制位从根节点开始插入。
查询某个数的最大异或值时，从根节点查找，如果存在二进制值相反的节点则选择该节点，不存在则选择二进制值相同的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100009;
int n, numbers[N];
int trie[31 * N][2];
int idx;


void build_trie(int &num)
{
    int p = 0;
    for (int i = 30; ~i; --i)
    {
        int u = num >> i & 1;
        if (!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }
}

ll query(int &num)
{
    int p = 0;
    ll target = 0;
    for (int i = 30; ~i; --i)
    {
        int u = num >> i & 1;
        if (trie[p][!u]) 
        {
            target = (target << 1) + !u;
            p = trie[p][!u];
        }
        else 
        {
            target = (target << 1) + u;
            p = trie[p][u];
        }
    }
    return target;
}

int main() 
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> numbers[i];
    
    ll res = 0;
    for (int i = 0; i < n; ++i)
    {
        int cur = numbers[i];
        build_trie(cur);
        res = max(res, query(cur) ^ cur);
    }
    cout << res << endl;
    return 0;
}

我们选择的是先对每个数拆分成二进制构建 Trie，再对每个数从 Trie 中查询最大异或值。
注意下 Trie 数组取值，因为最多 $10^5$ 个数，每个数最多 $31$ 位，所以数组行最多 $10^5 \times 31$，因为每个节点只存在两种值，$0$ 和 $1$，所以数组列为 $2$.

原题链接： AcWing 143. 最大异或对