CF1746E Joking

CF1746E1

CF1746E2

两个比较趣味的题,赛时 rush 出了 E1(虽然有较多不必要的罚时),使得我重新获得了我的 GM 账号。(见 CF1738G

本题大概和 IMO 的一个题的背景是类似的。

为了避免一些误会,接下来会用 YES/NO 表示询问时交互库的回答,“正确“ ”错误“ 表示交互库的回答是否在开玩笑(?)

E1

首先发现有出错的情况不能直接转化为不出错的情况。但是思路是对的:还是应该用一个集合维护经过了前面的询问,有哪些数可能是答案。由于交互库是自适应的,意味着其他乱搞是不可能通过的。

由于相邻的必然有一个是对的,考虑将两次相邻询问放到一起考虑。

将当前的集合等分成四组:\(S_1,S_2,S_3,S_4\),第一次询问 \(S_1\or S_2\),第二次询问 \(S_2\or S_3\),那么如果两次得到的答案是 No+Yes 的话,说明答案不可能在 \(S_1\) 里面(否则两次得到的回答都是错的)。因此可以使用两次询问将原问题的规模变为原来的 \(3\over 4\)

如果最后剩下的数小于 \(3\),可以直接去回答,但是如果剩下的数等于 \(3\) 的时候,并不能用前面的策略,如何实现 \(3\)\(2\)?。

假如剩下的是 \(v_1,v_2,v_3\),那么先问 \(v_1\),如果是 YES,就再问 \(v_2\),如果也是 YES,说明答案一定在 \(\{v_1,v_2\}\) 中。如果 \(v_2\) 是 NO,说明答案不可能是 \(v_2\),一定在 \(\{v_1,v_3\}\) 中。

如果 \(v_1\) 是 NO,就再问一次 \(v_1\),如果是 YES 就按照上面说的做,否则答案不可能是 \(v_1\),一定在 \(\{v_2,v_3\}\) 中。

这样我们可以在七十几次询问里得到答案,就可以把 E1 过掉了。

E2

可以发现,刚刚介绍的做法只利用了“同一组内两个数至少有一个是正确的”,原题中“任意相邻的询问都至少有一个是正确的”没有被完全利用。然后看到了一个做法,比官方题解不知道高到哪里去了。

维护两个集合 \(S\)\(T\)\(S\) 表示如果上一个询问的答案是正确的, 有哪些数是可能的答案;\(T\) 表示如果上一个询问的回答是错误的, 有哪些数是可能的答案。

每次把 \(S\) 等分成 \(S_1,S_2\)\(T\) 等分成 \(T_1,T_2\),询问 \(S_1\cup T_1\),如果回答是 YES,那么答案在 \(S_1\cup T_1\) 当且仅当本次回答是正确的,答案在 \(S_2\cup T_2\) 当且仅当本次回答是错误的。那么显然答案不可能在 \(T_2\) 里。(因为这样的话本次回答和上一次回答都是错误的)

此时可以更新 \(S,T\)。具体来说,\(S_1\cup T_1 \rightarrow S,S_2\rightarrow T\)。如果本次回答是 NO 情况也类似。

初始条件为 \(S=U=[1,n],T=\emptyset\)。每次询问可以排除掉 \(\frac 1 2 |T|\) 个数,比前面的做法更优。虽然不太能分析,总之能过


后记:我场上做 E1 的时候,是这样处理 \(n=3\) 的情况的:询问四次:\(\{v_1\},\{v_1,v_2\},\{v_1,v_2\},\{v_1\}\),如果回答是 0110,那么就是 \(\{v_1,v_2\}\),否则是 \(\{v_2,v_3\}\)。这个显然是不对的,但是居然没有 FST,太魔幻了。


CF1746E Joking
https://shmilyty.cf/cf1746e/
作者
ShmilyTY
发布于
2022年10月16日
许可协议