跳转至

字典树

模版
C++
 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
struct Trie {
    const static int N = 100000;
    const static int M = 26;
    int nxt[N][M], exist[N], tree_size;
    Trie() {
        tree_size = N;
        clear();
    }
    void clear() {
        for (int i = 0 ; i < tree_size ; i++) {
            for (int j = 0 ; j < M ; j++) {
                nxt[i][j] = 0;
            }
            exist[i] = 0;
        }
        tree_size = 0;
    }
    void insert(string str) {
        int len = str.size(), index = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            if (nxt[index][c] == 0) nxt[index][c] = ++tree_size;
            index = nxt[index][c];
        }
        exist[index]++;
    }
    int find(string str) {
        int len = str.size(), index = 0;
        for (int i = 0 ; i < len ; i++) {
            int c = str[i] - 'a';
            if (nxt[index][c] == 0) return 0;
            index = nxt[index][c];
        }
        return exist[index];
    }
}; // Trie
例题

P8306 【模板】字典树 - 洛谷

143. 最大异或对 - AcWing题库

\(n\) 个整数 \(a\), 任选两个数进行异或，求最大值。

代码
C++
 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
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

// 2024 OneWan

struct Trie {
    const static int N = 100000 * 30;
    const static int M = 2;
    int nxt[N][M], exist[N], tree_size;
    Trie() {
        tree_size = N;
        clear();
    }
    void clear() {
        for (int i = 0 ; i < tree_size ; i++) {
            for (int j = 0 ; j < M ; j++) {
                nxt[i][j] = 0;
            }
            exist[i] = 0;
        }
        tree_size = 0;
    }
    void insert(int x) {
        int index = 0;
        for (int i = 30 ; i >= 0 ; i--) {
            int c = x >> i & 1;
            if (nxt[index][c] == 0) nxt[index][c] = ++tree_size;
            index = nxt[index][c];
        }
        exist[index]++;
    }
    int query(int x) {
        int res = 0, index = 0;
        for (int i = 30 ; i >= 0 ; i--) {
            int c = x >> i & 1;
            if (nxt[index][c ^ 1]) {
                res |= 1 << i;
                index = nxt[index][c ^ 1];
            } else if (nxt[index][c]) {
                index = nxt[index][c];
            } else {
                return res;
            }
        }
        return res;
    }
}; // Trie

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    Trie trie;
    int ans = 0;
    for (int i = 0 ; i < n ; i++) {
        int x;
        cin >> x;
        int res = trie.query(x);
        ans = max(ans, res);
        trie.insert(x);
    }
    cout << ans;
    return 0;
}