- 顾名思义，trie树是由字典与树的结合体，是一种方便快捷地存储字符串等字符集较小的串集的数据结构（不确定算不算数据结构）
而其结构是朴素的。trie树的节点本身并没有特殊的含义，其信息更多体现在边上。如下图
- 这是一颗典型的trie树。
例如我们要表示aba这个字符串，我们就从1->2->6->11，将每条边所代表的字符连接起来就是我们所代表的字符串。
P2580 于是他错误的点名开始了
这道题是trie的模板题。
-
题意：给定原字符串集合(大小为 \(n\) )和一些字符串询问(大小为 \(m\) )。
对于每个询问，我们需要求出询问的字符串是否在字符集给定的字符集内。若在，还需判断是否已经被询问过。
对于每个给定的字符串，其长度 \(len\) 都小于等于50且 \(n\le 1e4,m\le 1e5\) -
由于数据规模并不很小，因此不能 \(O(nmlen)\) 地去暴力对比。因此考虑构建trie树。
对于先前给定的字符集构建trie树后对于每个询问，就直接向下跑寻找有没有就可以了。 -
但是需要注意，构建trie树后需要给节点设定终止标记。因为有些节点可能只是某个字符串的中间并不是结尾。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,tree[3000005][30],cnt[3000005],id=0,m,tr[3000005];
int getnum(char s)
{
return s-'a'+1;
}
void insert(string s)
{
int p=0,len=s.size();
for(int i=0;i<len;i++)
{
int c=getnum(s[i]);
if(!tree[p][c]) tree[p][c]=++id;
p=tree[p][c];
}
tr[p]=1;
return;
}
int find(string s)
{
int p=0,len=s.size();
for(int i=0;i<len;i++)
{
int c=getnum(s[i]);
if(!tree[p][c]) return -1;
p=tree[p][c];
}
if(!tr[p]) return -1;//末尾标记
cnt[p]++;
if(cnt[p]==1) return 1;
else return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
insert(s);
}
cin>>m;
for(int i=1;i<=m;i++)
{
string s;
cin>>s;
int res=find(s);
if(res==1) cout<<"OK"<<endl;
if(res==0) cout<<"REPEAT"<<endl;
if(res==-1) cout<<"WRONG"<<endl;
}
return 0;
}
P4551 最长异或路径
-
题意：给定一颗有 \(n\) 个节点的无根树，每条边有权值。寻找树上的两个节点，使其之间的异或路径最长（指两点间路径上所有边的异或和）
-
对于每一对节点，显然有 \((u,v)=(root,u)\oplus (root,v)\)，这里的括号是指 \(u\) 到 \(v\) 的异或路径。
因此考虑先求出每个点到根节点（自己随便定一个，一般就是1）的异或路径的值。现在考虑枚举每一个点，求出与其匹配的最优的另一个点的异或路径长度。 -
事实上，我们并不关心另一个点在哪里，我们只需要求出最优的异或路径是多少就可以了。
又发现了一个性质：对于两个值，其异或后的值如果要大，那一定是最高位优先。也就是说，如果异或后的值一种最高位大，另一种最高位不大，那第二种一定不优（注意都是在二进制下讨论的） -
因此考虑对于每个 \((root,u)\) 的二进制值建立trie树，对于每个枚举的 \((root,u)\) 值，从高到低位枚举，如果这一位有与其相反的数，那就向这边走。
根据上文的叙述，这种贪心的正确性显然。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e7+7;
int n,tot[N],sum[N],cnt=0;
struct bian
{
int v,w;
};vector <bian> q[N];
struct node
{
int son[3];
}tr[N];
void dfs(int u,int fa)
{
for(int i=0;i<tot[u];i++)
{
int v=q[u][i].v,w=q[u][i].w;if(v==fa) continue;
sum[v]=sum[u]^w;dfs(v,u);
}
}
void build(int val,int x)
{
for(int i=(1<<30);i;i>>=1)
{
bool c=val&i;
if(!tr[x].son[c]) tr[x].son[c]=++cnt;
x=tr[x].son[c];
}
}
int query(int val,int x)
{
int res=0;
for(int i=(1<<30);i;i>>=1)
{
int c=val&i;
if(tr[x].son[!c]) res=res+i,x=tr[x].son[!c];
else x=tr[x].son[c];
}
return res;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,u,v,w;i<=n-1;i++)
{
cin>>u>>v>>w;
q[u].push_back({v,w}),tot[u]++;
q[v].push_back({u,w}),tot[v]++;
}
dfs(1,0);for(int i=1;i<=n;i++) build(sum[i],0);
int ans=0;for(int i=1;i<=n;i++) ans=max(ans,query(sum[i],0));
cout<<ans<<'\n';return 0;
}