字典树(Trie)的学习笔记
2024-10-02 20:59:08
按照一本通往下学，学到吐血了。。。
字典树模板题吗。
先讲讲字典树：
给出代码（太简单了。。。）！
#include<cstdio>
#include<cstring>
using namespace std;
struct trie
{
int a[10],v;
//a代表0~9的儿子的编号，有则为这个节点的编号，没有就是0。
//v是附加权值，代表每个节点被经过的次数。
}tr[200000];int trlen;//多少节点
char st[11000][20];int n;
void add(char ss[])
{
int len=strlen(ss+1),root=0;//root代表根节点
for(int i=1;i<=len;i++)
{
int k=ss[i]-'0';//计算是哪个儿子。。。
if(tr[root].a[k]==0)tr[root].a[k]=++trlen;//添加新节点
root=tr[root].a[k];tr[root].v++;//给这个节点加一次走过的标记
}
}
int find(char ss[])
{
int len=strlen(ss+1),root=0;//root代表根节点
for(int i=1;i<=len;i++)//找到这个字符串最底下的节点编号
{
int k=ss[i]-'0';
root=tr[root].a[k];
}
return tr[root].v-1;//被经过两次代表这个字符串是某个字符串的前缀。
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(tr,0,sizeof(tr));trlen=0;//初始化
scanf("%d",&n);
for(int i=1;i<=n;i++)//添加
{
scanf("%s",st[i]+1);
add(st[i]);
}
bool bk=false;
for(int i=1;i<=n;i++)
{
if(find(st[i]))//发现答案
{
bk=true;
printf("NO\n");//输出
break;
}
}
if(bk==false)printf("YES\n");//同样是输出。
}
return 0;
}
我们发现只要把每个数字转成31位二进制，然后，一个个插入字典树，在插入之前，我们计算一下当前的数与哪个数的异或值最大，并记录一下。
至于如何找，只需要，我们只需要每次走与当前二进制位数不一样的数字就行了，看代码还挺好理解的（find函数）
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int a[2],v;//v是附加权值，代表这个二进制数是多少
}tr[6100000];int trlen;
char st[40];
int n,ans;
void lintoto(int x)//将x转成二进制数
{
memset(st,0,sizeof(st));
int len=0;
while(x)
{
st[++len]=(x&1);//相当于x%2。
x>>=1;//除于2
}
}
void add(char ss[],int id)
{
int len=31,root=0;
for(int i=len;i>=1;i--)//由于当时存二进制是倒着存的，现在也要倒着搜
{
int k=ss[i];
if(!tr[root].a[k])tr[root].a[k]=++trlen;//新建节点
root=tr[root].a[k];
}
tr[root].v=id;//添加附加权值
}
inline int mymax(int x,int y){return x>y?x:y;}
inline int find(char ss[],int id)
{
int root=0,len=31;
for(int i=len;i>=1;i--)
{
int k=ss[i];
if(tr[root].a[k^1])root=tr[root].a[k^1];//走相反的地方
else root=tr[root].a[k];//不存在，走相同的地方。
}
return (tr[root].v^id);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
lintoto(x);//转成二进制
if(i!=1)ans=mymax(ans,find(st,x));//更新新的答案
add(st,x);//添加
}
printf("%d\n",ans);
return 0;
}
先证明异或符合交换律、结合律。
首先，异或的过程中：(1,0),(0,1),(0,0)都是消掉一个0，而(1,1)是消掉一个1。
我们可以发现，多次异或就是看所有数二进制的每一位的1的个数，奇数就为1，偶数为0，而你调换顺序的话，个数并没有变，所以满足交换律与结合律。
那么这道题，我们设\(sst_{i}=a_{1}⨁a_{2}⨁a_{3}⨁a_{4}...⨁a_{i}\)，那么，求区间最大，我们可以发现：
\(a_{l}⨁a_{l+1}⨁...⨁a_{r}=(a_{1}⨁a_{2}⨁a_{3}⨁...⨁a_{r})⨁(a_{1}⨁a_{2}⨁a_{3}⨁...⨁a_{l-1})=sst_{r}⨁sst_{l-1}\)
也就是说，我们只要求出在1~r-1区间内能异或\(sst_{r}\)的最大值，也就是上面那道题，设\(ll_{i}=\) 在1~i区间内的一个区间最大异或值，\(ll_{i}=max(ll_{i-1},以i为结尾的最大异或区间)\)。
再设一个\(rr_{i}=\) 在i~n区间内的一个区间最大异或值，\(rr_{i}=max(rr_{i+1},以i为开头的最大异或区间)\)。
求出最大的\(ll_{i-1}+rr_{i}\)
#include<cstdio>
#include<cstring>
using namespace std;
struct trie
{
int a[2],v;
}tr[9100000];int trlen;//字典树
char st[210];
int sst[410000],n,ll[410000],rr[410000],ans;//数组
void intto(int x)//像上次那样。。。
{
memset(st,0,sizeof(st));
int len=0;
while(x)
{
st[++len]=(x&1);//x%2
x>>=1;//x/=2
}
}
void add(char ss[],int id)//添加
{
int len=31,root=0;
for(int i=len;i>=1;i--)
{
int k=ss[i];
if(!tr[root].a[k])tr[root].a[k]=++trlen;
root=tr[root].a[k];
}
tr[root].v=id;
}
int find(char ss[],int id)//寻找
{
int len=31,root=0;
for(int i=len;i>=1;i--)
{
int k=ss[i];
if(tr[root].a[k^1])root=tr[root].a[k^1];
else root=tr[root].a[k];
}
return (tr[root].v^id);//返回异或值
}
inline int getsum(int x,int y){return sst[y]^sst[x-1];}//[x,y]区间的异或值
inline int mymax(int x,int y){return x>y?x:y;}//最大值
int main()
{
scanf("%d",&n);
intto(0);
add(st,0);//将0添加
for(int i=1;i<=n;i++)
{
scanf("%d",&sst[i]);sst[i]^=sst[i-1];
intto(sst[i]);//二进制
ll[i]=mymax(find(st,sst[i]),ll[i-1]);//更新
add(st,sst[i]);//添加
}
memset(tr,0,sizeof(tr));trlen=0;
intto(0);
add(st,0);
for(int i=n;i>=1;i--)
{
intto(getsum(i,n));
rr[i]=mymax(rr[i-1],find(st,getsum(i,n)));
add(st,getsum(i,n));
}//反着来一遍
for(int i=2;i<=n;i++)ans=mymax(ans,ll[i-1]+rr[i]);//统计答案
printf("%d\n",ans);
return 0;
}
跟例题一 一样。。。只不过处理方式出了点问题。
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
int a[10],v;
}tr[2100];int trlen;//字典树
char st[20];
void add(char ss[])//打得不能再顺手的添加。。。
{
int len=strlen(ss+1),root=0;
for(int i=1;i<=len;i++)
{
int k=ss[i]-'0';
if(!tr[root].a[k])tr[root].a[k]=++trlen;
root=tr[root].a[k];
}
tr[root].v=1;
}
bool find(char ss[])//每天都在变。。。
{
int len=strlen(ss+1),root=0;
for(int i=1;i<=len;i++)
{
int k=ss[i]-'0';
if(!tr[root].a[k])return false;//不存在节点？返回
root=tr[root].a[k];
if(tr[root].v==1)return true;//存在，返回
}
return false;
}
int main()
{
int T=0;
while(scanf("%s",st+1)!=EOF)
{
T++;
memset(tr,0,sizeof(tr));trlen=0;//初始化
bool bk=false;
while(1)
{
int len=strlen(st+1);
if(len==1 && st[1]=='9')break;//退出
if(find(st))bk=true;//寻找
add(st);//添加
scanf("%s",st+1);//输入
}
if(bk==true)printf("Set %d is not immediately decodable\n",T);
else printf("Set %d is immediately decodable\n",T);
}
return 0;
}
将字典建个字典树，然后类似递推思想瞎搞。。。
提示：建一个d数组代表这一段在前i位能否被表达。
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int a[26],v;
}tr[51000];int trlen;//字典树
char st[2100000];//字符串
int n,m;
char d[2100000];//d数组
void add(char ss[])
{
int len=strlen(st+1),root=0;
for(int i=1;i<=len;i++)
{
int k=st[i]-'a';
if(!tr[root].a[k])tr[root].a[k]=++trlen;
root=tr[root].a[k];
}
tr[root].v=1;
}
bool find(int l,int r)//匹配l~r区间
{
int root=0;
for(int i=l;i<=r;i++)
{
int k=st[i]-'a';
if(!tr[root].a[k])return false;
root=tr[root].a[k];
}
return tr[root].v;
}
inline int mymax(int x,int y){return x>y?x:y;}
int jie;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
add(st);
jie=mymax(jie,strlen(st+1));//最长的单词
}
for(int kkk=1;kkk<=m;kkk++)
{
memset(d,0,sizeof(d));d[0]=1;//初始化
scanf("%s",st+1);
int len=strlen(st+1);
for(int i=1;i<=len;i++)
{
for(int j=mymax(1,i-jie+1);j<=i;j++)
{
if(d[j-1]==1 && find(j,i))//如果前j-1位已经匹配成功，那么判断当前能否匹配成功
{
d[i]=1;
break;
}
}
}
int ans=0;
for(int i=len;i>=1;i--)//统计
{
if(d[i]==1)
{
ans=i;break;
}
}
printf("%d\n",ans);
}
return 0;
}
建立信息为字典树，两个附加权值，代表被经过的次数和作为结尾的次数。
那密码进行统计。。。
怎么统计自己想或看代码
#include<cstdio>
#include<cstring>
using namespace std;
struct trie
{
int a[2],v1,v2;//两个附加权值，v1代表被经过次数，v2代表被作为结尾的次数
}tr[610000];int trlen;//字典树
char st[510000];//字符串
int n,m;
void add(int len)//添加
{
int root=0;
for(int i=1;i<=len;i++)
{
int k=st[i];
if(!tr[root].a[k])tr[root].a[k]=++trlen;
root=tr[root].a[k];tr[root].v1++;//经过一次
}
tr[root].v2++;//作为结尾加一
}
int find(int len)
{
int root=0,ans=0;
for(int i=1;i<=len;i++)
{
int k=st[i];
if(!tr[root].a[k])return ans;
root=tr[root].a[k];ans+=tr[root].v2;//有多少是他的前缀
}
ans+=tr[root].v1-tr[root].v2;//他是多少字符串的后缀
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int len;scanf("%d",&len);
for(int j=1;j<=len;j++)scanf("%d",&st[j]);//输入字符串
add(len);//添加
}
for(int i=1;i<=m;i++)
{
int len;scanf("%d",&len);
for(int j=1;j<=len;j++)scanf("%d",&st[j]);//输入字符串
printf("%d\n",find(len));//寻找
}
return 0;
}
这道题目QAQ。
首先，我们知道，长度为s1的字符串a1，长度为s2的字符串a2，如果\(s1<s2\)并且a1与a2都是a3的后缀，那么a1是a2的后缀。
将所有字符串翻转，建一个字典树，然后建一颗树，当\(i\)->\(j\)仅当，\(a_{i}\)是\(a_{j}\)的最大前缀。
然后，DFS新树，每次进入没进过且节点最少的树就行了。
（如果直接在字典树上跑的话，子树大小会错乱，导致每次进的不是节点最小的树）
这道题还是有点难的，因为用到了一点贪心思想。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char st[520000];
int n;
bool bol[110000];
struct trie//字典树
{
int a[26],v;
}tr1[610000];int trlen1;
struct node//新建的树
{
int y,next;
}tr2[110000];int trlen2,last[110000],size[110000];//用边目录储存
void ins(int x,int y)//新建一条边
{
trlen2++;
tr2[trlen2].y=y;tr2[trlen2].next=last[x];last[x]=trlen2;
}
void add(int id)//添加
{
int root=0,len=strlen(st+1);
for(int i=len;i>=1;i--)//字符串翻转
{
int k=st[i]-'a';
if(!tr1[root].a[k])tr1[root].a[k]=++trlen1;
root=tr1[root].a[k];
}
tr1[root].v=id;
}
int dfss(int x,int fa)//遍历字典树，建新树，fa是离他最近的有权的祖先
{
int ans=0;//代表子树大小
for(int i=0;i<=25;i++)
{
if(tr1[x].a[i])
{
if(tr1[x].v)ans+=dfss(tr1[x].a[i],tr1[x].v);//本身是一个节点
else ans+=dfss(tr1[x].a[i],fa);//本身不是一个节点，只是一个中转站
}
}
if(tr1[x].v)//本身是一个节点
{
ins(fa,tr1[x].v);//连向父亲
ans++;size[tr1[x].v]=ans;//继承大小
}
return ans;//返回目前的子树大小
}
long long anss;
int times,lis[110000],listlen;
bool cmp(int x,int y){return size[x]<size[y];}
void dfs(int x)
{
int now=++times;
int l=listlen+1,r;
for(int k=last[x];k;k=tr2[k].next)lis[++listlen]=tr2[k].y;//处理list
r=listlen;
if(l<=r)sort(lis+l,lis+1+r,cmp);//排序是排[l,r)
else return ;//没有子树
for(int i=l;i<=r;i++)
{
anss+=(times+1)-now;//统计答案
dfs(lis[i]);//继续递归
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
add(i);
}//添加所有字符串
dfss(0,0);//建树
dfs(0);//处理答案
printf("%lld\n",anss);//输出
return 0;
}
这道题，我一开始想得太复杂了。。。
我一开始想到的是一条路径上，起点是l，终点是r，然后还涉及到求LCA，然后就十分复杂。。。
然后膜了一波题解，发现自己就是个弱智。。。
设\(sum[i]=(1->i)\)的权值异或值 ，那么一条路径上的异或权值和就是\(sum[l]\)^\(sum[j]\)，然后就是求一个数组中求与\(sum[i]\)异或值最大的数，其实就是例题了，根本不用在树上进行特别麻烦的遍历，或者是过程很麻烦的树上递归，是不是很巧妙？好吧，我承认就是我没有想到然后就乱膜。。。
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int y,next,c;
}a[210000];int last[110000],alen;
int sum[110000];//边目录
void ins(int x,int y,int c)
{
alen++;
a[alen].y=y;a[alen].c=c;a[alen].next=last[x];last[x]=alen;
}
void dfs(int x,int fa)
{
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa)//不是他的父亲
{
sum[y]=sum[x]^a[k].c;//处理sum数组
dfs(y,x);//继续递归
}
}
}
struct trie
{
int a[2],v;
}tr[4100000];int trlen;//字典树
char st[40];//储存二进制的数组。
void intoo(int x)
{
memset(st,0,sizeof(st));//初始化
int len=0;
while(x)
{
st[++len]=(x&1);//x%2
x>>=1;//x/=2
}
}
void add(int id)//添加
{
int len=31,root=0;
for(int i=len;i>=1;i--)//添加二进制要注意的
{
int k=st[i];
if(!tr[root].a[k])tr[root].a[k]=++trlen;
root=tr[root].a[k];
}
tr[root].v=id;
}
int find(int id)
{
if(trlen==0)return 0;//判断目前字典树是否有节点
int len=31,root=0;
for(int i=len;i>=1;i--)
{
int k=st[i];
if(tr[root].a[k^1])root=tr[root].a[k^1];//贪心找异或值最大
else root=tr[root].a[k];
}
return (id^tr[root].v);//给出结果
}
int n;
inline int mymax(int x,int y){return x>y?x:y;}//找最大值
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
dfs(1,0);//默认1为根，处理sum数组
int ans=0;
for(int i=1;i<=n;i++)//例题的做法
{
intoo(sum[i]);
ans=mymax(ans,find(sum[i]));
add(sum[i]);
}
printf("%d\n",ans);
return 0;
}
终于写完了。。。
最新文章
- vim编辑器的使用
- Android数据存储-通过SharedPreferences实现记住密码的操作
- Visual Studio 如何恢复默认设置
- [UML]UML系列——状态机图statechart diagram
- Linux 读书笔记 一
- <转载>NPOI Excel 单元格背景颜色对照表
- Java的内存回收机制
- hihoCoder #1033 : 交错和 （数位Dp）
- Haproxy安装及配置(转)
- POJ 1503 Integer Inquiry(大数相加，java)
- ActiveMQ之消息指针
- WCF编程系列(三)地址与绑定
- NSDate与 NSString 、long long类型的相互转化
- 玩转Web之servlet（二）---servlet常见错误
- spring 注入使用注解（不用xml）
- 【Java学习笔记之一】java关键字及作用
- eclipse报错排解
- C++框架_之Qt的窗口部件系统的详解-上
- Python--day02（编程语言、运行python代码、变量）
- 【Rails App】 应用服务器从Passenger切换为Puma, Grape出现线程安全问题