题解：P16434 [APIO 2026 中国赛区] 蛋糕

cosf · 2026-05-09 22:12:33 · 题解

差点被题序创飞了。

因为 Sub 3, 4 的限制没有偏序关系，所以分开讨论。

对于 Sub 3，显然询问次数为 \log_2 W。考虑构造 \{1, 1, 2, 4, 8, \dots, 2^k\}。考虑 d 的位置：\{\dots, 2^{i - 1}, d, 2^i, \dots\}，我们从大到小依次枚举 j，并按照如下构造：

• 当我们找到 $i$ 之后，就直接二分即可（因为我们知道了 $d$ 的位置），次数为 $(k - i + 1) + (i - 1) = k \ge \lceil\log_2 W\rceil = 30$ 次，可以通过 Sub 3。

对于 Sub 4，我们先要解决 Sub 2。考虑构造 \{2, 2, 4\} 并询问下标 S_1 = \{0, 2\}, S_2 = \{3\}（注意，和原题同样是 0-\text{index}）：

• 当 d = 1 时，\{{\color{red}1}, 2, {\color{red}2}, {\color{blue}4}\}，返回 <；
• 当 d = 2 时，\{{\color{red}2}, 2, {\color{red}2}, {\color{blue}4}\}，返回 =；
• 当 d = 3 时，\{{\color{red}2}, 2, {\color{red}3}, {\color{blue}4}\}，返回 >；

更进一步，只要我们选取 a, b，满足 a + b \ge W，我们就能一次询问出，x 是属于 [1, a)、[a, b]、(b, W] 中的哪一个。

注意到 3^7 = 2187 \in [W, W + 200]，所以肯定是直接三分。这里以 W = 9 为例子，我们先构造 \{2, 3, \dots, W + 1\}。我们先要判断 d 是否属于 [4, 6]。这里可以询问下标 S_1 = \{2, 5\}，S_2 = \{9\}：

• 当 d \lt 4 时，S_1 = \{{\color{red}3, 6}\}，S_2 = \{{\color{blue}10}\}，返回 <。
• 当 d \in [4, 6] 时，S_1 = \{{\color{red}4, 6}\}，S_2 = \{{\color{blue}10}\}，返回 =；
• 当 d \gt 6 时，S_1 = \{{\color{red}4, 7}\}，S_2 = \{{\color{blue}10}\}，返回 \gt；

于是我们可以一次询问分辨出 d 在哪一个部分。

更普适的，假设当前将 d 限定在 [l, r] 中（保证区间长度为 3 的倍数），设中间的子区间为 l', r'，于是我们只用令下标 S_1 = \{l' - 2, r' - 1\}，S_2 = \{l' + r' - 1\} = \{l + r - 1\} 即可。注意这里 l + r - 1 可能超过了 W + 1，不过没关系，我们可以暴力地从 \lt l 的数里面暴力找（因为此时 l 肯定会比较大）。

那么询问次数就是严格 7 次了。

:::warning[代码] 恭喜你发现了滚木

场切了，以后再补。 :::