日记

值得记录的也就两题。

Neo’s Escape# Link to

我们发现，一个克隆体一次会按掉一个区间内的所有按钮。那么就直接 dp。设 $dp_i$ 为把 $[1,i]$ 这个区间内的所有按钮的都按完的最小克隆体数量。

转移十分的好写：$dp_{i} = \min\{dp_{j - 1} + 1\}$，但是 $[j,i]$ 一定要是一个克隆体能够全按完的。可以证明 $[j,i]$ 能被一次性按完，当且仅当 $[j,i]$ 形如：$a_j \le a_{j + 1} \le a_{j + 2} \le \dots \le a_{k - 1} \le a_k \ge a_{k + 1} \ge \dots \ge a_{i - 2} \ge a_{i - 1} \ge a_i$。

这么看，似乎连 $O(n^2)$ 暴力都不好写的，但是我们拥有 DS 之力，我们可以维护 $lft_i$ 满足 $[lft_i,i]$ 这段区间单调不降，再维护一个 $rht_i$ 满足 $[i,rht_i]$ 这段区间单调不增。感性理解：$dp$ 一定是单调不降的，于是我们的 $j$ 肯定最小越好。我们发现对于每个 $i$，$[lft_i,rht_i]$ 的每个子区间肯定都是合法的，那么 $[lft_i,rht_i]$ 转移的最优决策点肯定都不会在 $lft_i$ 右边。我们直接用线段树维护区间取 $\min$，单点查询。

Censoring G# Link to

既然出现在了 AC 自动机的题单里，我们肯定就要用 AC 自动机嘛。

对于文本串的匹配，我们用一个栈记录一路走来的 $rt$，和 $ans$ 记录答案。如果匹配到的这个点，是一个模式串 $s$ 的结尾，栈和 $ans$ 都 pop $|s|$ 次。然后 $rt$ 变成新的栈顶，继续匹配。

后日谈 # Link to 后日谈

正式因为配不上她，所以我才在努力变强啊。

有奖竞猜：“她”代指谁？

5 月 4 日 # Link to 5 月 4 日

时间不多了。

T1 # Link to T1

明天再问问。

一定记得哦！

T2 # Link to T2

AC 自动机 dp。

我们设 $dp_i$ 表示匹配前 $i$ 个字符的方案数。我们在 AC 自动机上走到的 $rt$，我们暴力跳 $fail$，如果跳到哪个节点是一个模式串的结尾，那么就说明该转移了。设这个模式串的长度为 $len$，那么显然的转移是 $dp_i$ 加上 $dp_{i - len}$。

考虑如何优化。因为只有模式串的结尾的那几个节点对转移有用。我们对于每个节点记录一个 $lst$ 表示跳 $fail$ 能跳到的第一个节点使得它是某个模式串的结尾。每次直接跳 $lst$ 就行。时间复杂度 $O(n\sqrt{n})$。

T3 # Link to T3

原题。但是需要一些奇技淫巧。

分两种情况考虑。

如果有集合的交集是 $\varnothing$，那么肯定只有一个。因为如果有多个，那么肯定可以合并。那么我们把所有的线段按照长度从大到小排序，取前 $k - 1$ 的就行。
那有人要问了：如果剩下的有交集怎么办？没事，dp 会出手。

剩下的是没有交集为 $\varnothing$ 的情况。
我们把所有的线段按照左端点排序。但是我们发现，排序完了依然不好做。究其原因是有线段包含了别的线段。我们考虑这些“包含了别的线段的线段”。如果它和它所包含的线段出现在了一个集合内，那么肯定不会影响到这个集合的答案。反之它肯定是单独成一个集合。因为如果它和别的线段一起，只可能使答案减少。

我们把“包含了别的线段的线段”的踢出去，那么剩下的肯定是左右端点都单调递增的线段。由于这样我们取一个集合只会取一个区间，于是我们 dp：设 $dp_{i,j}$ 为前 $i$ 个集合用了 $j$ 条线段。转移就是枚举 $[k,j]$ 当作最后的一个集合，然后转移。前缀和优化。

但是我们发现这玩意是 $O(nk)$ 的，无法通过。考虑 奇技淫巧。如果 $nk > 5 \times 10^7$，也就是 $O(nk)$ 跑不过，我们就不跑 dp，跑完上面的贪心就输出。能过就对了。

T4 # Link to T4

没改。

文本生成器# Link to

正难则反。

考虑如何求不可读的方案数。建出 AC 自动机，然后对于每个节点记录一个 $fl$ 表示它或者它在 $fail$ 树上的祖先是否有某个是一个模式串的结尾。然后 $dp_{i,rt}$ 表示当前已经有了 $i$ 个字符，在 $rt$ 节点上。枚举 $rt$ 在字典树上的每个儿子 $v$，如果 $v$ 的 $fl$ 不为 $1$，那么就可以转移，否则不行。答案就是 $26^m - \sum\limits_{i = 0}^{cnt}dp_{m,i}$。

Video Game G# Link to

我连最基础的 dp 都做不出来了？完蛋了

设 $dp_{i,rt}$ 表示已经匹配了 $i$ 个字符，当前在 $rt$ 节点上。对于每个节点记录一个 $sum$ 表示这个节点是几个模式串的结尾。如果我想转移到 $v$，那么我们就得从 $v$ 往上跳 $fail$，记录从 $v \to 0$ 路径上的所有点的 $sum$ 之和为 $tmp$，转移就是 $dp_{i + 1,v}$ 对众多 $dp_{i,rt} + tmp$ 取 $\max$。可以优化。

后日谈 # Link to 后日谈

唯有自救。