1746E1 Joking (Easy Version) && 1746E2 Joking (Hard Version)
给定 \(n\) ，你需要在至多 82 / 53 次询问和 2 次猜测后回答出 \(x\) 的值。
询问：给定一个集合，回答 \(x\) 是否属于集合。保证相邻 \(2\) 次询问中至少有 \(1\) 次询问没有说谎。
猜测：回答 \(x\) 的值，必须在 \(2\) 次猜测中猜对。
\(n\leq 10^5\) ，交互库自适应。
首先考虑一个较多次数的方案：将每 \(2\) 次询问分成一组，则可以将整个全集 \(U\) 分成 \(4\) 个部分： \(S_{0,0},S_{0,1},S_{1,0},S_{1,1}\) ，表示是否在第 \(1\) 次询问的集合中，是否在第 \(2\) 询问的集合中。由于交互库不能连续说谎，所以 \(2\) 次都不在这个区间内的集合将被删去。
| 询问 \(1\) 结果 | 询问 \(2\) 结果 | 排除的集合 |
|---|---|---|
| YES | YES | \(S_{0,0}\) |
| YES | NO | \(S_{0,1}\) |
| NO | YES | \(S_{1,0}\) |
| NO | NO | \(S_{1,1}\) |
所以在这种情况下，最优的策略是让 \(\min\{|S_{0,0}|,|S_{0,1}|,|S_{1,0}|,|S_{1,1}|\}\) 尽可能大，所以取到 \(\frac{|S|}{4}\) 时最靠谱，每 \(2\) 次询问可以减少 \(\frac{1}{4}\) 的集合大小。
然后就是只有 \(3\) 个数的情况，在这种情况下有很多构造方案使得在 \(4\) 步以内可以再排除一个，这里提供一个比较好像的：设这三个数是 \(a,b,c\) 。
先分别询问 \(\{a,b\}\) 和 \(\{b,c\}\) ，则
| 询问 \(1\) 结果 | 询问 \(2\) 结果 | 排除的元素 |
|---|---|---|
| YES | YES | \(\{a,b,c\}\setminus (\{a,b\}\cup\{b,c\})=\varnothing\) |
| YES | NO | \(\{a,b,c\}\setminus (\{a,b\}\cup\{a\})=c\) |
| NO | YES | \(\{a,b,c\}\setminus (\{c\}\cup\{b,c\})=a\) |
| NO | NO | \(\{a,b,c\}\setminus (\{c\}\cup\{a\})=c\) |
对于两个 YES 的情况还要进一步讨论，首先询问 \(\{a\}\) ：
| 询问 \(3\) 结果 | 排除的元素 |
|---|---|
| YES | \(\{a,b,c\}\setminus (\{b,c\}\cup\{a\})=\varnothing\) |
| NO | \(\{a,b,c\}\setminus (\{b,c\}\cup\{b,c\})=a\) |
对于三个 YES 的情况还要进一步讨论，询问 \(\{c\}\) ：
| 询问 \(3\) 结果 | 排除的元素 |
|---|---|
| YES | \(\{a,b,c\}\setminus (\{a\}\cup\{c\})=b\) |
| NO | \(\{a,b,c\}\setminus (\{a\}\cup\{a,b\})=c\) |
最后直接猜测 \(2\) 个剩下的元素即可，这样的询问次数是 \(2\log_{\frac{4}{3}}n+4\) 的。
同时，最后的 \(4\) 步也启示了另一个做法：直接将集合分成 \(3\) 个部分，每 \(4\) 步为一个周期进行循环，询问次数 \(3\log_{\frac{3}{2}}n\) 。
在 \(n=10^5\) 时上方的算法略优于下方的算法。（但是不知道为什么它们在 \(n=10^5\) 处的取值都 \(>82\) 但是能过，大概是卡不满吧）
接下来考虑如何继续优化算法。To be continue……
原文地址：http://www.cnblogs.com/zhouzizhe/p/16913151.html
