自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:48:43，当前版本为作者最后更新于2023-07-24 17:05:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

出题人题解实际上在正确性这一块完全是乱说明的，没有任何逻辑，纯粹是名词堆砌：

• 计算信息熵变化不能对事件进行捆绑

• 每次询问后信息熵不一定会下降那么多，甚至不一定会下降

• 信息熵下降与接近正确答案没有任何关系，概率更集中不一定会集中在正确答案上

下面给出一种我想的一种正确性的合理说明方式。

贝叶斯公式可以如下理解：有若干件不同的事 $A_1,A_2,\cdots, A_n$，它们之中必定发生且只发生一件。设 $A_i$ 的发生概率为 $p_i$，$A_i$ 发生时 $B$ 的发生概率为 $q_i$，则 $B$ 发生时 $A_i$ 的发生概率，即为将 $p_iq_i$ 进行归一化（全部乘以特定值使得和为 $1$）后的结果。

为了简化下面的说明，用 $p$ 代表原题中的 $p\%$。

对于此题来说，可以定义 $1\le i\le n$ 都对应一个权值 $a_i$，初始 $a_i=1/n$。假设询问 $y$ 后返回了 <，那么将 $a_y$ 归零，对所有 $i<y$ 将 $a_i$ 乘上 $p$，对所有 $i>y$ 将 $a_i$ 乘上 $1-p$。这样，任何时刻，$a_i$ 都代表此刻结果是 $i$ 的“概率权值”，归一化后即为实际概率。

直到答对之前，每一次询问后，$a_x$ 将以 $p$ 的概率乘以 $p$，$1-p$ 的概率乘以 $1-p$，即 $\ln a_x$ 将以 $p$ 的概率增加 $\ln p$，$1-p$ 的概率增加 $\ln (1-p)$。

相信大家都听说过大数定律，即一个随机变量多次试验后的均值总是会趋于它的期望。它有一个更“精确”的版本，即中心极限定理：如果随机变量 $X$ 的期望是 $E$，方差是 $\sigma^2$，则 $n$ 次试验求平均后，结果的分布会趋向于正态分布 $N(E,\sigma^2/n)$。

应用在上面即说明，在 $q$ 次询问没猜出来后，

$\dfrac{\ln a_x-\ln(1/n)}{q}\sim N(p\ln p+(1-p)\ln (1-p),p(1-p)\ln^2(1/p-1)/q)$

现在已经搞清楚了概率权值的分布。既然在求出最终结果前需要归一化，那么下面就研究归一化的分母，即 $\sum a_i$。

我们希望最终能够以大概率选中答案，即 $a_x/\sum a_i$ 尽量大，那么应该让归一化的分母尽量小。

以贪心策略来说，在每一步询问时，应该让 $\max(p\sum\limits_{iy}a_i,(1-p)\sum\limits_{iy}a_i)$ 尽量小。</p>

显然，将 $y$ 选为 $\sum\limits_{i<y}a_i\le \sum a_i/2$ 与 $\sum\limits_{i<y}a_i>\sum a_i/2$ 的交界点时，$\sum\limits_{iy}a_i\le \sum a_i/2$，那么上面的式子就不会超过 $\sum a_i/2$。

如此一来，就能保证每次 $\sum a_i$ 至少减少一半。

现在假设已经按照上面的方法进行了 $q$ 次询问且没猜出来，此时 $\sum a_i\le 2^{-q}$。可以发现， 一旦 $a_x> \sum a_i/2$，下一次询问必定会询问 $x$，即猜中，那么下一次猜中的概率至少为 $a_x> 2^{-q-1}$ 的概率。

根据上面的正态分布结论，将 $p,n,q$ 带进去计算可以就可以得到一个单点通过概率的下界了。

现在就是把各 Subtask 的数据范围一个一个带进去看了。可以使用 WolframAlpha。

以最后一个 Subtask 为例，带入 $p=0.49,n=10^{18},q=249999$（需要保留最后一次回答）。这里舍入误差相对比较大，考虑移一些项，记 $t=q\left(\dfrac{\ln a_x-\ln (1/n)}{q}-(p\ln p+(1-p)\ln (1-p))\right)$，则 $t\sim N(0,qp(1-p)\ln^2(1/p-1))=N(0,99.9863)$，需要求的概率是 $P(a_x>2^{-q-1})=P(t>-9.24975)=82.2527\%$。那么，通过整个 Subtask 的概率至少为 $(10p^3(1-p)^2+5p^4(1-p)+p^5)|_{p=82.2527\%}=95.7926\%$。

可以算出来通过各个 Subtask 的概率依次至少为 $100\%,100\%,100\%,100\%,100\%,98.751\%,96.39\%,95.9417\%,95.8114\%,95.7926\%$（第一个以后的 $100\%$ 是失败概率低于输出精度了），乘起来也有 $83.8166\%$。而且实际上这些概率被低估了很多，有可能不需要等到最后一次询问就已经猜到了，实际的通过概率可能有 $99\%$ 以上。

由此，就得到了一个正确性有保证的做法。

具体实现来讲，使用动态开点线段树即可。为了防止概率权值小于实数精度，每次修改时立即归一化即可，整体乘一个常数并不会改变上面的论证的正确性。实现起来没那么麻烦就不附代码了。