企业官网建设流程全解析

辽宁网站建设fengyan,成都制作网站的公司简介,什么网站可以做平面设计赚钱,dede cms 网站模板字典树 字典树的原理是复用前缀信息#xff0c;所以字典树又叫前缀树。 构建过程 这里只介绍基本的构建框架#xff0c;因为字典树的能实现的功能很多#xff0c;所以结点信息种类也很多#xff0c;不可能把所有的信息都写上#xff0c;所以只写框架#xff0c;后续再…字典树字典树的原理是复用前缀信息所以字典树又叫前缀树。构建过程这里只介绍基本的构建框架因为字典树的能实现的功能很多所以结点信息种类也很多不可能把所有的信息都写上所以只写框架后续再根据题目自己补充。假设字符集是a ∼ z \mathrm a\sim\mathrm za∼z共26 \mathrm {26}26个字符最开始字典树有一个根结点1 \mathrm 11然后这个根结点需要维护26 2626条边( c h a r , v ) (\mathrm {char},\mathrm v)(char,v)表示这条边对应的字符种类以及这条边的另一个端点v \mathrm vv。最初26 \mathrm {26}26条边都不存在。加入字符串最初我们在树根设其深度为d e e p \mathrm {deep}deep根节点的深度为0 \mathrm 00全局维护一个结点池c n t \mathrm {cnt}cnt初值为1 \mathrm 11。我们要将字符串s \mathrm ss加入树中对于当前字符s d e e p \mathrm {s_{deep}}sdeep​检查当前结点是否存在对应字符的边( s d e e p , v ) \mathrm {(s_{deep},v)}(sdeep​,v)如果存在则前往下一个结点v \mathrm vv重复检查过程如果不存在那么给当前结点建边( s d e e p , c n t 1 ) \mathrm {(s_{deep},cnt1)}(sdeep​,cnt1)然后跳转到下一个结点c n t 1 \mathrm {cnt1}cnt1直到访问到字符串最后一位字符。查询字符串是否存在最初我们在树根我们查询字符串s \mathrm ss是否在树中出现过。对于当前字符s d e e p \mathrm {s_{deep}}sdeep​检查当前结点是否存在对应字符的边( s d e e p , v ) \mathrm {(s_{deep},v)}(sdeep​,v)如果存在则前往下一个结点v \mathrm {v}v如果不存在直接报告不存在如果访问到最后一个字符仍存在那么报告存在。删除字符串这个具体题目有具体的删除方式主要是看我们给每个结点定义了怎样的信息参照之前每个字符串是如何贡献的删除字符串就是将字符串的贡献取消。模板1模版题1查询某个字符串是否出现以及是否出现过两次。需要给每个结点加一些额外信息即e n d \mathrm{end}end其中e n d \mathrm {end}end表示当前结点以末尾的形式出现的次数。#includebits/stdc.husingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl\n#definePIIpairint,int#defineINF1e18constintM1e5;constintN1e4;inttr[50*N50][27];intEnd[50*N50];intcnt1;intexist(strings){intnext1;for(inti0;is.size();i){if(!tr[next][s[i]-a]){return0;}nexttr[next][s[i]-a];}returnEnd[next];}voidadd(strings){intnext1;for(inti0;is.size();i){if(!tr[next][s[i]-a]){tr[next][s[i]-a]cnt;}nexttr[next][s[i]-a];}End[next];return;}voidslove(){intn;cinn;for(inti1;in;i){string s;cins;add(s);}intm;cinm;for(inti1;im;i){string s;cins;inttexist(s);if(t!0)add(s);if(t0)coutWRONGendl;elseif(t1)coutOKendl;elsecoutREPEATendl;}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();}模板2判断在所有字符串中是否存在一个字符串是另一个字符串的前缀。实现这个功能我们需要给结点维护两个信息一个是p a s s \mathrm {pass}pass一个是e n d \mathrm {end}end。p a s s \mathrm {pass}pass统计的是当前结点被经过多少次e n d \mathrm {end}end统计的是以当前结点为终点的字符串有多少个。那么我们只需要判断是否存在一个结点的e n d \mathrm {end}end大于0 \mathrm 00的情况下p a s s \mathrm {pass}pass至少为2 \mathrm 22。所以只需要按顺序添加字符串然后判断这个字符串的末尾结点的p a s s \mathrm{pass}pass是否大于1 \mathrm{1}1。#includebits/stdc.husingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl\n#definePIIpairint,int#defineINF1e18constintM1e5;constintN1e4;inttr[50*N50][27];intEnd[50*N50];intPass[50*N50];intcnt1;intexist(strings){intnext1;for(inti0;is.size();i){if(!tr[next][s[i]-0]){return0;}nexttr[next][s[i]-0];}returnnext;}voidadd(strings){intnext1;Pass[next];for(inti0;is.size();i){if(!tr[next][s[i]-0]){tr[next][s[i]-0]cnt;}nexttr[next][s[i]-0];Pass[next];}End[next];return;}voidslove(){for(inti1;icnt;i){for(intj0;j10;j){tr[i][j]0;}Pass[i]0;End[i]0;}cnt1;intn;cinn;intflag0;vectorstringv(n1);for(inti1;in;i){cinv[i];add(v[i]);}for(inti1;in;i){intnextexist(v[i]);if(Pass[next]1){flag1;}}if(flag)coutNOendl;elsecoutYESendl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT;cinT;while(T--)slove();}异或字典树将每个二进制当作一个字符串s t r i n g \mathrm {string}string构建一棵字符集为{ 0 , 1 } \mathrm {\{0,1\}}{0,1}的异或字典树。最长异或路径给定一棵n \mathrm nn个点的带权树结点下标从1 \mathrm 11开始到n \mathrm nn。求树中所有异或路径的最大值。异或路径指的是树上两个结点之间唯一路径上的所有边权的异或值。解找到一条路径( X , Y ) \mathrm {(X,Y)}(X,Y)使得路径异或值最大而路径( X , Y ) \mathrm {(X,Y)}(X,Y)的异或值这其实等价于X \mathrm {X}X到L C A ( X , Y ) \mathrm {LCA(X,Y)}LCA(X,Y)的路径异或值异或值异或上Y \mathrm {Y}Y到L C A ( X , Y ) \mathrm {LCA(X,Y)}LCA(X,Y)的路径异或值。进一步地等价于X \mathrm {X}X到R o o t \mathrm {Root}Root的路径异或值异或上Y \mathrm YY到R o o t \mathrm {Root}Root的路径异或值。所以我们其实只需要预处理出每个点到R o o t \mathrm {Root}Root的路径异或值特别注意R o o t \mathrm {Root}Root到R o o t \mathrm {Root}Root自己的路径异或值是0 00。所以我们现在的问题就变成任选这n \mathrm nn个值n \mathrm nn个路径异或值中的两个使得二者的异或之和最大。把这n \mathrm nn个异或值用二进制方式存入字典树内不妨令所有异或值均具有32 \mathrm {32}32位我们从最高位开始存入字典树树高是32 \mathrm {32}32。将所有二进制存入字典树后我们要想最终异或的结果最大那么就要尽可能地让高位二进制位不同。枚举每个异或值作为答案之一另外一个异或值就需要贪心地从t i r e \mathrm {tire}tire树里面找。代码#includebits/stdc.husingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl\n#definePIIpairint,int#defineINF1e18constintN1e57;inttrie[32*N][3];intcnt1;voidadd(strings){intst1;for(inti0;is.size();i){if(!trie[st][s[i]-0]){trie[st][s[i]-0]cnt;}sttrie[st][s[i]-0];}}// 查找与给定字符串 s 异或后最大的字符串intquery(strings){intans0,st1,deep31;for(inti0;is.size();i){intfs[i]-0;if(trie[st][1^f]){ans(1lldeep);sttrie[st][1^f];}else{sttrie[st][f];}deep--;}returnans;}voidslove(){intn;cinn;vectorPIIg[n1];for(inti1;in-1;i){intu,v,w;cinuvw;g[u].emplace_back(v,w);}vectorintdp(n1,0);functionvoid(int,int)dfs[](intu,intfa){for(auto[v,w]:g[u]){if(vfa)continue;dp[v]dp[u]^w;dfs(v,u);}};dfs(1,0);intans0;for(inti1;in;i){string s;for(intj31;j0;j--){if(dp[i](1llj))s1;elses0;}add(s);}for(inti1;in;i){string s;for(intj31;j0;j--){if(dp[i](1llj))s1;elses0;}ansmax(ans,query(s));}coutansendl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();}