IOI 2022 Day2 题解 & 锐评
ix35
·
·
个人记录
IOI 2022 D2T1 Circuit
题目大意：
给定一个 N 个非叶结点，M 个叶结点的值，叶结点有初值 0 或 1，某个非叶结点如果有 x 个儿子，则需要设置一个参数 y\in [1,x]，表示如果其儿子有至少 y 个的值为 1，那么它的值也为 1。
现在进行 Q 次操作，每次翻转编号在区间 [l,r] 内的叶结点的初值（0 变成 1，1 变成 0），然后询问有多少种为非叶结点设置参数的方案，使得根结点值为 1，对 10^9+2022 取模。
N,M,Q\leq 10^5
题解：
如果你是赛后做题，那么解题的关键或许是看到排行榜——有一车人过了这题，说明这题是水题。
或者是觉得这题看上去非常不可做，因为编号区间和树的形态并无关联，我们不可能用任何树上的数据解构解决此题。
无论如何，我们可以猜想：每个非叶结点对答案的贡献独立，幸运的是这是对的，证明并不困难，略。
于是首先树形 DP 算出每个非叶结点单独为黑色时的答案，然后用线段树维护总的答案即可，时间复杂度为 O(Q\log M+N+M)。
IOI 2022 D2T2 Insects
题目大意：
现在有 N 个未知数 a_{1\ldots n}，还有一台神秘机器，机器初始是空的，你可以进行下列三种操作：
- 将一个数 a_i 加入机器；
- 将一个数 a_i 取出机器；
- 询问机器里出现次数最多的数的出现次数。
你需要求出 a_{1\ldots n} 中出现次数最少的数的出现次数，设每种操作进行次数的最大值为 Q。
---
### 题解：
首先可以想到一个 $O(N^2)$ 次操作的算法：每次放一对数进去，就能知道它们是否相等。
还有一种 $O(N^2)$ 次操作的算法（记为青蛙算法）：每次选择一个数，然后得到与它相等的所有数（加入一个别的数如果众数出现次数没有增加则说明不相等）。
还有一种 $O(N^2)$ 次操作的算法（记为垒球算法）：每次选择当前剩下的所有不同的数各一个（时刻保持众数出现次数为 $1$ 即可），这样当某一次得到的不同的数的个数和上一次不同时，就知道出现次数最少的已经取完了。
综合青蛙算法和垒球算法，可以得到 $O(N\sqrt N)$ 的算法。
考虑垒球算法的扩展：如果保持众数出现次数始终小于等于 $C$，就可以得到每个数的前 $C$ 次出现，设不同的数有 $x$ 种，如果选出了恰好 $Cx$ 个数则说明出现次数最少的数也出现了 $\ge C$ 次，否则说明是 $<C$ 次。
所以可以二分，得到了 $O(N\log N)$ 的垒球算法。
然后发现这个二分的操作次数实际上可以变成 $O(N)$，因为如果二分之后发现答案 $\ge C$，那么此时已经放进机器里的就不用动了，可以看成总数大致减半；如果二分之后答案 $<C$，那么此刻不在机器里的数就可以全部扔掉了，总数也大致减半，根据等比数列求和这就是 $3N$ 次左右的。
然后一交获得了 $99$ 分的好成绩，下面使用你的独门技巧乱搞卡常即可。这里我的方法是在判断时只要某个时刻机器里已经有 $Cx$ 个数就直接退出循环，没必要加剩下的数，同时为了防卡，初始序列要随机重排。
## IOI 2022 D2T3 Islands
### 题目大意：
有一张 $N$ 个点，$M$ 条边的有向图，你需要从点 $1$ 出发走一些边回到点 $1$，要求：
- 一条边经过后就会反向，也就是下次经过必须是从反方向经过；
- 不能连续经过同一条边。
构造一组方案，或说明无解。
$N\leq 10^5,\ M\leq 2\times 10^5
题解：
如果一个结点出度为 0，那么走到这里就寄了，所以可以删掉。
删掉之后可能会导致另一些点出度也变为 0，也要删掉，这个可以做一次拓扑排序，就相当于我们删掉了所有不能走到环的点。
现在我们断言，如果点 1 的出度 \ge 2，那么一定有解，下面给出构造。
事实上考虑下列结构：由于不存在零出度点，所以我们可以为每个点（除了 1）指定一条出边，这样整张图就形成了若干个基环树，以及一棵以 1 为根的树，如下图所示：
现在我们加上 1 的两条出边，那么有以下两种情况：
-
Case 1：至少一条出边指向以 1 为根的树外。
如下图所示，y,z 是出边到达的点，至少有一个在某个基环树上。
对于这种情况，我们先走到 y，然后沿着继续走，在 y 所属的基环树上绕一圈，再回到 1，现在整张图和初始情况相比就是 y 所在的基环树的环（红色环）被反向了。
然后再走到 z，同理绕一圈（蓝色环）再回 1。
然后再走一次 y，再绕一次红色环，这样红色环被绕了两次，就变回最初的方向了，同理再走一次 z，使得蓝色环也回到最初方向。
-
Case 2：两条出边都指向 1 为根的树内。
如下图左上部分所示：
这种情况我们考虑 y,z 的 LCA，如果 LCA 恰好是 1，那么按照和 Case 1 相同的方法做就是没有问题的。
否则我们换一种构造：首先走到 y，然后沿着树上路径走到 x，也就是绕了右上图的红色环。
然后走到 z，沿着树上路径走到 LCA，再从 LCA 走回 y，再走 y\to x 这条边，如左下图的蓝色环。
最后从 x 沿树上路径走到 LCA，再从 LCA 走到 z，再走 z\to x 这条边，如右下图的红色环，构造完成。
证明比较简单，注意图中 y,z 是动态变化的，在实现的时候，构造过程中的 y,z 始终是 x 的出边指向的点。
那么 1 的出度 \ge 2 的情况已经证完了，下面考虑 1 的出度 =1 的情况。
这时我们只能走这条出边，设为 1\to x，之后 1 就可以看出零出度点（只要在不走 x\to 1 这条反向边的情况下回到 1 就寄了），所以我们删去点 1，同样这也会导致连锁反应，还是用一个拓扑排序就可以把所有该删的点都删了。
在剩下的新图上，把 x 看成起点继续做即可，即如果 x 的出度 \ge 2 那么按照上面方法得到构造；如果 x 的出度 =1 那么再走它的出边，然后把 x 删掉，以此类推。
时间复杂度应该可以做到 O(N+M)，不过我在实现时为了图省事，在记录边的序号以及删点的时候用到了 multiset 和 map，复杂度为 O(N+M\log M)。
锐评环节
D1T1：比较简单的题，大概是想到单调性之后随便 DP 一下就行了，不过如果没想明白的话可能会用线段树去维护，其实是不用的。
D1T2：人类智慧题，有点看运气，运气好就想出来罢了，主要是到 X=26 那一步比较有难度，后面的使用其他进制并 DP 以及掐头去尾其实都不是很难。
D1T3：偏简单题，主要是想到用区间表示每个点的状态，后面的数据结构部分非常简单。
D2T1：诈骗题，猜出结论就没有难度了，而想到去猜这个结论其实并不很难（正如我前面所说，如果没有这种结论，这题是不可做的）。
D2T2：中档题，每一步优化都不是很难，但是只要少一步就做不出来，然后最后还要为了零点零几分在那卡常。
D2T3：思维简单，代码不太好写题，感觉这题口胡起来非常舒服。