【题解】dcy xya 模拟赛

· · 个人记录

那咤 2 系列赛 题解

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

谢罪

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

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

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

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

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

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

网球君

P5959 [POI 2018] Plan metra - 洛谷

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

对于第一种情况，要求所有的点的 \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 项的最长公共口吃序列长度，考虑向后转移，显然有以下转移：

由于空间限制只有 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) 比较了。