IOI 2022 Day1 题解

· · 个人记录

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 的大小关系。

--- ### 题解： 这里写的就是我的思考过程。 首先考虑一个最最 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)$。