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
class Trie {
 public:
  struct Node {
    bool is_end;
    Node* son[26];
    Node() {
      is_end = false;
      for (int i = 0; i < 26; i++) {
        son[i] = NULL;
      }
    }
  } * root;
  /** Initialize your data structure here. */
  Trie() { root = new Node(); }

  /** Inserts a word into the trie. */
  void insert(string word) {
    auto p = root;
    for (auto c : word) {
      int u = c - 'a';
      if (!p->son[u]) {
        p->son[u] = new Node();
      }
      p = p->son[u];
    }
    p->is_end = true;
  }

  /** Returns if the word is in the trie. */
  bool search(string word) {
    auto p = root;
    for (auto c : word) {
      int u = c - 'a';
      if (!p->son[u]) return false;
      p = p->son[u];
    }
    return p->is_end;
  }

  /** Returns if there is any word in the trie that starts with the given
   * prefix. */
  bool startsWith(string prefix) {
    auto p = root;
    for (auto c : prefix) {
      int u = c - 'a';
      if (!p->son[u]) return false;
      p = p->son[u];
    }
    return true;
  }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

用数组模拟实现，速度更快。

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
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
// 可以理解为一次性先 new N 个节点，每个节点对应一个标号
// son[i][j] 表示标号为 i 的点的第 j 个儿子节点的标号
// cnt[i] 表示以标号为 i 的点结尾的单词个数
// idx 当前分配到了哪个标号
int son[N][26], cnt[N], idx;

char str[N];

void insert(char str[]) {
  int p = 0;
  for (int i = 0; str[i]; i++) {
    int u = str[i] - 'a';
    if (!son[p][u]) son[p][u] = ++idx;
    p = son[p][u];
  }
  cnt[p]++;
}

int query(char str[]) {
  int p = 0;
  for (int i = 0; str[i]; i++) {
    int u = str[i] - 'a';
    if (!son[p][u]) return 0;
    p = son[p][u];
  }
  return cnt[p];
}

int main() { return 0; }

最大异或对

枚举 AiA_i，通过 trie 树优化查询与 AiA_i 异或值最大的元素。为了使异或值最大，需要从最高位开始选择与 AiA_i 最高位不同的那些数。枚举时先将 AiA_i 二进制形式插入到 trie 树，然后从最高位查询与 AiA_i 每一位相反的路径。

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
#include <iostream>
using namespace std;

// 每个数有 31 位，一共有 N 个数，所以需要开辟 31 * N 个 trie
// 树节点，每个节点有两个孩子，存储 1 和 0
const int N = 100010, M = 31 * N;

int n;
int a[N];
int son[M][2], idx;

void insert(int x) {
  int p = 0;
  for (int i = 30; i >= 0; i--) {
    int u = x >> i & 1;
    if (!son[p][u]) son[p][u] = ++idx;
    p = son[p][u];
  }
}
int query(int x) {
  int p = 0, res = 0;
  for (int i = 30; i >= 0; i--) {
    int u = x >> i & 1;
    if (son[p][!u]) {
      res = res * 2 + !u;
      p = son[p][!u];
    } else {
      res = res * 2 + u;
      p = son[p][u];
    }
  }
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    insert(a[i]);
    int t = query(a[i]);
    res = max(res, a[i] ^ t);
  }
  printf("%d\n", res);
  return 0;
}