2021-11-13 Test

感觉这场比赛还是存在很多问题的，比如说 T2，T3 完全没有认真思考而是武断地将其规约到我不会的知识点然后摆烂，并且死磕人类智慧的 T4

# Solutions:

# A

考试的时候想到的两条结论：

• 选择多的放在统一生产线上并不优秀，所以贪心地把大区间独立为生产线。

• 若要选择一些在同一生产线上一定会选择按左端点排序后相邻的一段。

然后结合一些这些结论，假如说有一个区间 $A$ 完全包含了区间 $B$ ，那对答案贡献 / 限制的部分都是 $B$ ，而 $A$ 是不会限制的（要求选择的方案与 $B$ 有交一定与 $A$ 有交，且交的部分一定是 $B$）。所以你可以直接把 $A$ 区间删掉，现在你留下了一些两两互不包含的区间，而我们又知道选择的状况一定是连续段，于是直接 $O(n^3)Dp$ 计算出把这些区间分为任意个生产线上的答案，再把多的区间贪心分配给包含区间中长度最长的若干个即可。

# B

考虑正难则反，既然满足题意的方案数是个复杂的计数问题我们就可以把问题转化为长度为 $m$ 的 $01$ 串总数减去不符合题意的 $01$ 串数。

考虑计算不符合题意的 $01$ 串长什么样，也就是这些串中不包含把符合题意要求的子串–也就是那与给出文本串差距小于一个字符的 $n+1$ 个串。

这是一个多模匹配的问题，我们把这 $n+1$ 个串放在 $AC$ 自动机上，要求就是不能匹配到终止节点，我们设 $dp_{i,j}$ 表示构造到了第 $i$ 个字符，在自动姬上匹配到了 $j$ 的 不合题意的子串数 ，转移为：

$$dp_{i,j}=\sum dp_{i - 1, k}$$

其中 $k$ 为能转移到 $j$ 的一个状态且不为终止状态。

# C

首先是看错题了，以为是区间本质不同回文子串，然后自然想到什么 SAM 上的奇怪东西，然后就 GG 了。
区间本质不同回文子序列，看着没有什么思路吗，为什么会想到区间 $dp$ ?

• 信息可以合并，比方说你知道一个子序列是回文的，那在它两边加上一个相同的字符仍为回文串。

• 是个计数问题，并不关心具体是那些子序列，故信息的合并较为便捷。

那考虑区间 $dp$ ，经过以上分析，我们最朴素的 $dp$ 方程不难得出：

主体思想是枚举最外侧两个相同字符，设 $L_{i,j}$ 表示在 $i$ 位置左侧第一个颜色为 $j$ 的位置 $k$ , 类似地设 $R_{i,j}$.

方程即为：

$$dp_{l,r} = [ R_{l,col}\le L_{r,col} ] + [ R_{l,col}< L_{r,col} ] + \sum_{col} dp_{R_{l, col} + 1, L_{r, col} - 1}$$

前面两个括号表示枚举的最终字符组成长度为 $1,2$ 的回文子序列。

这样无法通过，考虑优化。

考虑到从 $dp_{l,r-1}$ 推到 $dp_{l,r}$ 需要多算什么信息，显然只有 $r$ 处一个地方会多出一个字符的贡献，设这个地方字符为 $c$ ，同时记 $u$ 为 $R_{l,c}$ ，$v$ 为 $L_{r,c}$ ，我们还要加上的贡献是 $dp_{u + 1, r - 1}$ ，同时在 $dp_{u+1,v-1}$ 处贡献被记了两次，于是需要减去。

在讨论一波 $u,v,r$ 的关系即可判断长度为 $1,2$ 的回文子序列的增量。

于是复杂度就符合要求了。

# D

bdfs

Thue-Morse sequence