| 题目 | A | B | C | D | E |
|---|---|---|---|---|---|
| 状况 | AC+0 | AC+1 | 已补 | 待补 | 没看 |
涨分了，终于有点橙汁的颜色了。（我好菜呀）
A. Prefix Sum Primes#
题意#
\(a\) 个 1，\(b\) 个 2，用这些构造一个数列 \(\{a_i\}\)，使得它的前缀和 \(\{S_i\}\) 出现尽可能多的质数。
题解#
质数最多只能让小于或等于 \(a + 2b\) 的全部出现一遍；\(a = 0\) 或者 \(b = 0\) 就直接输出就好，\(a = 0\) 时最多能出现个质数 \(2\)；如果能有一个 1 和一个 2，那就可以先放下一个 2，再放下一个 1，接下来把剩下的 2 全部放下，最后放下剩下的 1，这样做是因为偶质数只有个 2，接下来尽可能地构造出来所有的奇数，就可以保证小于或等于 \(a + 2b\) 的全部出现一遍了。
B. Three Religions#
RE 一发，交题的时候没仔细检查，状态压成整数时越界了
题意#
给个长度为 \(n \le {10}^5\) 的小写字母字符串 \(S\)，然后有 3 个长度不超过 \(250\) 初始为空的小字符串 \(t_{i}\)。有 \(q\) 次操作，要么在某个小字符串后面加一个小写字母，要么删掉某个小字符串最后的字符。每次操作完成后，回答可否从 \(S\) 抽取 3 个不相交的子序列，和 3 个小字符串相同。
题解#
假设 3 个小字符串不变，可以有 \({dp}_{i, j, k}\)，意义是从 \(S\) 一个字符一个字符地划分 3 个子序列，构成了 3 个小字符串各自的前 \(i, j, k\) 个字符的情况下，最少需要使用到 \(S\) 的前 \({dp}_{i, j, k}\) 个字符。
有 \({dp}_{0, 0, 0} = 0\)，记 \({nearest}(i, c)\) 为 \(S\) 从第 \(i\) 个字符找，字符 \(c\) 第一次出现的位置。则：
\[{dp}_{i, j, k} = \min\begin{cases}
{nearest}({dp}_{i - 1, j, k} + 1, t_{0, i}), & i > 0; \\
{nearest}({dp}_{i, j - 1, k} + 1, t_{1, j}), & j > 0; \\
{nearest}({dp}_{i, j, k - 1} + 1, t_{2, k}), & k > 0.
\end{cases}\]
\(nearest\) 可以 \(\mathcal{O}(n \Sigma)\) 时间内预处理出来，\(dp\) 转移 \(\mathcal{O}(1)\)
会发现这个 \(dp\)，在每次修改某个小字符串，比如 \(t_0\) 末尾的时候，只需要重新对各种 \(j, k\) 算 \({dp}(|t_0|, j, k)\) 即可。
所以时间复杂度大概是 \(\mathcal{O}(n \Sigma + q \cdot 250 \cdot 250)\)。
C. Tree Generator™#
比赛时实际想到、也查到了，使用DFS序类似的动态维护树的深度等信息。但是没有想到维护直径的方式（有点菜）。补一下。
D. Abandoning Roads#
待补
E. Election Promises#
待补
评论