Shannon’s Channel

总览#

C. 征服倍数#

题意： 给定区间 [l,r]，从 x=l 开始两人轮流删除当前 x 的一个倍数并令 x++，无法操作者输，问先手 Alice 是否必胜。

思路：

1. 每一轮只关心当前数字 x 是否还能在区间内找到一个未删除的倍数。若找不到，当前玩家失败。
2. 偶数的倍数仍然是偶数，所以偶数回合只能消耗偶数；奇数 x 可以删除 2x，从而提前消耗之后的偶数回合。
3. 若最小奇数的二倍不在区间内，则双方无法有效干扰对方，只能不断删除当前数字本身。此时直接按区间长度的奇偶判断胜负。
4. 若最小奇数的二倍在区间内，则拿到这个奇数的一方可以先删除它的二倍。这样场上会少掉一个偶数，而奇数数量不变，之后只要每轮删除当前数字本身即可。
5. 由于剩余偶数数量不超过奇数数量，且偶数无法删除奇数，偶数一方会先遇到没有可删倍数的情况。因此拿到最小奇数的一方可以获胜。

实现： if-else 判断即可实现。

复杂度： O(1)

I. 寻找终极神器#

题意： 给定 n 个非负数和一个 k，你可以任选 k 个数合并成它们的乘积，问经过若干次操作后，剩下神器中最大可能的能量值对 998244353 取模是多少。

思路：

1. 贪心找最大的数进行合并，但凑够 k 个数才能进行合并。

2. 如果合并的数字存在 0 会导致合成得到的数变小；数字 1 不会对合并出更大数字产生贡献，但可以用来凑合并时需要的数量 k。

3. 推导出所有能用来合并的数字个数 m 满足

   $$m \equiv 1 \pmod{k-1}$$

4. 遍历，设 drop 作为所需要扔掉的大于 1 的数字个数，sz 是大于 1 的数字总个数，need 是需要的 1 的个数。 int need = (1 - (sz - drop) % d + d) % d; 使 drop 尽量小的前提下 need 符合个数条件。

5. 如果全丢掉了，有数字 1 答案就为 1，否则答案就为 0。

实现： 循环和判断。

复杂度： O(n)

B. Aqua 学习图论#

题意： 给定一个无向图和一个排列 p。可以自行决定 DFS 中枚举起点、枚举邻接点的顺序，也可以添加边。求使 DFS 输出恰为 p 的最少补边数，并构造这些边。

思路：

DFS 的输出是先序遍历。按照 p 从前往后模拟访问过程，并构造一片 DFS 森林。

对每个点维护 sz[u]，表示 u 在原图中尚未访问的邻居数量。初始时它就是 u 的度数；每当一个点 x 首次被访问，就遍历原图中 x 的所有邻居 v，令 sz[v]--。因此任意时刻 sz[u] 的含义始终正确。

设当前刚访问到 u：

1. 若 sz[u] == 0，说明 u 的原图邻居均已访问。此时 DFS 可以从 u 返回父亲。
2. 若 sz[u] > 0，则 u 还存在未访问的原图邻居，DFS 不能返回。排列中下一个尚未访问的点必须成为 u 的直接儿子。设它为 v：若原图有边 u-v，直接递归访问 v；否则补上 u-v 后递归访问 v。
3. 访问完 v 的整棵子树后，需要再次处理 u。此时子树中的访问可能已经使 sz[u] 变为 0；若仍大于 0，则继续为 u 构造下一个儿子。

若一棵构造树完全返回，而排列中还有未访问点，则将下一个未访问的排列元素作为新树的根。此时不可能存在已访问点到未访问点的原图边：否则该已访问点仍有未访问邻居，sz 不会归零，整棵树不可能完成回溯。因此这样新开一棵树合法。

正确性证明：

每次从 u 返回时，sz[u] == 0，即 u 没有未访问的原图邻居；DFS 不会遗漏必须在返回前处理的边。反之，若 sz[u] > 0，u 不能返回，而目标输出的下一个点 v 必须紧接着由 dfs(v) 输出，所以 v 必须是 u 的直接儿子。边 u-v 因而是必要的：原图没有它时，任何合法方案都必须补上这条边。

算法恰在这些必要的时刻补边，并以 p 的顺序递归访问儿子，所以可以构造出输出为 p 的 DFS 森林。又因为每一条补边都被任意合法方案强制需要，补边数量最少。

实现： 使用集合存图以查询边 u-v 是否存在。补边只需记录到答案中，不必写回原图，因为 sz 只统计原图中尚未访问的邻居。递归函数在处理完一个儿子后再次处理当前点，即可模拟从儿子返回后继续枚举邻居的过程。

复杂度：O(m log n)，空间复杂度：O(n + m)。

D. 减少与交换#

赛时队友通过，暂时不补题解。