夢に僕らで帆を張って
来るべき日のために夜を超え

标签 字典树 下的文章

October 31, 2019

洛谷P3966/TJOI2013 单词

题意给出$n$个单词,求每个单词共出现几次数据范围:单词总长度$\le 10^6$题解多模匹配,使用$\text{AC}$自动机解决需要注意的是,可能出现重复的单词;为避免字典树的值被覆盖,只记录第一个编号,而将其他相同的单词指向这个编号统计答案时,在该前缀的所有后缀上($\text{Fail}$树上的祖先节点上),将其自身答案累加上去,就是总共出现的次数代码:#include<ios...
October 31, 2019

洛谷P4551 最长异或路径

题意给出一棵$n$个点的带权树,求最长异或路径数据范围:$1 \le n \le 100000,1 \le w < 2^{31}$题解由于$\text{xor}$是自己的逆运算,因此可以得到一个结论:树上任意$1$条路径可由$2$条从根节点出发的路径$\text{xor}$得来假设以$1$为根节点,先$\text{dfs}$对于每个点求出到$1$节点的路径其次,求解$\text{xor...
September 29, 2019

CometOJ3978 天天背单词prefix

题意求总共$n$个单词中$k$个单词连成的字符串在所有可能的字符串中从小到大排序后的排名数据范围: 单词总长度$\le 10^6$,输入文件大小小于$2MB$题解因为数据保证不存在某个单词是另一个单词的前缀,所以直接对输入的单词进行排序,将其转化为数字那么输入的字符串自然是$1 \dots n$的数字中$k$个数字的排列,问题转化为计算这个排列的排名,例如样例5 3 a b c d e ca...