题解：P12797 [NERC 2022] Hot and Cold

· · 题解

首先考虑如果我们知道每个单词是什么含义，这时该怎么做。

先从一维的情况开始考虑，不难发现可以二分。

在当前区域内，每次取中点和中点右面的点，如果得到的回复是“Closer”说明在中点右面，反之则在中点左面。

一个维度的二分次数为 2 \times \log_210^6，是 40 次。对两个维度分别做二分，需要的次数是 80。

这样做是对的，但超过了 64。原因是我们对两个维度分别做二分，对一个维度二分时会浪费另一个维度的信息。我们考虑对两个维度同时做二分。

取平面中点，再取中点上方的点，如果回复“Closer”说明宝藏在中点上方，反之在中点下方。然后取中点右上方的点，如果回复“Closer”说明在中点右侧，反之则在中点左侧。

这样做只需要取 3 个点就对两个维度同时进行了二分。最后需要的次数是 60，小于 64 次，非常成功。

现在我们并不知道每个单词是什么含义，我们考虑如何知道。

带感叹号的一定是“Found!”，第一个出现的一定是“Not Found”。我们只需要区分“Closer”“Further”和“At the same distance”即可。

取 (0, 0) 作为第一个点，取 (1, 1) 作为第二个点，这时得到的回复要么是“Closer”要么是“At the same distance”。

然后我们再取回 (0, 0)，如果得到的回复和刚才不同，那么刚才的回复是“Closer”，现在的回复是“Further”，那个没出现的回复就是“At the same distance”。这时用了 3 次询问，加上刚才的 60 次，总共 63 次，没有超过 64。

如果相同的话，说明这个回复是“At the same distance”，那么宝藏一定在 (0, 1) 或 (1, 0) 的位置，分别询问即可。