最近的做题小结

Hello 2026

A. Binary Array Game

大致题意：给定一个只包含数字 和 的数组 （大小为 ），双方轮流操作。

每次操作需选择两个整数 和 满足 ，然后将子数组 替换为一个单独的数字 ，当替换后数组只剩下一个数字时，若为 则先手方获胜。若为 则后手方获胜，问先手方是否存在必胜策略。

思路：注意到先手最后一次操作时，若

• 序列全是 ：则先手显然直接操作整个数组即可获胜；
• （或 ）：则先手直接操作 （或 ）即可获胜；
• Otherwise：先手无法同时操作 和 ，无法一次性获胜，后手直接操作整个序列即可获胜。

故先手获胜的充要条件是 且 ，时间复杂度 。

B. Yet Another MEX Problem

大致题意：给定一个长度为 的序列 和一个整数 ，每次需要选定一个长度为 的具有最大 MEX 值的窗口，并删除窗口中任意一个元素， 次操作后，最大化剩余元素的 MEX 值，其中 MEX 表示序列中未出现的最小非负整数。

思路：由于 次操作后序列长度变为 ，故最终答案一定不超过 ，且不会超过原有序列的 MEX 值，故答案的上界是 ，下面证明其必能取到

• 由于选择的窗口长度为 ，故区间内值不小于 的值都可以进行删除；
• 窗口中值重复的数字无效，亦可以删除；
• 是否存在以上两种任何一种都无法满足的情况？答案是否定的，因为在 这 个数中，所有值均小于 且不存在重复值的情况显然是不存在的，故每次必定可以删除一个无效元素值。

故下界与上界重合，答案即为 ，时间复杂度 。

C. War Strategy

大致题意：有一排长度为 的基地，其中第 个为根据点，初始状态下根据点有一个士兵，每天可以选择任意一个基地内的任意个士兵向相邻根据点移动，移动后根据点产生一个新的士兵，求 天后，士兵最多能覆盖多少个基地？

思路：容易想到二分答案，确定答案范围 ，接下来是在线性时间内进行验证，对于总长为 ，以 为中心，要覆盖 个点， 天内能否满足。

首先令 ，除去根据点，对于两边扩散的的最大长度，易知短边 ，长边 ，则

短边扩散的最佳距离

长边扩散的最佳距离

接下来考虑花费的时间，由于中心点在 处，则为了节省时间可考虑一次性链式运送到最远，路途每经过一个基地留下一个士兵即可，故需积攒 个士兵即可向长边运送，额外花费 天，注意到此时短边所需积攒时间一定小于长边的运送时间，故不再需要花费额外的时间。故答案为 天，将其与 比较即可。

整体复杂度 。

思考

以上是用逆推的思路来进行检验的，如果顺推的话有没有更简便的做法？

有的兄弟，有的，以下借鉴标答思路。

若 ，则将 变为 ，操作后，中心一定偏右，优先扩散右侧。

定义 分别表示向左、向右已经扩展了多少基地，初始值均为 ，接下来轮流地让 和 增加 ，直到不越界且 天内能完成即可。

向右扩展（即增 ）时，需满足

向左扩展（即增 ）时，需满足

无法增加时退出循环即可，最后覆盖的基地数为 ，整体复杂度 。

可以看到这种做法推出的花费天数与前面的做法是一样的，但避免了二分查找的对数开销。

D1. Tree Coloring (Easy Version)

大致题意：有一棵由 个节点构成的有根树，节点序号从 到 ，根节点序号为 ，每个节点初始均为白色，定义 为节点 的深度，每次操作你可以选择一些节点将它们涂黑，要求选择的节点之间互相没有边相连且深度不同，最小化将整棵树涂黑的操作次数。

思路：是个比较常规的图染色问题，考虑哪些节点之间相互排斥。定义“团”为节点的一种集合，该集合间所有节点两两间不能同时涂黑，则只需要求出最大团即可。

• 首先是相同深度的节点之间组成“团”，定义深度为 的点数为 ，则最大团为 ；

• 其次是对于每个节点 与其子节点之间组成“团”，则“团”的表达式 为

最大团为 ，故最终答案为 。

其中 可通过拓扑排序求得， 可通过桶计数 求得，整体复杂度 。

E. LCM is Legendary Counting Master

大致题意：给定一个长度为 的序列 和一个正整数 ，序列中每个元素都在 中。

定义序列 是“好序列”，当且仅当

• 序列 严格单调递增；

你需要用 范围内的整数去替换序列 中每个的 ，计算替换后 是“好序列”的种数。

我们认为序列 与 序列 相同，当且仅当 。

思路：复杂的带有最小公倍数的分式，考虑将其化简。

铺垫结论：当 时，，证明如下：

定义 ，则 ，，且 ，，故 ，证毕。

下面开始推导，易知有

且

故

不等式取等的充要条件为

于是题目转化为求满足该条件的序列个数。

对于 ，理解为 是 的因数，即若有 ，则应满足 ，这样的二元组通过可通过动态规划解决。

设 为长度为 的前缀序列，末项为 的“好子序列”数，则从 转移到 时，允许转移当且仅当

对于每个 ，枚举其因数 ，令 ，若 ，则允许转移，否则不允许转移。

这时候思路就很清晰了，初始 ，枚举后，对于从 转移到 时，若 或 ，则进行转移

否则不转移。

最后答案即为

拓展

以上做法的复杂度是多少？

由于过程中我们对每个 枚举它的所有约数 ，故枚举的次数为 ，则对所有 做一次复杂度为 ， 轮 dp 就是 。

以下是关于 式的推导。

定义

这里可以交换求和顺序，先固定约数 ，考虑满足 且 的数量，故

对于第一部分

其中 为欧拉初始。

对于第二部分，记 为 的小数部分，其影响比较小，事实上，利用狄利克雷双曲求和法（有兴趣的读者可以自行探索），可以估算出

故

可以看到其主项为 ，故题目整体复杂度为 。