A考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀,最后一次删除的串长度为 $2/3$ 的方案数。转移就判断一下两次长度相等是否子串相等即可。B这种最长的最短路链问题贪心超过两步都是错的。首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路,注意到贪心一步是正确的,我们去枚举 $b,c$,预处理最远,次远,第三远的点即可(因为路径不...
题目链接题目描述题目大意:给你前 $alphabet$ 个小写字母组成的字符集,以及 $n$ 个单词,定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$,其中 $Taboo[i]$ 是第 $i$ 个单词(禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数)。现在给定一个长度 $len$,求随机一个用字符集生成的长度为 $len$ 的...
定义首先简要介绍一下 AC 自动机:Aho-Corasick automation,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂 AC 自动机,先得有模式树(字典树)Trie 和 KMP 模式匹配算法的基础知识。KMP 算法是单模式串的字符匹配算法,AC自动机是多...