MX-S3 T3 官方题解

vegetable_king · 2024-08-17 22:12:09 · 题解

出题人题解。

首先有一个转化是我们可以求出最终的集合 S，再倒过来进行交换操作得到初始的 S。

然后考虑如果获得了一个数 p 之后，你可以把它和 1 交换。因为 p 是所有 pair 中更大值最小的，所以一定有 p \le o，其中 o 是与 1 配对的数。

先不考虑 p = o 即 p 与 1 配对的情况，此时有 p < o。

那么和 1 交换之前，配对情况显然是 (q, p), (1, o)，交换之后配对情况变为 (1, q), (p, o)，且有 q < p < o，则操作后返回的 res 一定为 q。于是我们知道了，在这次操作前 p, q 是配对的，但是这并没有什么用，因为无法确保 p, q 之前没有动过，也无法确保以后不会动。

我们还要找到一个更大的数与 q 配对从而将它覆盖在底下来得到新的 res，选择 2n 就可以了。于是交换 1, 2n，配对情况变为 (q, 2n), (p, o)（如果 o = 2n 则变为 (q, 2n), (1, p)，但这并不重要），于是我们成功把 q 覆盖在了底下。而且因为 2n 是全局最大值，只要 q, 2n 这两个数保持配对，那么它们就都不会成为 res，可以直接将这两个数删掉，变为一个 n' = n - 1 的子问题。

现在考虑 p = o 的情况。如果是这种情况，交换 1, p 实际上不会产生任何效果，可以通过返回的 res 是否变化来判断。然后我们只需要同样地交换 1, 2n 来覆盖住 p 即可。

最后 n = 1 的时候一定会剩下一个 1，而另外一个数就是 res，共需要 2(n - 1) 次询问。但是这个 res 是我们能通过之前产生的 pair 推导得出的，所以就可以减少一次询问，做到 \max(0, 2n - 3) 次询问。

code