IOI 2022 D1T1 Fish

题目大意：

有一个 \(N\times N\) 的网格，其中的 \(M\) 个位置有垒球，第 \(i\) 个垒球的位置为 \((x_i,y_i)\)，重量为 \(w_i\)。

你可以为每一列 \(c\) 选择一个前缀的行 \(1,2,\ldots,\ldots,r_c\) 修建长堤，这样 \((1,c),(2,c),\ldots,(r_c,c)\) 这些位置就会被长堤覆盖。

如果一个垒球的位置没有被长堤覆盖，且其左右相邻的位置至少有一个被长堤覆盖，那么就会有一个 ix35 走到长堤上捡起这个垒球，即如果垒球的位置为 \((x,y)\)，它能被捡起当且仅当 \((x,y)\) 未被长堤覆盖且 \((x,y-1),(x,y+1)\) 至少有一个被长堤覆盖。

求最多能捡起总重多少的垒球。

\(N\leq 10^5,\ M\leq 3\times 10^5\)

题解：

假设 \(r_{c-1}<r_c>r_{c+1}\)，那么第 \(c\) 列的垒球都不能被捡起，所以不如直接把第 \(c\) 列修到顶，即 \(r_c\) 可以改为 \(N\)。

假设 \(r_{c-1}>r_c<r_{c+1}\)，那么第 \(c\) 列不如不修，所以 \(r_c\) 可以改为 \(0\)。

于是我们观察长堤的形状，发现修建了长堤的列可以分成若干连续段，每一段内 \(r_c\) 先递增后递减。

据此容易写出 DP，时间复杂度为 \(O(M\log M+N)\)。

IOI 2022 D1T2 Prison

题目大意：

有 \(500\) 个囚犯，还有一个房间，房间中有两个袋子 \(A,B\)，分别装有 \(n_A,n_B\) 个垒球，此外还有一个数字 \(x\)，初始为 \(0\)。囚犯们已知 \(1\leq n_A,n_B\leq N\) 且 \(n_A\ne n_B\)，他们的目标是指出 \(n_A\) 和 \(n_B\) 的大小关系。

现在会按照随机的顺序每次叫一个囚犯进房间，此时囚犯可以看到数字 \(x\)，并做出两种选择之一：打开袋子 \(A\)，或者打开袋子 \(B\)，即获知 \(n_A\) 或 \(n_B\)。

此时囚犯知道了 \(x\) 以及一个袋子中的垒球数量，他可以做出三种选择之一：指出 \(n_A<n_B\)，或者指出 \(n_B<n_A\)，或者将 \(x\) 修改为 \(x'\)（也可以 \(x'=x\)）。

你需要构造一种策略，使得任意时刻 \(0\leq x\leq X\)，且在 \(500\) 个囚犯都进去过一次之前得到 \(n_A,n_B\) 的大小关系。

\(N\leq 5000\)，当你构造的 \(X\) 满足 \(X\leq 20\) 时得满分。

题解：

这里写的就是我的思考过程。

首先考虑一个最最 naive 的方法：考虑 \(n_A,n_B\) 的二进制表示，前两个人比较 \(n_A,n_B\) 的最高位，第三个和第四个人比较 \(n_A,n_B\) 的次高位，以此类推，那么可以实现如下：

• 第 \(2i\) 个人离开房间后确保 \(x\) 为 \(3i\)；
• 第 \(2i+1\) 个人来到房间，会发现 \(x\) 为 \(3i\)，于是查看 \(n_A\)，如果 \(n_A\) 第 \(i\) 高位为 \(0\) 则将 \(x\) 改为 \(3i+1\)，否则改为 \(3i+2\)；
• 第 \(2i+2\) 个人来到房间，根据 \(x\) 是 \(3i+1\) 还是 \(3i+2\) 就可以知道 \(n_A\) 第 \(i\) 高位是 \(0\) 还是 \(1\)，他再查看 \(n_B\)，如果这一位不同，那么可以直接得到答案，否则就把 \(x\) 改成 \(3i+3\)，再比较下一位。

这样需要 \(X=38\) 左右。

我们将这方法略作修改，如果第 \(2\) 个人进来看到 \(n_A,n_B\) 最高位相同，并不是只能把 \(x\) 改成 \(3\) 然后交给下一个人，实际上他还掌握更多信息，比如 \(n_B\) 的次高位，于是我们将策略改成如下：

• 第 \(1\) 个人来到房间，会发现 \(x=0\)，查看 \(n_A\)，根据最高位跳到 \(x=1\) 或 \(x=2\)；
• 第 \(2i\) 个人来到房间，根据 \(x\) 的奇偶性知道 \(n_A\) 当前比较位是 \(0\) 还是 \(1\)，然后查看 \(n_B\)，如果不同则直接返回，否则看 \(n_B\) 的下一位，根据 \(0\) 还是 \(1\) 跳到两个不同的 \(x\)；
• 第 \(2i+1\) 个人同理，不过查看的是 \(n_A\)。

这样只需要 \(2\log N\) 次，即 \(X=26\)。

再优化一下，发现这里采用二进制不如采用三进制，\(3^8>N\)，所以只需要 \(X=3\times 8=24\) 即可。

再想一想，其实对于不同的数据范围可以采用不同的进制，于是我们考虑 DP，令 \(f(i)\) 表示 \(N=i\) 需要的最小的 \(X\)，枚举将 \(i\) 分成 \(j\) 段，那么 \(f(i)\leftarrow f(\lceil\dfrac{i}{j}\rceil)+j\)，这样应该可以 \(X=22\) 或者 \(X=21\)。

现在只需要卡一下常数就可以了，我们注意到如果第一个人进去发现 \(n_A=1\) 或者 \(n_A=N\) 都可以直接返回结果（因为保证 \(n_A\ne n_B\)），所以我们每次可以把边上两个数砍掉，于是转移变成 \(f(i)\leftarrow f(\lceil\dfrac{i-2}{j}\rceil)+j\)，这样就能顺利得到 \(X=20\) 的解。

IOI 2022 D1T3 Towers

题目大意：

有 \(N\) 座塔，第 \(i\) 座塔高度为 \(h_i\)，保证高度两两不同。

现在有 \(Q\) 个询问，每个询问给定 \(l,r,d\)，询问从 \([l,r]\) 中至多可以选择多少个塔，使得他们两两可以 \(d\)-通信。

两座塔 \(i<j\) 可以 \(d\)-通信，当且仅当存在一座塔 \(k\) 使得 \(i<k<j\) 且 \(h_k-d\ge\max(h_i,h_j)\)。

垒球。

\(N,Q\leq 10^5\)。

题解：

对于一个确定的 \(d\)，令 \(l_i\) 表示 \(i\) 左边第一个比 \(i\) 高了至少 \(d\) 的位置，\(r_i\) 表示 \(i\) 右边第一个比 \(i\) 高了至少 \(d\) 的位置。

那么两座塔 \(i<j\) 能 \(d\)-通信，当且仅当 \(r_i\leq l_j\)，即它们对应的区间 \([l_i,r_i)\) 无交。

同时易证以下两个结论：

• 如果 \(i<j\) 满足 \(l_j<r_i\)，那么一定有 \(l_j\leq l_i\)，即不可能两个区间既不为包含关系，又相交。
• 如果对于某个 \(d\) 有 \([l_i,r_i)\subseteq [l_j,r_j)\)，那么对于更大的 \(d\)，这一关系也成立。

于是我们可以从小到大扫描 \(d\)，维护当前没有包含任何其他 \([l_j,r_j)\) 的区间 \([l_i,r_i)\)，根据第一个结论，它们是两两无交的。我们称这些区间为 \(d\) 对应的有效区间。

扫描过程中维护的方法是：用一个链表记录当前的有效区间，并且用优先队列记录每个区间在什么时间（即 \(d\) 增大到多少时）会和左边或右边合并，然后在合并时删去一个元素即可。由于询问在线，所以需要用主席树记录每个时刻的有效区间。

询问 \((L,R,d)\) 时，我们首先找到这个 \(d\) 对应的情况下，\([L,R]\) 中有多少个有效区间（一个有效区间 \([l_i,r_i)\) 在 \([L,R]\) 中定义为其中心点 \(i\) 在 \([L,R]\) 中）。

那么这些有效区间的中心一定是要选择的了，但是可能还不全面，因为左右两边可能还需要各补选 \(0\) 个或 \(1\) 个塔（这是因为可能某个有效区间与 \([L,R]\) 有交，但是其中心不在 \([L,R]\) 中，就没统计到）。

这个稍微讨论一下即可：

• 如果 \([L,R]\) 中一个有效区间都没有，那么我们找到 \([L,R]\) 中高度的最大值 \(h_m\)，显然最多只能在 \(m\) 左右各选一个，判断一下行不行即可；
• 如果 \([L,R]\) 中有至少一个有效区间，那么我们找到第一个有效区间左侧的最大值 \(h_m\)，考虑能不能在 \(h_m\) 左边多选一个即可（即 \([L,m-1]\) 的最小值是否不超过 \(h_m-d\)），右边同理。

用 ST 表预处理区间最值。

时间复杂度为 \(O((N+Q)\log N)\)。

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\)。

\(N\leq 2000\)，\(Q\leq 3N\) 可得满分。

题解：

首先可以想到一个 \(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：思维简单，代码不太好写题，感觉这题口胡起来非常舒服。