18款禁用网站app直播,创新的福州网站建设,推动高质量发展的意义,建设网站了还能消除吗Trie树学习总结 字典树#xff0c;又称前缀树#xff0c;是用于快速处理字符串的问题#xff0c;能做到快速查找到一些字符串上的信息。 另外#xff0c;Trie树在实现高效的同时#xff0c;会损耗更多的空间#xff0c;所以Trie是一种以空间换时间的算法。 Trie的思想 Tr… Trie树学习总结 字典树又称前缀树是用于快速处理字符串的问题能做到快速查找到一些字符串上的信息。 另外Trie树在实现高效的同时会损耗更多的空间所以Trie是一种以空间换时间的算法。 Trie的思想 Trie的思想十分简单其实我在很早之前就已经懂了Trie的思想只不过一直没有实现所以就…… 咕咕没事Trie无论是思想还是代码思想都还是很简单。现在我重新再搞回Trie也很快就代码实现了。 Trie是思想其实用图更容易展现。下面放一张图给大家看看相信大家很快就会明白了。 如果我们插入字符串 zlh
AK
tql
AKIOI
AKnoip 上面就是一颗我们建的Trie树。 如果我们要查找“zlh”那么就会沿着1-2-3点找下去。 如果我们要查找“AKIOI”那么我们就会沿着4-5-9-10-11点找 也可以十分容易发现AK是AKIOI的前缀。 那么大家现在应该就能明白Trie的构造了吧。 简单说就是顺着之前Trie树的构造去插入点例如我们最后插入AKnoip就会先走过A和K然后发现没有匹配的字符了就先后新建了n,o,i,p这几个点。复杂度O(len(字符串))。 查询就会沿着Trie的构造一个一个跳所以查询复杂度是O(len(字符串))。 那么Trie的思想就是这样了。 Trie的实现 明白了思想实现就应该很简单了吧这里通过一道例题来实现Trie。 题目P2580 于是他错误的点名开始了 定义 struct kkk{int son[27],cnt;bool flag;
}trie[maxn]; 首先是插入操作 void insert(string s){int lens.size(),u0; //获取长度lenu是当前点的编号根的编号是0for(int i0;ilen;i){int vs[i]-a; //获取位置if(!trie[u].son[v]) //如果没有继续下去的节点trie[u].son[v]num; //就新建一个utrie[u].son[v]; //跳到下一个点去插入}trie[u].flagtrue; //标记此处是一个单词
} 然后是查询操作 int find(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-a; //同上if(!trie[u].son[v])return 3; //找不到返回没有utrie[u].son[v]; //同上}if(trie[u].flagfalse)return 3; //不是一个单词就返回没有if(!trie[u].cnt){ //如果没有被点过trie[u].cnt; //标记被点过了return 1; //返回有} return 2; //不然返回重复
} 那么Trie的实现就这样了。 Trie的考点 异或XOR以及利用XOR的性质后缀转前缀记忆化缩点重构树Trie的思想见 P3294 [SCOI2016]背单词P2292 [HNOI2004]L语言可持久化详见下文 随便给点题 phone list The XOR Largest Pair Nikitosh 和异或 Immediate Decodability [SCOI2016]背单词 [HNOI2004]L语言 [USACO08DEC]秘密消息Secret Message 最长异或路径 做完上面那几道应该就能了解Trie了 习题讲解 1、phone list 题目Phone list 题目意思十分明确求有没有一个字符串是其他字符串的前缀如果有就返回NO没有返回YES。 这题和前面讲的Trie的作用一模一样可以快速判断一个字符串是不是已插入的字符串中的前缀。 那么这道题就很简单了我们先将全部字符串都插入到Trie中。 然后查找每一个字符串如果字符串下有儿子那么就代表当前字符串是某个字符串的前缀直接返回。 代码实现也很简单可以算是Trie的模板题。 #includebits/stdc.h
using namespace std;
struct kkk{int son[11],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum0;flag0;} //清0
}trie[400001];
int n,T,num;
string S[400001];
void insert(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])trie[u].son[v]num;trie[u].sum; //表示u有多少个儿子utrie[u].son[v];}trie[u].flagtrue;
}
int find(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])return 0; //找不到字符串就返回utrie[u].son[v];}if(trie[u].sum0)return 0; //如果没有儿子就代表不是前缀return 1; //否则就是前缀
}
int main(){scanf(%d,T);while(T--){num0; //记得清0for(int i0;i400000;i)trie[i].clear(); //记得清0scanf(%d,n);for(int i1;in;i){cinS[i];insert(S[i]); //一个一个插入}bool ansfalse;for(int i1;in;i){int resfind(S[i]); //查询if(res1){anstrue;break;} //判断是不是前缀}if(anstrue)printf(NO\n); //输出else printf(YES\n);}
} 2、Immediate Decodability 题目Immediate Decodability 这道题和上面那道题一模一样不过输入比较恶心而且数据范围也比较小。 这里的输入就是不断输入字符串S然后将字符串S插入到Trie中直到S9为止。 到了S9就将之前的S都像上面的一样查询一边输出答案然后清0。 代码 #includebits/stdc.h
using namespace std;
struct kkk{int son[11],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum0;flag0;}
}trie[2001];
int n,T,num,t;
string S[400001];
void insert(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])trie[u].son[v]num;trie[u].sum;utrie[u].son[v];}trie[u].flagtrue;
}
int find(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])return 0;utrie[u].son[v];}if(trie[u].sum0)return 0;return 1;
}
void solve(){ //解决之前的字符串bool ansfalse;for(int i1;in;i){int resfind(S[i]);if(res1){anstrue;break;}}if(anstrue)printf(Set %d is not immediately decodable\n,t);else printf(Set %d is immediately decodable\n,t);
}
int main(){n1;while(cinS[n]){if(S[n]9){t;solve(); //解决之前的问题memset(trie,0,sizeof(trie)); //清0num0;n1;continue; //清0}insert(S[n]);n; //如果不是‘9’就插入}
} 3、The XOR Largest Pair 题目The XOR Largest Pair 这道题是一道变向的Trie也是Trie的一个基本应用。 思路 1、首先将a[i]转换为二进制的字符串存起来记得空位要补0 2、然后将这些字符串都插入到Trie里。 3、查询每一个字符串找到以每一个数和另外其他数的最大异或和。 那么问题就是怎么找一个数和另外其他数的最大异或和了。 我们知道异或是不同就为1相同就为0所以我们因尽量让高位的二进制为1。 所以我们查询的时候就倒着查也就是如果s[i]为0那么我们就查1。但是没有1怎么办我们总不能就此放弃吧于是我们继续查0。 最后取个最大值就OK了。 看看代码 #includebits/stdc.h
using namespace std;
struct kkk{int son[3],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum0;flag0;}
}trie[4000001];
int n,T,num,ans;
int x[1000001];
void insert(string s){ //插入int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])trie[u].son[v]num;trie[u].sum;utrie[u].son[v];}trie[u].flagtrue;
}
int find(string s){int lens.size(),u0,ans0,num(int)(2147483648ll/2ll);for(int i0;ilen;i){int v((s[i]-0)^1); //倒着查if(!trie[u].son[v])v^1; //找不到就倒回来else ansnum; //不然就累加进去utrie[u].son[v];num/2; //跳下一个}return ans;
}
string decompose(int x){ //拆分成二进制string s;while(x!0)s(x%2)0,x1;while(s.size()!31)s0;reverse(s.begin(),s.end());return s; //返回字符串
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d,x[i]);string sdecompose(x[i]);insert(s);}for(int i1;in;i){int resfind(decompose(x[i]));ansmax(ans,res); //取最大值}printf(%d\n,ans);
} 4、[USACO08DEC]秘密消息Secret Message 题目大意给你n个信息和m个密码要你求出对于每一个密码都多少信息使这些信息的前缀和密码的前缀相同。 理解清题目这道题就很简单了我们用信息来在建立Trie时多维护一个数据sum存的是有多少个信息经过这个节点。那么我们在查询时先统计有多少信息是密码的前缀再加上当前节点的sum就是答案。 #includebits/stdc.h
using namespace std;
struct kkk{int son[11],sum,flag;void clear(){memset(son,0,sizeof(son));sum0;flag0;}
}trie[400001];
int n,T,num,ans;
string S[400001];
void insert(string s){int lens.size(),u0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])trie[u].son[v]num;utrie[u].son[v];trie[u].sum; //记录sum}trie[u].flag; //有重复所以要加加
}
int find(string s){int lens.size(),u0,ans0;for(int i0;ilen;i){int vs[i]-0;if(!trie[u].son[v])return ans; //找不到utrie[u].son[v];anstrie[u].flag; //记录信息是密码前缀}return ans-trie[u].flagtrie[u].sum; //-trie[u].flag是为了去重
}
int main(){int n,m;scanf(%d%d,n,m);for(int i1;in;i){int x;scanf(%d,x);string s;char c;for(int j1;jx;j)cinc,sc;insert(s);}for(int i1;im;i){int x;scanf(%d,x);string s;char c;for(int j1;jx;j)cinc,sc;ansfind(s);printf(%d\n,ans);}
} 5、Nikitosh 和异或 题目在这里「一本通 2.3 例 3」Nikitosh 和异或 首先对于如何求异或最大值我们已经在上文学到了现在我们要求的是两个没有覆盖的区间异或的和。 异或有一个性质就是据有可减性也就是说我们记前缀异或sum数组如果求[l,r]的异或和那么答案就是sum[r]^sum[l-1];后缀异或也是一样的 所以我们可以对于每一个位置i都求一遍以i为结尾的区间中最大的区间异或值。方法是将i前面的每一个前缀sum数组都插入到Trie中然后find(sum[i])答案计为l数组。 另外对于每一个位置i都求一遍以i为开头的区间中最大的区间异或值。方法是将i后面的每一个后缀sum数组都插入到Trie中然后find(sum[i])答案计为r数组。 那么对于每一个位置i都统计前面的最大的l记录下来。表示的是i前面的最大区间异或和 对于每一个位置i都统计后面的最大的r记录下来。表示的是i后面的最大区间异或和 那么答案就是对于每一个位置i的 前面的最大区间异或和 和 后面的最大区间异或和 的 和 的最大值 代码 #includebits/stdc.h
using namespace std;
struct kkk{int son[3];void clear(){memset(son,0,sizeof(son));}
}trie[8000001];
int n,T,num,ans;
int x[1000001],l[1000001],r[1000001],s[35];
void insert(int x){int j-1,u0;memset(s,0,sizeof(s));while(x){s[j]x1;x1;}for(int i31;i0;i--){if(!trie[u].son[s[i]])trie[u].son[s[i]]num;utrie[u].son[s[i]];}
}
int find(int x){int ans0,u0;for(int i31;i0;i--){int v1-s[i];if(!trie[u].son[v])v^1;else ans(1i);utrie[u].son[v];}return ans;
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d,x[i]);}int sumx0;num0;for(int i1;in;i)sumx^x[i],insert(sumx),l[i]max(l[i-1],find(sumx));memset(trie,0,num1);sumx0;num0;for(int in;i1;i--)sumx^x[i],insert(sumx),r[i]max(r[i1],find(sumx));for(int i1;in;i)ansmax(ans,l[i]r[i1]);printf(%d\n,ans);
} 可持久化Trie 转载于:https://www.cnblogs.com/hyfhaha/p/10684418.html
