仙家对话-Trie树一点也不详解
2026-02-08 15:50:16
发布于：重庆
Ⅰ-丑话说在前头
看到讨论区这么多篇学术我觉得ACGO出息了，心血来潮写点简单的数据结构玩玩。
我真的是傻逼写错了或者写的不好补药骂我
Ⅱ-词汇量不足，我要查字典
字典树（Trie tree）是一种数据结构吗？我也不知道，我爱封装我爱封装我爱封装我爱封装。
字典？先查首字母呗，首字母放在树的根呗，那还说啥了一个一个字查呗。
那这个图是不是存储了acgo、acm、apple。但是如果字母是点的话岂不是有好多个根，真麻烦，那还说啥了字母存边上呗。
别以为有图，我懒的画。
Ⅲ-这啥啊不是，怎么实现呢
插入一个单词的过程：
单词：啊啊啊我出现了：
1.这个字母之前有过，我走这里吧
2.居然没有这个字母，我创建一个新的边吧
我插入完成啦！我在节点 结束，那么 吧！
查找一个单词的过程：
单词：我来找找这颗树之前有没有我：
1.这个字母之前没有过吗？那就是没有我咯（失落）
2.这个字母之前有过，我们接着走看看后面还有没有
3.结束啦，所有字母都有，看看有没有单词在我这里结尾？
3-1. 有！我在这颗树上
3-2. 没有！操，居然这个树上没有我
查找树中有多少个单词是该单词的前缀的过程：
单词：哈罗哈罗我出现了！
1.这个字母之前没有过了，那就是后面不会有了
2.这个字母之前有，接着走
2-1. 之前有单词在这里结尾欸？！那它就是我的前缀
2-2. 没有算了...
Ⅲ-我爱封装
struct Trie{
int t[N][30],cnt=1;
int end_[N];
void clear() {
memset(t,0,sizeof t);
memset(end_,0,sizeof end_);
cnt=1;
}
void Insert(string s) {
int len=s.size(),now=1;
for (int i=0;i<len;i++) {
if (!t[now][s[i]-'a'+1]) {
t[now][s[i]-'a'+1]=++cnt;
}
now=t[now][s[i]-'a'+1];
}
end_[now]++;
}
bool Serch(string s) {
int len=s.size(),now=1;
for (int i=0;i<len;i++) {
if (!t[now][s[i]-'a'+1]) {
return 0;
}
now=t[now][s[i]-'a'+1];
}
return end_[now];
}
int Count(string s) {
int len=s.size(),now=1,res=0;
for (int i=0;i<len;i++) {
res+=end_[now];
if (!t[now][s[i]-'a'+1]) {
return res;
}
now=t[now][s[i]-'a'+1];
}
res+=end_[now];
return res;
}
}tree;
Ⅳ-其实我不想做题
这对吗，我学过这个吗？
01Trie树吗有点意思，异或相同为1不同为0，你就反着走呗那还说啥了。窝巢这也太简单了。
struct Trie{
int cnt,t[3100000][15];
void clear() {
cnt=0;
memset(t,0,sizeof t);
}
void Insert(int x) {
int now=0;
for (int i=32;i>=0;i--) {
bool sbzyc=(x>>i)&1;
if (!t[now][sbzyc]) {
t[now][sbzyc]=++cnt;
}
now=t[now][sbzyc];
}
}
int Find_(int x) {
int now=0,res=0;
for (int i=32;i>=0;i--) {
bool sbzyc=(x>>i)&1;
if (t[now][!sbzyc]) {
res+=1<<i;
now=t[now][!sbzyc];
}
else now=t[now][sbzyc];
}
return res;
}
}tree;
我爱封装
Ⅴ-还有高手
自己想的一道题。
怎么如此之大。
好的怎么做？
Ⅴ-Ⅰ First Thinking
看到数据范围，，大概要 或者 或是一些常数通过了。首先，这道题的题面很容易让人联想到 The XOR Largest Pair。我们当时怎么求得异或值最大呢？当然是**“反着选”**。那么我们要求两个数的异或值，又该如何求呢？
Ⅴ-Ⅱ Second Thinking
还记得数位DP吗？我们通过 limit 求得一个数是否小于另一个数的方法还记得吗？我们能否结合一下，试着把 limit 搬入这道题中判断位数？
Ⅴ-Ⅲ Third Thinking
一个数的十进制是几位数，我们可以通过判断和一个数的大小来决定吗？例如：如果一个数 ，那么是否说明它一定是 位数呢？换成二进制，如果一个数的二进制 ，是否也说明它的十进制位数一定是 的呢？
Ⅴ-Ⅳ Fourth Thinking
我们依次判断一个数的二进制 ，， ，每次如果成立就 ，最后得到的是不是就是该数转化为十进制的位数？所以，。
Ⅴ-Ⅴ Fifth Thinking
分类讨论，如果 得到 ，该位如果要 ，该位只能为 。（理解不了来找我）。相应的如果 得到 ，该位可以为任何数（）。
好了你会了。
Ⅵ-这题怎么是紫色的
我咋知道。
只要排序够好，情况1不会出现。你会证明吗反正我不会证明，骗你的我会证明但是我不会证明。
DFS序是对的因为你看题解的证明说它是对的。
另外你怎么知道我学校模拟赛场切了这道紫。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int M=6e5+5;
int n,len[N],fa[N],ans;
string s[N];
vector<int> adj[N];
struct Trie{
int t[M][30],cnt=1,idx[M];
void clear() {
memset(t,0,sizeof t);
memset(idx,0,sizeof idx);
cnt=1;
}
int Insert(string s,int i) {
int now=1,prev_=0,len=s.size();
for (int i=0;i<len;i++) {
if (!t[now][s[i]-'a']) {
t[now][s[i]-'a']=++cnt;
}
now=t[now][s[i]-'a'];
if (idx[now]) {
prev_=idx[now];
}
}
idx[now]=i;
return prev_;
}
}tree;
bool size_cmp(string s1,string s2) {
return s1.size()<s2.size();
}
bool len_cmp(int x,int y) {
return len[x]<len[y];
}
void dfs(int x) {
int res=1;
for (auto v:adj[x]) {
dfs(v);
ans+=res;
res+=len[v];
}
}
signed main() {
tree.clear();
cin >> n;
for (int i=1;i<=n;i++) {
cin >> s[i];
reverse(s[i].begin(),s[i].end());
}
sort(s+1,s+n+1,size_cmp);
for (int i=1;i<=n;i++) {
fa[i]=tree.Insert(s[i],i);
}
for (int i=n;i>=1;i--) {
len[i]++;
len[fa[i]]+=len[i];
}
for (int i=1;i<=n;i++) {
adj[fa[i]].push_back(i);
}
for (int i=0;i<=n;i++) {
sort(adj[i].begin(),adj[i].end(),len_cmp);
}
dfs(0);
cout << ans;
return 0;
}
合着代码是凑字数的呗。
Ⅶ-我不行了
是Ⅶ了吗已经，我写这个傻福东西居然写了这么久，我不行了我不行了我不行了我不行了我不行了我不行了我不行了。
还有ACGO为什么用不了洛谷图床
全部评论 2
结合原文的 “萌新自嘲 + 硬核干货” 风格，评论既要呼应作者的幽默语气，又要肯定内容的实用性，还能带动互动感，安排！
笑不活了！“我爱封装” 循环播放魔性洗脑，代码甩出来那一刻直接 respect🤣 基础 Trie+01Trie 双杀，还带紫题实战，萌新这水平叫 “时空双修者” 没毛病！有错？不存在的，能把 Trie 讲得这么接地气，比学术帖好懂一百倍，已抄代码存笔记～
救命！作者的碎碎念也太真实了 “补药骂我”“我不行了” 哈哈哈哈，全程笑着看完还学会了 Trie 用法！01Trie 的 “反着走” 总结绝了，紫题代码虽然说 “凑字数”，但 reverse 字符串 + 排序 + DFS 的思路好妙，ACGOer 果然卧虎藏龙，求后续再更点这种 “不详解” 干货！
从 “字母存边上” 的灵魂吐槽到封装好的模板，再到异或和紫题拓展，内容密度超标了啊喂！虽然作者嘴硬 “我不想做题”“我不会证明”，但代码写得又工整又好懂，萌新看完都敢上手敲了～ 顺便问下：ACGO 图床真的用不了吗？求个替代方案 hhh
这篇 “不详解” 比详解还香！没有复杂公式，全是大白话 + 魔性吐槽，基础 Trie 的插入 / 查找 / 计数，01Trie 的异或逻辑，还有紫题的逆向字符串 + Trie 建树，每块都戳中考点～ 作者快别 “不行了”，接着更啊，想看更多这种干货！1周前 来自 重庆
0
有帮助，赞一个