Trie 树
基本用法
高效的存储和查找字符串集合的数据结构
模板
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
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];
}
Trie字符串统计
维护一个字符串集合，支持两种操作：
- “I x”向集合中插入一个字符串x；
- “Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数N，表示操作数。
接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。
输出格式
对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2?104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
代码样例
#include<iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N];
int 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';// 若不存当前字母的节点则直接返回 0 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. 最大异或对
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>#define x first
#define y secondusing namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;int gcd(int a, int b){
return b ? gcd(b, a % b) : a;}
int lowbit(int x) {
return x & -x;}int n;
int a[N], son[N][2], idx;void insert(int x){
int p = 0;for(int i = 30; i >= 0; i -- ){
int &s = son[p][x >> i & 1];if(!s) s = ++ idx;p = s;}}int search(int x){
int p = 0, res = 0;for(int i = 30; i >= 0; 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;for(int i = 0; i < n; i ++ ) res = max(res, search(a[i]));cout << res << endl;return 0;
}