IOI2020 mushrooms 题解

· · 题解

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 代码