字典树

Jun 16, 2017 | 算法总结 | 阅读

应用

求解计数类问题
贪心问题如位运算（异或有奇效）
加速动态规划问题

题目

UVA 11488 Hyper Prefix Sets

题意
给定一个字符串集合 $S$，定义 $P(S)$ 为所有字符串的公共前缀长度与 $S$ 中字符串个数的乘积。给$n$ 个$01$串，从中选出一个集合 $S$，使得 $P(S)$ 最大。
数据
$ n \leq 50000$
题解
把字符串插入到 $01$ 字典树里，记录每个节点字符串的数量，遍历树同时更新最大值。
code

UVALive 3942 Remember the Word

题意
给出一个由 $S$ 个不同单词组成的字典和一个长度为 $L$ 的长字符串。问把该字符串分解为若干个单词连接，有多少种方案（mod $20071027$）。
数据
$L \leq 300000$, $1\leq S \leq 4000$, 单词长度不超过 $100$
题解
递推法：令 $d(i)$ 表示从 $i$ 开始的字符串的方案数，则 $d(i)=\sum{d(i+len(x))}$ | 单词 $x$ 是字符串 $[i,L]$ 的前缀。
如果依次枚举单词，时间无法承受。那么把单词放进Trie中，树上遍历时每经过一个单词结点，就能找到转移方程中的 $x$。
code

UVA 11732 “strcmp()” Anyone?

题意
输入 $n$ 个字符串，两两调用一次strcmp()，问字符比较的总次数（for循环内的比较也算）。
数据
$1 \leq n \leq 4000$，字符串长度不超过 $1000$，输入文件大小约为 $23$MB
题解
把所有字符串插入到一颗字典树里，记录每个节点字符的数量，那么再遍历一次字典树就可以把比较次数累加起来了。
因为数据量很大，使用左儿子-右兄弟的动态建树方法。
code

UVALive 5913 Dictionary Size

题意
给出 $n$ 个字符串组成的字典，现在要添加新的单词，从已有单词中选出非空前缀和非空后缀，组成新单词，问能组成多少个单词。
数据
$1 \leq n \leq 10000$
题解
建立一棵前缀树和一棵后缀树，有多少节点即为有多少个前缀。但是直接相乘并不是答案，考虑可能有重复的，比如”XAY”，可以由”X”和”AY”组成，也可以由”XA”和“Y”组成，一共计算了两次，所以要减去一次（注意字符串是单个字符的时候要特殊处理）。
code

UVALive 7192 Chip Factory

题意
从 $n$ 个数中选出不同的三个数$a、b、c$，使得 $(a+b)$ ^ $c$ 最大。
数据
$1 ≤ T ≤ 1000$，$3 ≤ n ≤ 1000$，$0 ≤ s_i ≤ 10^9$
There are at most $10$ testcases with $n > 100$
题解
先将所有数字按位插入到字典树上，然后删除两个数字，树上二分贪心询问与剩下的数字最大异或值。
code

HDOJ 5715 XOR游戏

题意
有一个长度为 $N$ 的数组，度度熊可以任意添加分割线，将数组划分为 $M$ 段，且每段长度小于等于 $L$。求所有分组内异或和的最小值的最大值。
数据
$1≤T≤300$，$1≤N≤10^4$，$1≤M≤10$，$1≤L≤N $，$1≤A_i≤10^9$
题解
显然答案满足二分性质，那么问题转化为判断值是否可行。
$dp[i][j]$ 表示前 $i$ 个数字分为 $j$ 组，且所有分组异或和最小值大于等于 $val$ 是否可行，$A_i$ 先转变为前缀异或和，假设当前判断的值为 $val$，那么状态转移方程为：$dp[i][j]$ |= ($dp[k][j-1]$ && $A_i$ ^ $A_k \geq val$)。时间复杂度：$O(TN^2M)$，显然无法承受。
注意到异或的特殊性，考虑生成M棵字典树，把所有 $dp[k][j-1]=true$ 的 $A_k$ 插入到第 $j-1$ 棵字典树里，当 $A_i$ 在第 $j-1$ 棵字典树使用上题的方法求得的最大异或和大于等于 $val$ 时，$dp[i][j]=true$，同时把 $A_i$ 插入到第 $j$ 棵树。
注意每棵字典树只保存前一个分组的信息，分组的长度也有限制，所以还需要动态删点。
code

数据结构