P17165 [CEOI 2026] Treasure Hunt

题目附件来自 [QOJ](https://qoj.ac/problem/18999)。

你正在一片巨大的 $N\times N$ 方格区域中，借助一个魔法罗盘寻找失落已久的宝藏。场地中共有 $K\le 3$ 个宝箱，分别藏在互不相同的格子里。你的目标很简单：找到所有宝箱！ 当你把罗盘放在某个格子上时，它会寻找仅通过向左、向上、向右、向下移动而到达某个宝箱的最短路径，也就是寻找曼哈顿距离最近的宝箱。随后，罗盘会显示最短路径第一步的方向。如果有多个合法的第一步可以通向某个最近的宝箱（也可能通向多个最近的宝箱），罗盘会返回所有这些方向。如果当前格子中有宝箱，罗盘则会指出这一点。 每当你找到一个宝箱时，你会取出其中的宝物，但无法移走宝箱，因为它太重了。罗盘不知道某个宝箱是满的还是空的，它总会指向距离最近的宝箱，无论该宝箱为空还是装有宝物。 请尝试用尽可能少的罗盘询问找到所有宝箱的位置。 ### 任务 这是一道交互题。在每个测试用例（即程序的每次运行）中，你的程序都需要完成若干次寻宝。你应当使用主办方提供的库与评测程序交互。该库包含以下声明： - `void NextHunt(int &N, int &K)`——调用此函数以开始下一次寻宝。该函数会将网格大小写入变量 $N$，并将宝箱数量写入 $K$。如果本次程序运行中已经没有需要完成的寻宝，该函数会将 $N$ 和 $K$ 都设为 $-1$；此时，你应当立即以退出码 $0$ 终止程序。请注意，你可以在尚未找到当前寻宝中的全部宝箱时调用此函数，例如，你只打算争取部分分数时可以这样做。 - `enum { TREASURE = 0, DIR_RIGHT = 1, DIR_UP = 2, DIR_LEFT = 4, DIR_DOWN = 8 };`——这些常量用于 Query 函数的返回值，详见下文。 - `int Query(int x, int y)`——如果坐标为 $(x,y)$ 的格子中有宝箱，此函数返回 TREASURE；否则，它会返回 DIR_RIGHT、DIR_UP、DIR_LEFT 和 DIR_DOWN 中一个或多个常量之和，以表示将罗盘放在格子 $(x,y)$ 上时返回的移动方向。坐标 $x$ 和 $y$ 必须是 $0$ 到 $N-1$ 之间的整数。（注意：在本题中，$y$ 坐标从上向下递增。） 当 NextHunt 将 $N=K=-1$ 后，程序不得再次调用 NextHunt 或 Query；在第一次调用 NextHunt 之前，程序也不得调用 Query。如果程序违反这些限制，单次寻宝中发起超过 $1000$ 次询问，或者调用 Query 时传入了越界的 $x$ 和/或 $y$，该库将终止程序，并使当前测试用例得到运行时错误（RTE）的评测结果。 如果你曾至少一次询问到某个宝箱所在的格子，就认为该宝箱已被找到。如果程序在找到当前寻宝的所有宝箱之前调用 NextHunt，这不会被视为错误，但会影响程序得分，详见下文的计分方式。 要使用该库，程序应包含头文件 `treasurehuntlib.h`： ```cpp #include "treasurehuntlib.h" ``` 你可以在此处下载该头文件：`treasurehuntlib.h`。 为了帮助你开发解决方案，此处还提供了该库的一个简单实现：`treasurehuntlib-public.cpp`。要将它与程序一起编译，只需把它的文件名作为参数传给编译器。例如： ```cpp g++ foo.cpp treasurehuntlib-public.cpp ``` 这里，`foo.cpp` 是包含你的解决方案的文件名。 除上述声明外，`treasurehuntlib-public.cpp` 中的实现还支持一个名为 `void InitFromFile(const char *fileName)` 的函数。该函数会从文件中读取一系列寻宝数据，使你可以在这些数据上进行游戏，而不是由该实现自行随机生成寻宝数据。你可以在 `treasurehuntlib-public.cpp` 文件中找到更多细节。 评测服务器会使用该库的另一种实现，因此你不应对其具体工作方式作出任何假设。不过，你可以假定，除上文列出的 NextHunt、Query 和五个常量外，该实现不会向全局命名空间中引入任何其他声明。 你的代码不得从标准输入读取，也不得向标准输出写入，因为评测服务器上的库实现会使用它们与评测环境的其他部分通信。

无

无

### 样例 | 调用 | 返回值 | |:-:|:-:| | NextHunt($N$, $K$) | $N=4$，$K=1$ | | Query($2$, $0$) | DIR_DOWN $+$ DIR_RIGHT $=9$ | | Query($3$, $1$) | DIR_DOWN | | Query($3$, $2$) | TREASURE | | NextHunt($N$, $K$) | $N=-1$，$K=-1$ | ### 限制条件 - $2\le N\le 10^6$ - $1\le K\le 3$ - 在程序的单次运行中，寻宝次数至多为 $100\,000$。 - 在单次寻宝中，最多可以发起 $1000$ 次询问。 - 评测系统不具有自适应性。 ### 子任务 - 子任务 $1$（$10$ 分）：$K=1$ - 子任务 $2$（$30$ 分）：$K=2$ - 子任务 $3$（$60$ 分）：$K=3$。 ### 计分方式 一个子任务可能包含多个测试用例（即程序运行多次），而每个测试用例又可能包含多次寻宝。计分时，同一子任务中的所有寻宝会合并评估，而不考虑它们原本如何分布在不同测试用例中。对于第 $i$ 次寻宝，记网格大小为 $N_i\times N_i$，宝箱数量为 $K_i$，程序发起的询问次数为 $Q_i$，程序找到的宝箱数量为 $F_i$。再以 $S$ 表示该子任务的总分。程序在该子任务中获得的分数如下： - 如果程序每次都找到了所有宝箱，即对所有 $i$ 均有 $F_i=K_i$，则得分取决于 $t_i=\dfrac{Q_i}{\lceil\log_2N_i\rceil}$： $$\begin{aligned} \frac{S}{2}+\frac{S}{2}\cdot\min_i f(t_i),\qquad f(t_i)&= \begin{cases} 1, & t_i\le 11,\\ 1-(t_i-11)/9, & 11\le t_i\le 20,\\ 0, & t_i\ge 20. \end{cases} \end{aligned}$$ - 如果程序并非每次都找到了所有宝箱，即存在某个 $i$ 满足 $F_i