题解：P17486 第四槐安通道

Librarius · 2026-09-25 21:14:27 · 题解

注意到我们可以在四次询问内确定前四个数的状态。之后就相当于我们可以选择 1/2/3 个数询问和了。

考虑对未确定的变量维护 B 种可行状态（例如，我们可能会认为 \{(0,0,0),(1,0,1),(1,1,0),(1,1,1)\} 是当前可行的），每次若可行状态数过小就加入一个新变量。每次询问时找到在可行状态中信息熵最大的询问即可——例如，假若我们问出了和为 2，上述可行列表就会变为 \{(1,0,1),(1,1,0)\}，注意到我们此时又确定了 a_1 的取值！接下来因为列表太小了，我们又会加入一个元素，可行变为 \{(0,1,\color{red}{0}\color{black}),(1,1,\color{red}{0}\color{black}),(0,1,\color{red}{1}\color{black}),(1,1,\color{red}{1}\color{black})\}。

官方数据中最差的点需要 439945 次询问。实测大约询问次数在 0.543n 左右，当然是用随机数据测出来的，但因为本题保证交互库不会自适应，所以其实输入只取决于 \sum a_i，本算法在 \sum a_i=\Omicron(\frac{n}{2}) 的时候，也就是，数据随机生成的时候跑的最差——这也是可以理解的，因为此时输入数据的信息熵最大。

本题比较卡常，可能需要一点实现技巧才能通过。