本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-17 14:11:11

那咤 2 系列赛 题解

题目并非按照难度升序排序

谢罪

NOI 风格的 PDF 太难做了，有些公式放进去爆炸了（比如 T2 的 K），以及题面数据范围有误，谢罪。

疏忽考虑，奇怪原因导致 T1 SPJ 无法正确返回结果，谢罪。

T3 搬大样例搬串了，谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪……，错了哥。

没想到会换机房，科研做法忘记改存储地址了，谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪。

太多了谢不开了，错了哥。

第一次办模拟赛，经验不足，望原谅（想骂就骂吧，错了哥）。

网球君

P5959 [POI 2018] Plan metra - 洛谷

首先考虑树的形态，只会有两种情况：

• $1$ 与 $n$ 直接连边，其余点连向 $1$ 或 $n$。
• $1$ 与 $n$ 的路径上有一些点，其余的点都挂在这条链上。

对于第一种情况，要求所有的点的 $\left| d(1,i) - d(i,n) \right|$ 均相等。

考虑第二种情况，在 $1$ 号点与 $N$ 号点之间，必然有一条路径，在这条路径上的点 $i$ 都满足 $d(1,i) + d(i,n) = d(1,n)$。那么 $d(1,n)$ 就应该为

$$\min_{i = 1}^{n} {d(1,i) + d(i,n)}$$

如果我们选择了一个更大的作为 $d(1,n)$，那么小于它的点就无法放置了。

接下来我们需要做的操作就是在这条链上挂上一些节点，我们考虑在点 $i$ 上挂上点 $j$，那么需要满足 $d(1,j) - d(j,n) = d(1,i) - d(i,n)$。

我们设 $i,j$ 之间的边权为 $w$，那么 $d(1,j) = d(1,i) + w$，$d(j,n)$ 同理，两个减一下就有了这个式子。用 map 存一下即可。

大战

P12738 [POI 2016 R2] 口吃 Stutter - 洛谷

在这里我们称题目中要求的 $K_{2\times i} = K_{2\times i - 1}$ 的两个数称为一个配对。

时空均为 $O(n ^ 2)$ 的做法应该是好想的，看原题题解是设 $f_{i,j}$ 表示 $A$ 序列前 $i$ 个，$B$ 序列前 $j$ 个元素，满足条件的最大长度，转移的时候像其他公共子序列的题目一样转移就好。

这里我最开始想到的状态是 $f_{i,j,0/1}$ 表示 $A$ 序列前 $i$ 个，$B$ 序列前 $j$ 个，当前已经配对完成 / 还没有完成配对的最大长度。

转移时，对于 $A_i = B_j$ 的情况，我们记录 $A_i$ 和 $B_j$ 上一次出现的位置，记作 $pre_i$ 和 $pr_j$，那么转移就有：

$$f_{i,j,0} = \max(f_{i,j,0},f_{pre_i,pr_j,1} + 2)$$

发现当我们从最近的一个转移过来是不劣的，而由于转移时我们已经保证了 $A_i = B_j$，所以我们不需要再考虑 $i$ 的限制，只需要从 $B$ 序列中 $j$ 前面第一个与 $j$ 相同的位置 $k$，从 $f_{x,k}$ 转移过来即可，我们维护前缀最大值，直接转移即可。

题解：P12738 [POI 2016 R2] 口吃 Stutter - 洛谷专栏

首先考虑一个时空复杂度都是 $O(n^2)$ 的做法：

首先求出 $a_i,b_i$ 中的每一个数下一次的出现位置 $nxta_i,nxtb_i$。类似于正常的 LCS，设 $dp_{i,j}$ 为考虑 $a$ 的前 $i$ 项，$b$ 的前 $j$ 项的最长公共口吃序列长度，考虑向后转移，显然有以下转移：

• $dp_{i+1,j}\leftarrow dp_{i,j}$，$dp_{i,j+1}\leftarrow dp_{i,j}$；
• 特别地，若 $a_{i+1}=b_{j+1}$，则 $dp_{nxta_{i+1},nxtb_{j+1}}\leftarrow dp_{i,j}+2$。

由于空间限制只有 32MB，而当前的状态转移又无法进行滚动数组优化，考虑重新设计状态。

仔细分析转移过程，考虑如何将第二步写成能够滚动数组优化的形式。现在的转移过程是 $i\to nxta_{i+1}$，$j\to nxtb_{j+1}$，不如我们先将 $j$ 一步移动到 $nxtb_{j+1}$，并对当前状态进行标记，代表 $i$ 目前只匹配了一次，在转移的过程中，不断将 $i$ 往右移，不改变 $j$ 的值，直到发现 $a_i=b_j$（此时的 $j$ 就相当于原来的 $nxtb_{j+1}$），完成一次匹配。

这样我们只会从 $dp_i$ 转移到 $dp_{i+1}$，可以使用滚动数组优化。具体的转移可以参考代码。其中的一个细节是，若发现 $a_{i+1}=b_{j+1}$，我们只能将 $dp_{i+1,nxtb_{j+1},1}$ 更新，但是此时 $a_{i+1}=b_{nxtb_{j+1}}$，因此我们完成匹配时判断的是 $a_{i+1}$ 和 $b_j$ 是否相等。

魔丸

P7215 [JOISC 2020] 首都 - 洛谷

做法 $1$

可以考虑一种颜色 $c$，将它作为目标颜色，将它的所有结点从树中取出来。

这样可以确定最小的一棵连通子树使得所有颜色为 $c$ 的结点都在这棵连通子树上。

但是连通子树上会存在许多其他颜色的结点。这样可以确定很多形如“必须将颜色 $d$ 归为颜色 $c$ 才能达成目标”的颜色之间的关系。然而只将所有 $d$ 变成 $c$ 是不够的。

将这样的颜色关系进行连边。$c$ 连向 $d$ 表示 “必须将颜色 $d$ 归为颜色 $c$ 才能达成所有颜色为 $c$ 的结点组成一棵连通子树”。

根据这样的依赖关系，对所有颜色都去尝试连边，然后将图建立出来。

可以发现，想要满足“所有颜色为 $c$ 的结点组成一棵连通子树”，必须要将点 $c$ 可以到达的所有颜色都变成 $c$。答案等价于点数最少的缩点之后出度为 $0$ 的强连通分量的点数。

而连边可以使用重链剖分+线段树优化建图，建立同色结点形成的连通子树可以使用类似虚树的建立方法。

这种方法的时间复杂度是 $O(n\log ^2n)$，瓶颈在于线段树优化建图和确定连通子树上，这些的常数是低于点分治的，效率良好。

更优的理论复杂度

首先考虑一个 $n^2$ 的暴力，我们考虑对于每种颜色的点，维护一个队列，最初将所有与它颜色相同的点加入队列，随后将他的所有父亲节点加入，以及所有与它父亲颜色相同的点，这样相当于将所有必要的点都加入了，时间复杂度 $O(n^2)$。

发现有这样一条贪心性质：如果以 $y$ 为根时选到了颜色 $x$，则以 $x$ 为根的答案一定不会更劣。

换句话说：如果我们在统计点 $x$ 时发现要选颜色 $y$，但我们已经知道了以 $y$ 为根的答案，则无需继续统计这个 $x$，因为选择 $x$ 一定要选择 $y$，所以选择 $x$ 一定会包含选择 $y$ 的所有贡献，因此选择 $y$ 更优。

有了这个结论，我们考虑点分治，考虑选择分治中心作为这个点的最小次数，依旧维护队列，如果发现队列中元素位于当前子连通块外，则直接返回即可，否则假如有关的点，计算贡献取 $\min$ 即可，由于对于每个子连通块计算是 $O(size)$ 的，因此总时间复杂度 $O(n\log n)$。

掌牧松

CF1393E2 Twilight and Ancient Scroll (harder version) - 洛谷

考虑暴力，直接设 $f_{i, j}$ 表示前 $i$ 个字符串，第 $i$ 个删了第 $j$ 个字符的合法方案数。

直接暴力枚举前一个，然后暴力比较 $O(L^3)$。

然后可以将比较换成 hash 加二分比较时间复杂度 $O(L^2 \log L)$

然后考虑将 $s_{i, j}$ 排序，$s_{i, j}$ 表示字符串 $i$ 删除第 $j$ 个字符，这可以贪心排序，就是考虑字符串 $i$ 第一个不同的位置，如果 $a_i<a_{i+1}$ 那么删掉 $1\sim i$ 中的某个字符一定比删除 $i+1 \sim len$ 的某个字符字典序小，所以将 $1 \sim i$ 设成字典序前 $i$ 小；如果 $a_i > a_{i + 1}$ 是类似的。然后将前 $i$ 个字符删掉，继续重复即可。

然后现在设 $f_i,j$ 表示前 $i$ 个字符串，第 $i$ 个是 $s_i,k$ 中的吃第 $j$ 小时方案数。

然后 $f_{i,j}$ 一定由 $f_{i-1}$ 的某个前缀转移过来，而且如果 $j$ 增加，那么它能从 $f_{i-1}$ 转移过来的区间长度也增加。

所以那个指针扫一下，然后二分判断即可做到 $O(L\log L)$。

然后发现只会比较相邻的字符，维护三个数组，分别是偏移量为 $0,1,-1$ 时的 lcp，然后就可以 $O(1)$ 比较了。