CF163E e-Government
CodeforcesLuogu分析建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。代码// ==...
标签 AC 自动机 下的文章
- 首页
- AC 自动机
CF547E Mike and Friends
CodeforcesLuogu分析考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。代码// =================================== // au...
洛谷2414 [NOI2011]阿狸的打字机
Luogu分析做完这题感觉对 AC 自动机有了新的理解...注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀（这里建议想一想 fail 的定义），因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串，于是我们只需要把 $Y$ 的前缀...
洛谷5319 [BJOI2019]奥术神杖
LuoguBZOJ分析0/1分数规划+AC自动机+DP。设 $ans=\sqrt[n]{\prod\limits_{i=1}^na_i}$ 。那么有 $\ln ans=\frac{1}{n}\sum\limits_{i=1}^{n}\ln a_i$ 。发现这是一个分数规划的形式。二分答案 $mid$ ，假设右边大于 $mid$ ，可以化为 $\sum\limits_{i=1}^n(\ln ...
洛谷3041 视频游戏的连击Video Game Combos
Luogu分析$\mathrm{AC}$ 自动机+ $\mathrm{DP}$ 。把所有串丢到 $\mathrm{AC}$ 自动机里面去，然后设 $f[i][j]$ 表示前 $i$ 个字符，匹配到了第 $j$ 个节点，直接转移即可。注意一开始要置 $-\infty$ ，边界是 $f[i][0]=0$ ，答案是 $\max\limits_{i=1}^{tot}f[k][i]$ 。代码//It ...
洛谷3966 [TJOI2013]单词
LuoguBZOJ分析注意到 fail 树中某个节点的子树中的节点都以该节点作为一个后缀。因此对于每个单词，把 trie 上它到根路径上的所有点权值加 $1$ ，然后统计 fail 树中权值和就好了。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib...
洛谷2444 [POI2000]病毒
LuoguBZOJ分析多个字符串，考虑$\texttt{AC自动机}$。先建出$\texttt{AC自动机}$，考虑一下如果有一个无限长的串会发生什么。发现，如果有的话，会存在一条无限长的不经过任何病毒代码段的结尾的路径。也就是说成环了。于是$\texttt{dfs}$判一下就行了。代码//It is made by M_sea #include <algorithm> #inc...
洛谷4052 [JSOI2007]文本生成器
LuoguBZOJ分析比较套路了。总的单词个数是$26^m$，减去不可读的就是可读的。不可读的应该很容易求。建出AC自动机，然后在上面跑DP即可。可以参照数数那题，不过没有上界限制还要更简单一点。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib&g...
洛谷3311 [SDOI2014]数数
LuoguBZOJ分析好像和GT考试那题差不多。设$f[i][j][0/1]$表示前$i$位，在AC自动机上匹配到了第$j$个节点，是否到了$n$的上界的方案数。然后分情况转移。若前一位和这一位都没有到上界：$\large f[i-1][p][0]\to f[i][ch[p][0\sim9]][0]$若前一位到了上界，这一位没有到上界：$\large f[i-1][p][1]\to f[i]...