Trie
定义
字典树，英文名 trie。顾名思义，就是一个像字典一样的树。
引入
这棵树包含了：
aa
aba
ba
caaa
cab
cba
ac
这几个单词。
如何维护
定义 son[i][j] 为在 i 号节点，往下边权为 j 的下一个节点。
struct trie {int son[100000][26],cnt;int back[100000];void insert(string s) { // 插入字符串int p=0;for (int i=0;i<s.size();i++) {int c=s[i]-'a';if (!son[p][c]) son[p][c]=++cnt;p=son[p][c];}back[p]++;}bool find(string s) { // 查找字符串int p=0;for (int i=0;i<s.size();i++) {int c=s[i]-'a';if (!son[p][c]) return 0;p=son[p][c];}return back[p];}
};
应用
应用于字符长度不长，但数量极多的情况。
- 字符串的前缀数量。
记录下沿途的 back 总和，就是答案。
struct trie {int son[100000][26],cnt;int back[100000];void insert(string s) { // 插入字符串int p=0;for (int i=0;i<s.size();i++) {int c=s[i]-'a';if (!son[p][c]) son[p][c]=++cnt; // 如果没有，就添加结点p=son[p][c];}back[p]++;}bool find(string s) { // 查找字符串前缀数量int p=0;int ans=0;for (int i=0;i<s.size();i++) {int c=s[i]-'a';if (!son[p][c]) return ans;p=son[p][c];ans=ans+back[p];}return ans;}
};
- 01字符串
如果是关于二进制，便可以直接转换为二进制。
例题:
给定 N 个整数 \(A_1,A_2,A_3,···,A_n\) 中选出两个进行异或计算，得到的结果最大是多少？
我们可以先枚举其中一个数，从高位开始，每一次如果能异或后得到一，便优先选择，最终取 n 个方案的最大值。
CODE:
#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=100005;
int n,A[N];
int tot,ch[N*32][2];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void ins(int x) {int p=0;for(int i=30;i>=0;i--) {int j=(x>>i)&1;if(ch[p][j]==0) ch[p][j]=++tot;p=ch[p][j];}
}
int find(int x){int p=0,ans=0;for(int i=30;i>=0;i--) {int j=(x>>i)&1;int k=j?0:1;if(ch[p][k]==0) p=ch[p][j];else p=ch[p][k],ans+=(1<<i);}return ans;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++) {cin>>A[i];ins(A[i]);}int ans=0;for(int i=1;i<=n;i++)ans=max(ans,find(A[i]));cout<<ans;return 0;
}