前言：
Trie树：高效地存储和查找字符串集合的数据结构。
用于路径存储和路径查找，一种树结构。维护字符串集合。
题目一、trie字符串统计
835. Trie字符串统计 - AcWing题库
分析：
代码
其实就是 son[p] = ++idx; 根为0，空； 父母p索引 指向 孩子索引。 只是孩子是字符，多了个
son[p][u]； u 为0 - 25 映射26个字母 str[i]-'a';
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
char str[N];
int son[N][26], cnt[N],idx; // son 表示 父母索引指向孩子索引
// 二维数组模拟Trie树，里边存储索引（idx编号），横坐标代表路径，也是索引。纵坐标是哪一种字符。
// 总而言之，二维数组，横坐标代表根索引指向 儿子索引。 纵坐标代表儿子是哪一种字符。
//cnt[N] 用于统计字符串次数,搜索到某孩子索引为止，的个数。
// idx 编号，从0开始，0是根，也是空的。
void insert(char *str) {int p = 0;//根 // 0是根也是空的 // 遍历字符串for(int i = 0; str[i]; i ++) {// 孩子int u = str[i] - 'a';if(!son[p][u]) son[p][u] = ++idx; // 0是根，也是空 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() {int n;cin >> n;while(n --) {char op[2];cin >> op >> str;if(op[0]=='I') insert(str);else cout << query(str) << endl;}return 0;
} 题目二： 最大异或对
143. 最大异或对 - AcWing题库
分析
首先，考虑双循环暴力，TLE。可以看出 A[i]固定， 和挑选出A[i]^A[j] 最大值，选出A[j]. 那么对挑选优化。
怎么挑选？ 假设A[i] = (32位二进制） ： 100 11 00 11 .......100
首先如果其余第一位有0，则挑选0，其余除取（也就是减枝）。如果没有第一位为0的，没办法走1路径。后面同理。其实就是Trie树的数据结构。
代码（双循环暴力—TLE）
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int a[N];int main() {int n;cin >> n;for(int i = 0; i < n; i ++) cin >> a[i];int res = 0;for(int i = 0 ; i < n-1; i ++) {for(int j = i + 1; j < n; j ++) {res = max(res,a[i]^a[j]);}}cout << res << endl;return 0;
}代码：(优化后Trie树数据结构）
相当于 减枝 （确定后边的不要了，直接跳过）
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10, M = 3e6;
int n;
int son[M][2], idx; // M: 有N个数，每个数32位二进制
int a[N];
// Trie树
void insert(int x) {int p = 0;for(int i = 30; ~i; i --) {int &s = son[p][x>>i&1];if(!s) s = ++ idx;p = s;}
}
// 查询
int query(int x) {int res = 0, p = 0;for(int i = 30; ~i; i --) {int s = x >>i &1;if(son[p][!s]) {res += 1 << i;p = son[p][!s];}else p = son[p][s];}return res;
}int main() {cin >> n;for(int i = 0; i < n; i ++) {cin >> a[i];insert(a[i]);}int res = 0;// 每一种A[i] 都要匹配一种a[j] 使的对应res 最大， 再取n个res中最大for(int i = 0; i < n; i ++) res = max(res,query(a[i]));cout << res << endl;return 0;
}
