AtCoder Regular Contest 077 简要题解
比赛地址pushpush双端队列模拟即可。代码11显然有恰好一个数出现了 $2$ 次，设其出现的两个位置为 $l,r(l<r)$。考虑容斥。长度为 $k$ 的子序列数显然为 ${n+1\choose k}$，但其中有重复的。冷静分析一下可以发现，重复的一定是在 $l-1+(n+1-r)$ 个元素中选了 $k-1$ 个，和某个重复的数组成了子序列。所以答案为 ${n+1\choose k...
标签 KMP 下的文章
- 首页
- KMP
洛谷5770 [JSOI2016]无界单词
Luogu分析容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$，如果 $...
洛谷3193 [HNOI2008]GT考试
LuoguBZOJ分析考虑一个 naive 的 DP。设 $f_{i,j}$ 表示前 $i$ 位匹配到不吉利数的第 $j$ 位的方案数。设 $g_{i,j}$ 表示在匹配到第 $i$ 位时加一个字符会匹配到第 $j$ 位的方案数，那么考虑如何求出 $g$。枚举每一位以及后面加的字符，然后爆跳 nxt 即可找到加字符后转移到的位置。然后注意到上面的 DP 式像矩阵乘法的形式，直接矩阵快速幂即可...
ARC060F 最良表現 / Best Representation
AtCoderLuogu分析首先你要知道怎么求一个字符串的循环节。事实上跑 KMP ，然后 $len-nxt[len]$ 就是它的循环节长度了。当然你要判一下这个是不是 $len$ 的约数，不是就没有循环节。那么这题就比较简单了。首先 $m$ 显然只有 $3$ 种取值：$1,2,|w|$ 。然后可以发现，当且仅当循环节长度为 $1$ 时 $m$ 取 $|w|$ ，当且仅当不存在循环节时 $m...
UVA12387 Alphabet Soup
UVaLuoguVjudge分析考虑 Polya 定理。容易得到一个置换的循环个数是 $\gcd(k,P)$ 。于是我们只需要找出所有置换即可。可以使用 KMP 。把原数组倍长，然后求差分数组。于是直接拿原差分数组匹配，能够匹配上的位置就对应着一个置换。代码// =================================== // author: M_sea // websi...
洛谷4548 [CTSC2006]歌唱王国
Luogu分析听了 laofu 的讲课并看了 ymd 的论文后做了这题。以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。分析一下...
洛谷3435 [POI2006]OKR-Periods of Words
LuoguBZOJ分析$\mathrm{KMP}$+阅读理解首先翻译一下题目：如果存在串 $B$ （ $B$ 可以为空） ，使得 $A=PB$ ，那么称 $P$ 是 $A$ 的前缀。如果 $A\neq P$ 并且 $P$ 是 $A$ 的前缀，那么称 $P$ 是 $A$ 的 $\mathrm{proper}$ 前缀。如果 $Q$ 是 $A$ 的 $\mathrm{proper}$ 前缀，并且...
洛谷2375 [NOI2014]动物园
LuoguBZOJ分析$\mathrm{KMP}$ 。首先求出 $nxt$ ，然后考虑怎么求 $num$ 。发现 $num$ 的不重叠的限制似乎不太好搞，于是考虑先求出一个没有这个限制的数组 $tmp$ 。发现对于一个前缀 $i$ ，满足既是它的前缀又是它的后缀的串是 $nxt[i]$ 、 $nxt[nxt[i]]$ 、...那么在求 $nxt$ 的时候顺便把 $tmp$ 求出来就行了。具体...
洛谷3426 [POI2005]SZA-Template
Luogu分析$\mathrm{KMP+DP}$ 。先把 $nxt$ 求出来，考虑怎么 $\mathrm{DP}$ 。设 $f[i]$ 表示前缀 $i$ 的答案。显然 $f[i]$ 只能取 $i$ 或 $nxt[i]$ 。进一步发现， $f[i]$ 取 $nxt[i]$ 仅当存在一个 $j$ ，满足 $f[j]=f[nxt[i]]$ 且 $i-nxt[i]\leq j$ 。实际上不用每次循环...