wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共3篇）

bzoj2553 禁忌

题目链接题意给出一个\(n\)个字符串的字典。对于一个字符串，他的贡献是这个字符串中最多的在字典中出现的不重叠子串的数量。然后问一个长度为\(len\)的，字符集为前\(alphabet\)个字符的字符串的贡献期望是多少。思路首先想如果这个长度为\(len\)的字符串已经给出了。应...

AC自动机

2019-01-31

0 688

bzoj2434 阿狸的打字机

题目链接思路可以发现，其实题目中所描述的操作，就是在\(AC\)自动机上走的过程。输出就是打上标记。删除就是返回父亲节点。然后看询问。每次询问字符串\(x\)在字符串中\(y\)出现的次数。其实也就是问在\(AC\)自动机上的\(y\)这个字符串上，有多少位置的\(fail\)指针指向\(...

树状数组 AC自动机

2019-02-01

1 530

bzoj1030 文本生成器

题目链接题意给出\(n\)个字符串，要构造一个长度为\(m\)的字符串\(S\)，使得给出的\(n\)个字符串中至少有一个是\(S\)的子串。问方案数。思路 \(AC\)自动机+\(DP\) 考虑至少有一个是S的子串不好考虑。考虑用全部情况减去其中不包含任何一个字符串的情况。全部情况...

AC自动机动态规划dp

2019-02-01

0 564