自动搬运

查看原文

来自洛谷，原作者为

	lightup37 KfbddzCkVrGtwLDijdpgaxqbLXDIoFsz51R2zxic

搬运于2025-08-24 22:24:28，当前版本为作者最后更新于2022-01-31 11:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

IOI2020 mushrooms 题解

题意

交互题. 给定 $n$, 有一个长度为 $n$ 的 01 序列 $a_0, a_1, \cdots a_{n-1}$, 你不知道 $a_1, a_2, \cdots a_{n-1}$ 的值, 但你知道 $a_0 = 0$.

我们定义一次操作为给定 $k(2\leq k\leq n)$ 和一个长度为 $k$ 的, 不含重复值的序列 $b_0, b_1, \cdots b_{k-1}$, 然后交互库返回 $\sum\limits_{i=0}^{k-2} [b_i \not= b_{i+1}]$.

你需要通过若干次操作, 求出 $\sum\limits_{i=0}^{n-1} (1-b_{i})$.

具体细节参见题面.

Note: 你需要 #include "mushrooms.h".

解法

为了方便, 以下我们将不加申明的将 $ret$ 用作上一次 $\texttt{query}$ 操作的返回值, 读者可以根据上下文知道这个 $ret$ 的值.

Method 1

我们考虑朴素暴力: 对所有 $i\in [1, n-1]$ 执行操作 $\texttt{query}(\{0, i\})$, 这是一个时间复杂度 $O(n)$ 的算法, 可以获得 ... 10 分.

Method 2

我们发现: 如果已知有 $k$ 个 0, 分别是 $a_{f_1}, a_{f_2}, \cdots a_{f_k}$, 那么可以执行这样的一次操作来求出长度为 $k$ 的序列 $g_1, g_2, \cdots g_k$ 中 0 的个数: $\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\})$. 容易知道 $\sum\limits_{i=1}^k g_i = \lceil\frac{ret}{2}\rceil$. 有 $k$ 个 1 的情况下同理.

而如何求出 $f_1, f_2, \cdots f_k$ 呢? 显然直接套用 Method 1 即可. 我们使用类似根号分治的思想可以做到 $O(\sqrt n)$ 的复杂度(实际上后续都是常数优化, 并没有超越这个复杂度.)

Optimize 1

我们考察这种操作: $\texttt{query}(\{g_1, f_1, g_2, f_2, \cdots g_k, f_k\})$. 那么可以根据 $ret$ 的奇偶性判断 $g_1$ 的值, 具体来说, 由于 $g_2, g_3, \cdots g_{k}$ 左右均为相同的值, 故不管这些数如何取值, 均不会影响 $ret$ 的奇偶性, 所以 $ret$ 的奇偶性只由 $a_{g_1}, a_{f_1}$ 决定, 也即可以得出 $a_{g_1}$ 的具体值. 于是我们可以动态的维护当前 0/1 的个数和这些 0/1 的位置然后每次启发式的用 0/1 去询问.

以上优化的代码

Optimize 2

这同时也可以对 Method 1 的过程做出优化: 在有两个相同值的数 $a_x, a_y$ 时, 每次可以通过 $\texttt{query\{p, x, q, y\}}$ 确定 $a_p$, $a_q$ 的具体值.

Optimize 3

Method 2 的过程已经难以优化, 接下来我们来优化 Method 1 的过程.

不妨考虑我们有充分多的 0 和充分多的 1, 接下来我们考虑如何更优的询问, 具体来说, 我们将用 2 询问次得到 5 个数的具体值.

我们设 $p_i$ 为所有 0 的位置序列, $q_i$ 为所有 1 的位置序列. 即 必有 $a_{p_i}=0, a_{q_i}=1$.

我们先进行询问 $\texttt{query}(\{x, p_1, y, p_2, z, p_3\})$. 根据返回值讨论: 首先可以发现根据 $ret$ 的奇偶性确定 $a_x$, 然后我们令 $ret\leftarrow \lfloor\frac{ret}{2}\rfloor$, 这样就有 $a_{y}+a_{z} = ret$. 显然只需要考虑 $ret = 1$ 的情况.

如果 $ret = 1$, 我们接下来进行询问 $\texttt{query}(\{q_1, y, q_2, p_1, z, p_2, u, p_3, v\})$, 然后令 $ret\leftarrow ret-1$(这是因为有相邻的 $q_2, p_1$).

首先考察 $ret$ 的奇偶性以确定 $v$, 然后令 $ret\leftarrow \lfloor \frac{ret}{2}\rfloor$, 这样就有 $1-a_y+a_z+a_u = ret$, 也即 $2a_z+a_u = ret$, 这样又可以根据 $ret$ 的奇偶性来确定 $a_u$, 从而确定 $a_z$ 和 $a_y$.

以上优化的代码

Optimize 4

调整你的参数.

AC 代码