题解 | 牛客挑战赛 56

A - Bitwise Or vs LCM

对于 ()，若 ，那么 ，是一组解。否则 ，不可能是解。

于是就变成找序列中是不是存在一个数是另一个数的因数， 枚举倍数即可。

B - 心灵迷宫

先考虑分配答案矩阵每一行的最小值（记之为固定点），再分配每一列的值。下面给出一种可能的贪心做法。

首先按 从小到大排序，从上至下依次为每一行分配固定点。对于第 行，如果 之前没在第 列出现过，则将它分配给第 列，否则分配到第 列；如果第 列也出现过，则分配给第 列……以此类推。中间如果出现不合法情况，则答案一定不合法。填好 行后，对每一列依次把没用过的数从小到大、从上往下填，最后判断解是否合法。

为每一行分配固定点的无解判定正确性是显然的。对于列的填写，如果在某一种方式中，一个数被分配到了更后面的位置，则由于 非降，往后丢反而可能变得不合法，因此越靠前越好。

任何有解的方案都可以通过交换行与调整列中非固定点的顺序对应到上述构造方案。简单证明：对于列的填写，从上至下调整成升序一定不会变劣，因此先调整为升序。考虑将最优解中某一列的固定点横向移动到另一列上，移动过程一定对列上的数无影响：如果交换的两列在第一步里固定点都为 ，那么交换后也合法，因为在它们两行之间的列上元素肯定不小于 ；如果只有一个固定点 ，那么另一个固定点 在列上某个非固定点填充的 会在 所在行的上方。将 与 按照固定点相同的情况交换，能让 移动到另一列上的对应位置。因此，固定点之间的移动是自由的，总是能通过将一列的固定点移动到另一列上，将固定点变成贪心做法中的模样。

该做法中需要对 排序，因此总时间复杂度为 。

C - 灵力之泉

先随便选一个点作为根节点 DP，记 为染色 子树的所有结点需要的最少时间，则对于结点 ，一定是在第一个能行动的时刻先染色 值前 大的儿子，在第二个能行动的时刻染色 值前 大的儿子，依次类推，最后 的值为染色儿子的时刻加上儿子子树所对应的 值中的最大值。

考虑换根 DP。当根节点从 往下移动到 时，由于 结点不再作为儿子，因此原来计算 时在 之后被染色的结点，都能往前移动一位而在更早的时刻被染色；原来在 之前被染色的结点，并不会因此导致染色时刻发生改变。因此维护一个原始染色顺序的前缀答案，与一个往前移动一位了的后缀答案，在换根到 时便可 计算来自 部分形成的新子树的 值。剩下的 DP 部分同原有 DP。

由于要在每个结点排序，因此总时间复杂度 。

D - 蜃楼观光

从小到大枚举 ，所有 和 一定都是 的因数，设 的因数从小到大分别是 ，如果能求出：

那么对答案的贡献即为：

通过从大到小遍历每个因子，维护 的后缀和，可以在 的时间复杂度内求解，对于所有 的时间复杂度总和为 。

考虑如何维护 和 ，可以转化为维护：

随着 变为 ， 所有因子的贡献会从 中消失，而 所有因子的贡献增加到 中，这部分的时间复杂度为 。

接着由 和 可以利用减法原理求解 和 ：

这部分时间复杂度为 ， 时值为 。

综上， 预处理每个数的因子后，时间复杂度为 ，空间复杂度为 ，可以通过本题。

E - 悟道

我们称被虚空覆盖的点为障碍点。

首先考虑没有障碍点的情况，那么游戏等价于四堆石子的取石子游戏，但这不好转化到有障碍点的情况，需要考虑一种不将四维独立开来的算法。

可以发现，对于固定的 至多存在一个 使得 是必败态，若存在两个 和 ，不妨设 ，则 可以一步达到 ，因此前者是必胜态。

从而必败态的数量是 个的，而对于一个状态有 个状态可以转移到它，因此按坐标从小到大枚举每一个状态，若其是必败态就标记所有能到达它的状态为必胜态，这样总标记次数为 ，遍历次数也是 ，时间复杂度为 。

注意到整个过程出现的数字都是 和 ，因此可以使用 bitset 加速。从小到大遍历 维护三个关于 的 bitset，分别为：

• 是否存在 满足 是必败态。
• 是否存在 满足 是必败态。
• 是否存在 满足 是必败态。

那么 是必胜态当且仅当上述三个 bitset 的并集中 对应位置为 或存在 使得 是必败态，将三个 bitset 取并 + 取反后利用 _Find_first 或 _Find_next 方法就可以找到第一个为 的位置 ，那么 即为必败态 (如果存在这样的 )，其它 () 均为必胜态。

这样我们得到了一个时空复杂度均为 的算法，注意到空间可以滚动数组优化，将遍历 抽象为遍历三维空间，那么三个 bitset 分别只需要开 维，从而空间复杂度可以优化到 。

接下来考虑有障碍点的情况，只需对上述算法做两个改动：

• 遍历过程中遇到障碍点 时，若 是障碍点，那么上述三个 bitset 在 位置都要清零，因为被这个障碍挡住就不能到必败态了。
• 上述过程对每个 对应的三个 bitset 取并 + 取反后，假设有 个 满足 是障碍点，因为障碍的阻隔使得每一部分都是独立的，那么要从小到大对这些 使用 _Find_next 找到对应的必败态。最多进行 次操作，这部分的时间复杂度为 。

将 个障碍点排序，在从小到大 的过程中维护一个指针以获取当前对应的 (或使用 map 和 unordered_map)，就可以得到一个时间复杂度为 ，空间复杂度为 的算法，可以通过本题。

F - 霉球研究

采用先花费 代价完全删掉某个 ，再直接添加出 的方法是平凡的，其代价是 ，因此只需考虑 中的串用了至少一个 的子串的情况。

可以发现此时的方案等价于从所有可能的 中各选出一些子串不相交地贴在 上， 中其余没被贴的地方可以直接加字符补上。在这种情况下，可以额外添加 个 串 ，这样添加操作也等价于"从 中选子串"，且代价为 。

考虑从 开始选 的某个子串最长能匹配多少，这个实际就是反串建立的广义 SAM 的 fail 树上从 跳到属于 的最近结点的长度。可以证明，对某个 选最长能匹配的串总是优的（考虑最后拼接的是 的情况，如果 还能更长，那么 少删一个代价减少 ， 多删一个代价增加 或变成免费，会更优）。因此记 为 的前 个字符需要的最小代价，那么可以枚举每个 串进行转移。

串个数很多，不能一个个枚举。但是我们发现对于 而言，由于每个 串都只会选匹配最长的情况（如果两个串匹配长度相同，那选其中原长最小的最优，因为花费等于原长减去当前结点长度），因此从 开始向后接 的子串，最多只能接 种本质不同的串，也就只有这么多种转移。

可以预处理得到选择每个点的最小代价，DP 的时候找到这 种长度对应的结点转移即可。另外需要多记录一维来表示目前有没有选过至少一个原来的 串，以避免选中的都是额外添加的 个串的平凡情况。

总时间复杂度 ，其中 为字符集大小。