[CF2150E2] Hidden Single (Version 2) 题解

好难绷的题。

你也许需要先会 E1。猜你喜欢：[CF2150E1] Hidden Single (Version 1) 题解

看到题后似乎只能想到分治，于是想想该怎么分治。

考虑对于 中的每个 ，判断它是不是答案。考虑 ，设中点为 。我们尝试找出 在当前区间内的分布情况（左区间或右区间）。总共分三类情况：

• 所有 均出现在左区间：有 的概率，需要询问 次。
• 所有 均出现在右区间：有 的概率，需要询问 次。
• 两个 分别出现在左区间和右区间：有 的概率，需要询问 次，可以结束递归。

所以一次递归的期望询问次数就是 。若当前区间长度为 则说明 是答案。容易算出，当 比较大时，对于单个 的总期望询问次数是大约 。再剪剪枝，找到答案之后直接返回，总期望询问次数是 ，上限是 。为了尽量达到期望询问次数，你需要创建两个随机的映射，以实现打乱数组并随机离散化的效果。可惜，这还是过不了 E2，甚至连 E1 都过不了。（E1 过不了的原因是，当 较小时，对于单个 ，实际询问次数会较大。）

不过我们先不讨论 E1，只讨论 较大的情况。考虑优化，发现对于单个 ， 的期望询问次数似乎很难再优化，于是能不能减少需要询问的 的数量呢？又如何减小？

这个时候你想到，E1 一定是有它存在的意义的。 想想 E1 的一次递归做了些什么，它花了 的期望询问次数。再考虑一次递归后产生的新区间有什么性质，发现新区间中，期望 个数出现了两次。于是考虑对新区间采用上文中提到的做法。因为我们只关注出现了两次的数，而不关注仅出现了一次的数（根据 E1 做法的性质，仅出现了一次的数一定不是答案），所以需要询问的 的期望数量就只剩 了。

这样，后半部分期望询问次数就是 ，上限是 。前半部分的期望询问次数相对稳定，所以总询问次数的上限就大约是 ，可以通过 E2。

提交记录