[CF2150E1] Hidden Single (Version 1) 题解

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

考虑 ，设中点为 。假定当前区间内存在答案，并且我们知道 中的每个 在这个区间内的出现次数 。特别地，对于答案 ，我们不得不钦定 。对于 中的每个 ，我们尝试找出它在当前区间内的分布情况（左区间或右区间）。于是根据 分讨：

• ：需要 次询问。直接跳过。
• ：需要 次询问。只需要询问左区间，即可得到它属于左区间还是右区间。
• ：最多需要 次询问。询问一次左区间，询问一次右区间，即可得到下面三种情况之一：
  • 两个 均出现在左区间
  • 两个 均出现在右区间
  • 两个 分别出现在左区间与右区间

容易发现，对于当前区间，我们最多进行 次询问，额外加 是因为我们钦定了 。这样，我们可以统计出左区间的元素数量与右区间的元素数量。按理来讲，一个区间的元素数量就应该是这个区间的长度，但是正是因为我们钦定了 ，所以在统计过程中，我们会把 视作两个元素，这就会导致统计的数量与实际冲突，而产生冲突的区间则正是包含 的区间。于是，我们只需要利用不包含 的区间更新 ，再递归处理包含 的区间即可。当区间内有且仅有一个元素时，这个元素就是 。

因为每次递归区间长度都要减半，所以总询问个数大约是 。由于取整带来的一点误差，题目还贴心地多给了 次询问，比较充足。

如果你还想在 E1 的基础上稍作优化，那么你可以创建一个随机的映射以实现打乱原数组的效果。这样，对于 的情况，期望询问次数就是 次，但是这优化不大，也过不了 E2。

代码实现是容易的，按照题解模拟即可。

猜你喜欢：[CF2150E2] Hidden Single (Version 2) 题解