CF1746E1

dbxxx · 2023-06-20 22:05:16 · 题解

欢迎您到我的博客阅读本文，谢谢！

CF1746E Joking

交互库最开始给定一个正整数 n，并生成一个 x \in [1, n]，你的目标是得到交互库中的 x。

你可以向交互库提出问题：

提问一个集合 S，交互库回答的内容是 x \in S 的真假。该提问次数不能超过限制数 Q。

交互库可以骗人，也即交互库的回答不一定正确。但保证 交互库连续的两次回答中，至少有一次是正确的。

你还可以向交互库提交答案，直接提交一个正整数 i。你只有 2 次提交答案的机会。

保证 1 \le n \le 10^5。交互库是自适应性的，它会通过某种神奇策略动态改变 x，使得它仍然满足它所回答过你的所有问题，保证交互正确性的同时，尽可能让你慢地猜出答案。

E1 Easy Version

在 Easy Version 中，限制参数 Q = 82。

观察到提交答案的机会只有 2 次，因此中途就提交答案并不是特别明智。但直接放弃一次多余的机会也不是很明智。

因此我的想法是：当知道 x 的范围只有两个数的时候，直接把这两个数猜一遍就可以了。那么我们提问的最终目标从将 x 锁定成一个数弱化成了锁定成两个数的一个小范围。

对交互的询问进行分析，我们考虑交互库不骗人的时候怎么做。

我们大概能知道这种交互问题都是不断缩小 x 可能的范围得到答案的，不妨放称当前 x 可能的范围为“目标范围”，最开始目标范围就是 [1, n] 的正整数全集，而我们的目标就是把目标范围减少到大小为 2。为了确保询问次数低于限制参数，我们期望每次能让目标范围降低的尽可能多。

这里让目标范围降低多少的计算，应该按照交互库的 Yes，No 两种回答中，能让目标范围降低地最少的那个来计算，也即我们要按照最坏情况考虑。

比如当前的目标范围是 U，你提问一次 S = \{1\}（我们先暂且假定交互库不骗人），那么交互库回答 Yes，不管 U 多大都能降低成 1，也即 U 的大小会降低 |U| - 1。这个降低效果没人敢说不高。但是如果交互库回答 No，目标范围大小只能降低 1，这就很不优秀了。根据按照最坏情况考虑的原则，这种询问策略的目标范围降低效果为降低 1，明显不是我们想要的策略。

提一嘴，这里交互库自适应，所以要按照最坏情况考虑；但如果交互库不自适应，那么可能可以有正确率不是 100\% 但是可以很高的交互策略：可以算一下交互库回答两种答案的期望，从而得到目标范围降低的期望，而不是最坏情况。

如果一个交互策略的最坏情况很不优秀，但是期望比较优秀，在交互库不自适应的情况下可能也是可以做的。这是后话了。

如果交互库不骗人，策略还是比较容易想到的，折半查找即可。

设当前目标范围是 U，我们取 U 的一个大小为 \left\lfloor\dfrac{|U|}2\right\rfloor 的子集 S 进行提问。如果回答 Yes，那么目标范围 U \gets S，大小变成 \left\lfloor\dfrac{|U|}2\right\rfloor，也即降低 \left\lceil\dfrac{|U|}2\right\rceil；如果回答 No，目标范围 U \gets \complement_US，大小变成 \left\lceil\dfrac{|U|}2\right\rceil，也即降低 \left\lfloor\dfrac{|U|}2\right\rfloor。

那么这种策略，每次可以将目标范围 U 大小降低 \left\lfloor\dfrac{|U|}2\right\rfloor，我们可以在 \log_2n 的询问次数解决问题。

如果交互库骗人呢？

首先我们要分析清楚的是，会骗人的交互库对于我们询问的回答，能给我们提供什么确定的信息。容易看出，在交互库骗人时，单独一次询问的回答什么信息都不能提供，如果我们只看不相邻的两次询问，也什么信息都不能提供。关键就是在于我们要利用好相邻两次询问最少有一次是真的，来看 相邻的两次询问能带来什么信息。

不过，在分析这个之前，我先介绍一个关键的思想：对于一次 S 的询问：

• 交互器回答 Yes：说明本轮交互器告诉我们 x 在 S 中。
• 交互器回答 No：说明本轮交互器告诉我们 x 在 \complement_US 中。

请注意这里对回答 No 的思考方式，我们不要直接思考 x 不在 S 中，这样会越思考越乱。正确想法应该是：对于一次 \boldsymbol S 的询问，无论交互器的回答是什么，它提供我们的信息都是 \boldsymbol x 在某个集合 \boldsymbol{S'} 里，只是回答 Yes 代表 S' = S，回答 No 代表 S' = \complement_US。这个想法的改变对于解题非常有帮助，后面大家会深刻感受到这点。

现在来看相邻的两次询问能带来什么信息。假设我们先询问一次，得到了 x \in S'（注意，根据上面的思想转变，这里 x \in S' 已经同时蕴含了交互器的两种回答），再询问一次，得到了 x \in T'，我们能得到什么信息？

这两次询问的结果在交互库不骗人时，保证均是真的，我们可以得到 x \in S’ 且 x \in T' 为真，即 x \in S’ \cap T'。

而在交互库骗人时，这两条信息的真假并不确定，只保证至少有一个是真的，即：x \in S' 或 x \in T' 为真。这样我们得到的信息是 x \in S' \cup T'。请记住这个结论： 本题中相邻的两次反馈为 \boldsymbol{x \in {S'}} 和 \boldsymbol{x \in {T'}} 的询问，得到的确定性信息为 \boldsymbol{x \in {S' \cup T'}}。这个结论尤为重要，是本题根据询问回答推出确定信息的基本方法。

总结一下：通过两次相邻的，反馈分别为 x \in S' 和 x \in T' 的两次询问，可确定 x \in S' \cup T'，将目标范围 U 缩小到 S’ \cup T'，换句话说，\complement_U(S' \cup T') = \complement_US' \cap \complement_UT' 可以从全集中被删除了。

回想我们的目标，我们期望用这两次相邻的询问，让目标范围降低地尽可能多。

先梳理思路：S' 和 T' 是由你的询问和交互器共同决定的，如果你决定做两次 S 和 T 的询问，交互器对这两种询问可能有四种不同的回答，而你显然无法事先预知交互器的回答，并且交互库自适应，所以 S' = S 或 S' = \complement_US，T' = T 或 T' = \complement_UT 组成的共四种可能中，你需要按照最坏情况作为“先问 S，再问 T”的目标范围缩小效果。然后，再探求什么样的 S 和 T 能使得这个目标范围缩小效果达到最高。

还是假设当前目标范围为 U，连续两次分别询问了 S 和 T，那么：

• 两次均回答 Yes，可以将目标范围进一步锁定到 S \cup T，也即 \complement_U\left(S \cup T\right) = \complement_U S \cap \complement_U T 可以被删去。
• 第一次回答 No，第二次回答 Yes，可以将目标范围进一步锁定到 \complement_U S \cup T，也即 \complement_U\left(\complement_U S \cup T\right) = S \cap \complement_UT 可以被删去。
• 第一次回答 Yes，第二次回答 No，可以将目标范围进一步锁定到 S \cup \complement_UT，也即 \complement_U\left(S \cup \complement_UT\right) = \complement_US \cap T 可以被删去。
• 两次均回答 No，可以将目标范围进一步锁定到 \complement_US \cup \complement_UT，也即 \complement_U\left(\complement_US \cup \complement_UT\right) = S \cap T 可以被删去。

上面的等号用的是德摩根定律化简，读者处理集合问题应当熟练应用。

这里我们应该按照最坏情况讨论，即如果我们钦定询问第一次询问 S，第二次询问 T：

• 最坏情况下，目标范围的大小至少会缩小到 \max\left(\left|S \cup T\right|, \left|\complement_U S \cup T\right|, \left|S \cup \complement_UT\right|, \left|\complement_US \cup \complement_UT\right|\right)。
• 最坏情况下，目标范围的大小至少会减少 \min\left(\left|S \cap T\right|, \left|\complement_U S \cap T\right|, \left|S \cap \complement_UT\right|, \left|\complement_US \cap \complement_UT\right|\right)。

当然，上面两条是等价的，这里我选择第二条处理（选第一条处理也很好做，读者可以自行尝试）。

我们的目标是最大化缩小效果，也即选定 S 和 T，最大化 \min\left(\left|S \cap T\right|, \left|\complement_U S \cap T\right|, \left|S \cap \complement_UT\right|, \left|\complement_US \cap \complement_UT\right|\right)。

对于集合问题我们可以考虑绘制韦恩图。

设上面黄色区域代表的集合为 S_1，大小为 a；紫色区域代表的集合为 S_2，大小为 b；棕色区域代表的集合为 S_3，大小为 c；白色区域代表的集合为 S_4，大小为 d。

容易发现，S_1，S_2，S_3，S_4 互不相交，并集为 U，即 a +b +c + d = |U|。

观察目标最值的四项：\min\left(\left|S \cap T\right|, \left|\complement_U S \cap T\right|, \left|S \cap \complement_UT\right|, \left|\complement_US \cap \complement_UT\right|\right)。

我们可以发现，S_1 = S \cap \complement_UT，S_2 = \complement_US \cap T，S_3 = S \cap T，S_4 = \complement_US \cap \complement_UT，也即目标最值中的四项恰好和韦恩图中的四个小区域是完全对应的。

那么目标最值其实就是 \min(a, b, c, d)，我们期望它最大。