Trie,又名字典树,顾名思义是一个用于存放字符串的树,他逻辑结构上是一棵树,而不是线性表
线性表存放字符串限制了字符之间的关系,仅仅只能前后相邻,因此一般一个一维表只用于存放一个串
而树就突破了这一限制,其字符之间关系变成了“父-子”,所以一棵Trie可以存放多个串
在 Trie 中,我们认为一个结点是一个字符串/状态,由从根到自身的所有边的字符构成
结点 并非 字符,边 才是 字符,结点可以理解为 状态 ,或 字符串
因此不难看出:任意两个结点的 LCA(最近公共祖先)表示两个结点的最长相等前缀
正如上述例子,借用树的性质,我们可以对 Trie 延伸出很多的结论和性质,今后会一一介绍
Trie的板子:
次板子可以修改成直接支持插入和删除的功能(言外之意,Trie 有时可以不需要刻意上可持久化)
struct Trie
{
// 假设字符串由小写字母构成
int trie[SIZE][26], tot = 0;
int end[SIZE]; //该节点结尾的字符串是否存在
// Trie的插入
void insert(char* str)
{
int len = strlen(str), p = 1;
for (int k = 0; k < len; k ++ )
{
int ch = str[k] - 'a';
if (trie[p][ch] == 0) trie[p][ch] = ++ tot;
p = trie[p][ch];
}
end[p] = true;
}
// Trie的检索
bool search(char* str)
{
int len = strlen(str), p = 1;
for (int k = 0; k < len; k ++ )
{
p = trie[p][str[k] - 'a'];
if (p == 0) return false;
}
return end[p];
}
} trie;
0
,把它变成 1
,然后这个位置后面的 1
都变成 0
即可给定
个字符串
,接下来进行
次询问,每次询问给定一个字符串
,求
中有多少个字符串是
的前缀。
输入字符串的总长度不超过
,仅包含小写字母。
输入格式
第一行输入两个整数
。
接下来
行每行输入一个字符串
。
接下来
行每行一个字符串
用以询问。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
输入样例:
3 2
ab
bc
abc
abc
efg
输出样例:
2
0
字典树的板子题,在查找时,顺便统计一下前缀中的字符串
int search(char *str)
{
int res = 0;
int p = 0, n = strlen(str);
for (int i = 0; i < n; i ++ )
{
int ch = str[i] - 'a';
if (!trie[p][ch]) return res;
p = trie[p][ch];
res += end[p];
}
return res;
}
在给定的
个整数
中选出两个进行 xor
(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数
。
第二行输入
个整数
。
输出格式
输出一个整数表示答案。
数据范围
输入样例:
3
1 2 3
输出样例:
3
注意,启发式策略下,我们希望异或对尽可能大,那么就是让高位尽可能不同
因此存储该字符串时,我们希望从高位往低位存储,这样查询时,在高位尽可能错开就错开
void insert(int num)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int ch = num >> i & 1;
if (trie[p][ch] == 0) trie[p][ch] = ++ tot;
p = trie[p][ch];
}
}
int query(int num)
{
int res = 0, p = 0;
for (int i = 30; i >= 0; i -- )
{
int ch = num >> i & 1;
if (trie[p][!ch] == 0) p = trie[p][ch];
else
{
res += 1 << i;
p = trie[p][!ch];
}
}
return res;
}
给定一个树,树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或和:
⊕ 为异或符号。
给定上述的具有
个节点的树,你能找到异或长度最大的路径吗?
输入格式
第一行包含整数
,表示树的节点数目。
接下来
行,每行包括三个整数
,表示节点
和节点
之间有一条边权重为
。
输出格式
输出一个整数,表示异或长度最大的路径的最大异或和。
数据范围
输入样例:
4
0 1 3
1 2 4
1 3 6
输出样例:
7
样例解释
样例中最长异或值路径应为 0->1->2
,值为
本题解法非常的秒,用到了异或的性质:
因此,求树上任意两点的异或路径长度 等价于 求他们各自到根节点的异或路径长度的异或值
证明如下,分类讨论即可:
第一种情况:根节点在两个点的路径之上
那么两点的异或路径长度就是各自到根节点的异或路劲长度的异或值
第二种情况:根节点不在两个点的路径之上
则任意一个点到根节点的路径都是先到两点的 LCA,再从 LCA 出发到达根节点
而从 LCA 出发到根节点的这段路径有两条,异或运算具有交换律,因此易得该段异或值为
下面给出数学证明,写出两个点各自到根节点的异或路径长:
两者取异或可得:
得证
因此原问题就等价于:求所有点到根节点的异或路径中,选出两条,使得两者异或值最大
就是 Trie 的板子了
struct Trie
{
int trie[SIZE][2], tot;
void insert(int num)
{
int p = 0;
for (int i = 30; ~i; i -- )
{
int ch = num >> i & 1;
if (!trie[p][ch]) trie[p][ch] = ++ tot;
p = trie[p][ch];
}
}
int query(int num)
{
int res = 0, p = 0;
for (int i = 30; ~i; i -- )
{
int ch = num >> i & 1;
if (!trie[p][!ch]) p = trie[p][ch];
else
{
res += 1 << i;
p = trie[p][!ch];
}
}
return res;
}
}trie;
int dist[N];
void dfs(int u, int xor_len, int fa)
{
dist[u] = xor_len;
for (int i = head[u]; i; i = nxt[i])
{
if (ver[i] == fa) continue;
dfs(ver[i], xor_len ^ edge[i], u);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a + 1, b + 1, c), add(b + 1, a + 1, c);
}
dfs(1, 0, 0);
int res = 0;
for (int i = 1; i <= n; i ++ )
{
int val = dist[i];
res = max(res, trie.query(val));
trie.insert(val);
}
printf("%d\n", res);
return 0;
}