字典树trie
顾名思义，在一个字符串的集合里查询某个字符串是否存在树形结构。
树存储方式上用的是结构体数组，类似满二叉树的形式。
模板
定义结构体和trie
- 结构体必须的内容：当前结点的字符，孩子数组
- 可选：
end用于查询，repeat用于统计。
typedef struct node {
char c;
int children[30] = {0};
int end = 0, repeat = 0;
};
vector<node>trie;
node root;
trie.push_back(root);
建树三部曲
- 不好理解的可能就是这个
fa，用于表示当前的父节点是谁。 - 查询结点是否存在于父节点的孩子中：
if (!trie[fa].children[idx]) 没有存在则添加结点：创建新下标
int new_idx = trie.size()，父节点的孩子添加该下标。
int new_idx = trie.size();
trie[fa].children[idx] = new_idx;
node x;
x.c = s[i];
if (i == s.size() - 1) {
x.end = 1;
}
trie.push_back(x);
- 父节点变为子节点：
fa = trie[fa].children[idx]
void build(string s) {
int fa = 0;
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
if (!trie[fa].children[idx]) {
int new_idx = trie.size();
trie[fa].children[idx] = new_idx;
node x;
x.c = s[i];
if (i == s.size() - 1) {
x.end = 1;
}
trie.push_back(x);
fa = new_idx;
}
else {
if (i == s.size() - 1) {
trie[fa].end = 1;
}
fa = trie[fa].children[idx];
}
}
}
字符串的查询
- 从父亲结点一直遍历到叶子结点，最后
i==s.size()-1时特判end是否为end==true?即可 - 与建树过程几乎完全一致
void query(string s) {
int fa = 0;
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
if (!trie[fa].children[idx]) {
cout << "WRONG" << endl;
return;
}
else {
fa = trie[fa].children[idx];
if (i == s.size() - 1) {
if (trie[fa].repeat) {
cout << "REPEAT" << endl;
}
else {
if (trie[fa].end) {
trie[fa].repeat = 1;
cout << "OK" << endl;
}
else cout << "WRONG" << endl;
}
}
}
}
}
打印字典树
void print_trie() {
for (int i = 0; i < trie.size(); i++) {
cout << trie[i].c << "|";
for (int j = 0; j < 30; j++) {
if (trie[i].children[j])cout << trie[i].children[j] << " ";
}
cout << "|" << trie[i].end << "|" << trie[i].repeat<<endl;
}
}
应用
- P2580 于是他错误的点名开始了:标准的查询字符串操作。
0-1字典树
将数字用二进制形式保存在trie中，一般是高位到低位。配合贪心思想，可以节约查询操作。
P4551 最长异或路径：这里需要用的异或的自反性质:自己跟自己异或不影响计算。当i<j, [ 1 , i ] ⊕ [ 1 , j ] = [ i , j ] [1,i] \oplus [1,j]=[i,j] [1,i]⊕[1,j]=[i,j], [ i , j ] [i,j] [i,j]表示i到j的异或路径。现在这个问题就变成了先获得[1,i]，然后再遍历每个j，计算 [ 1 , i ] ⊕ [ 1 , j ] [1,i] \oplus [1,j] [1,i]⊕[1,j]的最大值。时间复杂度为平方。将这些[1,i]结果保存为字典树，然后利用贪心从高位到低位选择最大的异或结果即可！
注意
bitset<int>val这个库，接受字符串和整型作为构造函数。一定要注意的是遍历时：从低位到高位遍历，val[0]表示从右往左第一位(也就是低位)。for (int i = bitval.size() - 1; i >= 0; i--)
#include<bits/stdc++.h>
#define MAX_VALUE 1000009
#define mod 1000007
using ll = long long;
using namespace std;
typedef struct node {
int x, w;
node(int a, int b) :x(a), w(b) {};
};
typedef struct trie_node {
int val, children[2] = { 0 };
};
vector<list<node>>graph(100009, list<node>());
int n, u, v, w, xors[100009], ans = INT_MIN;
vector<trie_node>trie;
void dfs(int st, int val) {
xors[st] = val;
for (auto item : graph[st]) {
dfs(item.x, val ^ item.w);
}
}
void build(int val) {
int fa = 0;
bitset<32>bitval(val);
//bitset[0]是指第一位
for (int i = bitval.size() - 1; i >= 0; i--) {
//cout << "val:"<<val<<" i:"<<i<<" bitval[i]:" << bitval[i] << endl;
if (!trie[fa].children[bitval[i]]) {
int new_idx = trie.size();
trie[fa].children[bitval[i]] = new_idx;
trie_node x;
x.val = bitval[i];
trie.push_back(x);
fa = new_idx;
}
else {
fa = trie[fa].children[bitval[i]];
}
}
}
int query(int val) {
int fa = 0;
bitset<32>bitval(val);//二进制
bitset<32>res;
//bitset[0]是指第一位
for (int i = bitval.size() - 1; i >= 0; i--) {
if (trie[fa].children[!bitval[i]]) {//取反
fa = trie[fa].children[!bitval[i]];
res[i] = 1;
}
else {
fa = trie[fa].children[bitval[i]];
res[i] = 0;
}
}
return (int)res.to_ulong();
}
void printout() {
for (int i = 0; i < trie.size(); i++) {
cout << trie[i].val << "|";
for (int j = 0; j < 2; j++) {
if (trie[i].children[j])cout << trie[i].children[j] << " ";
}
cout << "|" << endl;
}
}
void solve() {
cin >> n;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
graph[u].push_back(node(v, w));
}
dfs(1, 0);
//for (int i = 1; i <= n; i++) {
// cout << xors[i] << " ";
//}
//cout << endl;
trie_node root;
trie.push_back(root);
for (int i = 1; i <= n; i++) {
build(xors[i]);
}
//printout();
for (int i = 1; i <= n; i++) {
ans = max(ans, query(xors[i]));
}
cout << ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
solve();
return 0;
}
- P6824 「EZEC-4」可乐：这里x是有最大值的，暴力方法是对于每一个x都进行异或看看是否满足条件，时间复杂度为平方。利用a[i]构造0-1trie，可以在位级别，加速判断。对于第i位，如果k[i]为1，只需要找到与x[i]相同数字的结点，就一定可以知道x与该结点下的a[i]满足条件。如果k[i]=0，需要找到与x[i]相同数字的结点，否则一定不能与该父节点下的a[i]满足条件，提前结束。这里也是用由高位到低位的贪心思想。
#include<bits/stdc++.h>
#define MAX_VALUE 1000009
#define mod 1000007
using ll = long long;
using namespace std;
int n, k, a[1000009],res=INT_MIN;
typedef struct node {
int val, children[2] = {0}, repeat = 1;
};
vector<node>trie;
void build(int val) {
bitset<32>bitval(val);
int fa = 0;
for (int i = bitval.size() - 1; i >= 0; i--) {
if (!trie[fa].children[bitval[i]]) {
int new_idx = trie.size();
trie[fa].children[bitval[i]] = new_idx;
node x;
x.val = bitval[i];
trie.push_back(x);
fa = new_idx;
}
else {
int idx = trie[fa].children[bitval[i]];
fa = idx;
trie[idx].repeat++;
}
}
}
void printout() {
for (int i = 0; i < trie.size(); i++) {
cout << trie[i].val << "|";
for (int j = 0; j < 2; j++) {
if(trie[i].children[j])cout << trie[i].children[j] << " ";
}
cout << "|" << trie[i].repeat << endl;
}
}
int query(int val,int k) {
int ans = 0;
bitset<32>bitval(val);
bitset<32>bitk(k);
int fa = 0;
for (int i = bitval.size() - 1; i >= 0; i--) {
if (bitk[i]) {//bitk[i]==1
if (trie[fa].children[bitval[i]]) {//xor can be 0
int idx = trie[fa].children[bitval[i]];
//cout << bitval[i] << " "<<trie[idx].repeat << endl;
ans += trie[idx].repeat;
}
if (trie[fa].children[!bitval[i]]) {
fa = trie[fa].children[!bitval[i]];
}
else {
break;
}
}
else {//bitk[i]==0
if (trie[fa].children[bitval[i]]) {
fa = trie[fa].children[bitval[i]];
if (i == 0) {
ans += 1;//最后一个结点
//cout << "end:" << 1 << endl;
}
}
else break;
}
}
return ans;
}
void solve() {
node root;
trie.push_back(root);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
build(a[i]);
}
//printout();
for (int i = 0; i <= (1<<20); i++) {
res = max(res, query(i, k));
}
cout << res;
//cout<<query(0, k);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
solve();
return 0;
}