题解：P12797 [NERC 2022] Hot and Cold

· · 题解

题目传送门

思路

神秘方言题。

显然是二进制拆分的思路。题目要求 64 次询问出结果。那么由于范围最大达 10^6，则每次询问通过 3 \times \log(10^6)\approx3 \times 20=60 可知只能询问 3 次。所以剩下有 4 次机会来确定方言。

我们询问 3 次问出词义，通过询问 3 次分别为 (0,0)，(1,1)，(0,0)，确定 (1,1) 和 (0,0) 离目标点的关系。

若已经找到，则停止。该步骤之后每次询问之后都要加，不再赘述。

若没找到，即结尾不是感叹号，则如果两次字符串结果相同，则答案一定在 (1,0) 和 (0,1) 之间，直接询问即可。

否则我们知道答案一定不是 (1,0) 或 (0,1)，则 (1,1) 询问的结果一定是更近，(0,0) 询问的结果一定是更远。

所以 3 次可以确定词义。

接下来，每次缩小范围只能询问 3 次，如果可以询问 4 次可能这题就是个绿。我们把 x 和 y 的操作一起算，就可以减掉分开算的多余操作。

询问当前范围中心点，在询问中心点上面一个点（相距 1 单位长度），然后在询问中心点右上角的那个点，可以确定下来目标点在中心点哪个方向。即：\ 记此时的范围是 (lx,ly) 到 (rx,ry)，则定义 midx=\frac{lx+rx}{2},miny=\frac{ly+ry}{2}，(midx,midy) 即为中心点。再询问 (midx,midy+1)，可以确定目标点在中心点的上面还是下面。我们假设是在上面，下面同理。然后询问 (midx+1,midy+1)，则可以确定目标点是在中心点上方的左边还是右边。

所以 3 次操作可以把 x 和 y 均砍一半，则总的询问次数为 3 \times \log(10^6)\approx3 \times 20=60，加上确定词义的 3 次，共 63 次，可以通过。

\text{AC} 记录。