logoChat01.ai

下面这是CEOI2026 Day1T3的题面和官方题解。关于这道题的K=3的部分，题解没有描述得很详...

Créé le : 30 juillet 2026

Répondu en utilisant GPT-5.6 Thinking par Chat01

Question

下面这是CEOI2026 Day1T3的题面和官方题解。关于这道题的K=3的部分，题解没有描述得很详细，尤其最后如何从17logn优化到11logn。前面的部分（K=1、K=2、K=3的17logn）我都已经完全理解了，现在需要你参照题解帮我思考具体如何优化到11logn，给我讲明白。

Treasure Hunt（寻宝）

时间限制：8 s8\ \text{s} 内存限制：256 MiB256\ \text{MiB}

题目描述

你需要在一片巨大的 N×NN \times N 方格场地中，借助一个神奇的罗盘寻找失落的宝藏。场地内共藏有 K≤3K \le 3 个宝箱，分布在互不相同的格子中。你的目标是找出所有宝箱的位置。

将罗盘放置在任意格子上时，它会仅通过上下左右四向移动，计算通往宝箱的最短路径（即按曼哈顿距离找出最近的宝箱），并指示出第一步可行的所有方向。如果存在多个方向都能通向最近的宝箱（或多个最近宝箱分别对应不同方向），罗盘会返回全部可行方向。若当前格子本身就存放着宝箱，罗盘会直接指示该状态。

每当你找到一个宝箱，可以取走其中的宝物，但无法移动宝箱——它的重量过大。罗盘并不知道宝箱是否已被清空，它始终会指向距离最近的宝箱，无论宝箱内部是否还有宝物。

请你使用尽可能少的罗盘查询次数，确定所有宝箱的位置。

任务

本题为交互题。在每个测试用例（即程序的一次运行）中，你的程序需要完成多轮寻宝。你需要通过主办方提供的交互库与评测程序进行交互，该库包含以下接口声明：

  • void NextHunt(int &N, int &K)：调用该函数以开启新一轮寻宝。函数会将场地边长写入变量 NN，宝箱数量写入变量 KK。若当前运行中已无剩余寻宝轮次，函数会将 NN 和 KK 均设为 −1-1，此时你应当以退出码 00 正常结束程序。注意：你可以在找完当前轮次全部宝箱前就调用该函数，例如仅尝试获取部分分数时。

  • enum { TREASURE = 0, DIR_RIGHT = 1, DIR_UP = 2, DIR_LEFT = 4, DIR_DOWN = 8 };：这是 Query 函数返回值对应的常量（见下文）。

  • int Query(int x, int y)：若坐标 (x,y)(x,y) 处的格子包含宝箱，函数返回 TREASURE；否则返回若干方向常量的和，包含 DIR_RIGHT、DIR_UP、DIR_LEFT、DIR_DOWN 中的一个或多个，表示罗盘在该格子上返回的所有可行移动方向。坐标 xx 和 yy 必须是 00 到 N−1N-1 之间的整数。注意：本题中 yy 坐标从上到下递增。

当 NextHunt 返回 N=K=−1N=K=-1 后，程序不得再调用 NextHunt 或 Query；在第一次调用 NextHunt 之前，也不得调用 Query。若程序违反上述约束，或单轮寻宝内查询次数超过 1000 次，或调用 Query 时传入的坐标越界，交互库将直接终止程序，并判定该测试用例为运行时错误（RTE）。

只要你至少查询过一次宝箱所在的格子，即视为该宝箱已被找到。若程序在找完当前轮次全部宝箱前就调用了 NextHunt，不会被判定为错误，但会影响最终得分（详见评分规则）。

使用该交互库时，程序需包含头文件：

cpp
#include "treasurehuntlib.h"

你可以下载头文件 treasurehuntlib.h 进行本地开发。
为辅助调试，我们还提供了交互库的公开实现 treasurehuntlib-public.cpp，将其与你的代码一同编译即可，示例编译命令：

g++ foo.cpp treasurehuntlib-public.cpp

其中 foo.cpp 为你的解法代码文件名。

公开版交互库还额外提供了 void InitFromFile(const char *fileName) 函数，可以从文件中读取多组寻宝数据进行测试，而非使用随机生成的数据，更多细节可查看 treasurehuntlib-public.cpp 源码。

评测服务器上会使用不同的库实现，因此你不应对库的具体实现逻辑做任何假设；但你可以认为，除了上述 NextHunt、Query 与五个常量之外，库不会污染全局命名空间。

你的程序不得读写标准输入输出，评测环境下的交互库会占用标准输入输出通道与评测系统通信。

数据约束

  • 2≤N≤1062 \le N \le 10^6
  • 1≤K≤31 \le K \le 3
  • 程序单次运行中，最多包含 100 000100\,000 轮寻宝
  • 单轮寻宝中，最多可进行 10001000 次查询
  • 评测系统为非自适应

子任务

  • 子任务 1（10 分）：K=1K = 1
  • 子任务 2（30 分）：K=2K = 2
  • 子任务 3（60 分）：K=3K = 3

评分规则

一个子任务可能包含多个测试用例（程序的多次运行），每个测试用例又可包含多轮寻宝。评分时，同一子任务下的所有寻宝轮次统一评估，与它们所属的测试用例无关。

对于第 ii 轮寻宝，设场地大小为 Ni×NiN_i \times N_i，宝箱总数为 KiK_i，你的程序使用的查询次数为 QiQ_i，成功找到的宝箱数为 FiF_i。记该子任务的满分为 SS，则程序在该子任务的得分按以下规则计算：

  • 若程序总能找到全部宝箱（即对所有 ii 满足 Fi=KiF_i = K_i），得分由 ti=Qi⌈log⁡2Ni⌉t_i = \dfrac{Q_i}{\lceil \log_2 N_i \rceil} 决定：

    S2+S2⋅min⁡if(ti)\frac{S}{2} + \frac{S}{2} \cdot \min_i f(t_i)

    其中函数 f(ti)f(t_i) 定义为：

    f(ti)={1,ti≤111−ti−119,11<ti≤200,ti>20f(t_i)= \begin{cases} 1, & t_i \le 11 \\ 1 - \dfrac{t_i - 11}{9}, & 11 < t_i \le 20 \\ 0, & t_i > 20 \end{cases}

  • 若程序未能找到全部宝箱（即存在 ii 使得 Fi<KiF_i < K_i），得分为：

    S2⋅min⁡iFiKi\frac{S}{2} \cdot \min_i \frac{F_i}{K_i}

换言之，找到全部宝箱即可获得一半基础分，另一半分数由查询次数决定。要获得满分，解法需要在不超过 11⌈log⁡2Ni⌉11\lceil \log_2 N_i \rceil 次查询内找出所有宝箱；当查询次数在 11⌈log⁡2Ni⌉11\lceil \log_2 N_i \rceil 到 20⌈log⁡2Ni⌉20\lceil \log_2 N_i \rceil 之间时，分数线性递减；若查询次数超过 20⌈log⁡2Ni⌉20\lceil \log_2 N_i \rceil，则仅能获得找到全部宝箱对应的基础分。
符号 ⌈⋅⌉\lceil \cdot \rceil 表示向上取整，即对 log⁡2Ni\log_2 N_i 的值向上取到最近的整数。

若按公式计算出的得分不是整数，将四舍五入至最近的整数。

若程序出现运行时错误，或未遵守上述交互协议，该子任务将得 0 分。因此，若仅希望通过找到部分宝箱获得部分分数，程序也应当通过调用 NextHunt 正常结束当前轮次。

样例

  • 调用 NextHunt(N, K)，返回：N=4, K=1N = 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=−1N = -1,\ K = -1

题解 - 寻宝（Treasure Hunt）

本题中，我们需要在一张极大的网格上寻找至多 k≤3k \le 3 处宝藏。你可以发起查询 (x,y)(x,y)，查询结果会给出：从 (x,y)(x,y) 出发、沿着某条最短路径行进能够抵达任意一处最近宝藏的方向构成的子集。本题的核心难点在于：寻找某一处宝藏时，其余宝藏可能造成误导。

子任务 1 寻找单个宝藏

寻找单个宝藏的问题比较简单。我们可以进行两次二分查找，分别确定宝藏所在列与所在行；事实上，我们甚至可以并行执行这两次二分。

子任务 2 寻找两处宝藏

我们需要找到第一处宝藏 TT，此时另一处宝藏会带来干扰。
如果并行搜索宝藏所在行与列，很容易被干扰信息误导。因此我们先确定列，再确定行。
我们可以从任意起点出发，根据首次查询的结果水平移动（不妨假设向右），并用二分查找定位某一处宝藏所在的列：我们二分查找一条分界线，分界线左侧格子向右可以找到宝藏，右侧相邻格子向右找不到宝藏；这条分界线对应的列内一定存在宝藏。

随后，我们使用相同思路在该列内向下（或向上）搜索。若向上搜索，则二分查找分界线：分界线下方格子向上可以找到宝藏，上方相邻格子向上找不到宝藏；该分界线处就是其中一处宝藏。

找到第一处宝藏 TT 后，我们沿着经过 TT 的对角线，划分出四个待搜索区域（右、左、上、下），在各个区域内独立搜索第二处宝藏 UU。
假设我们从第一处宝藏出发，沿同一行向右搜索。部分格子会一直指向左侧、朝向宝藏 TT，直到某个格子查询结果发生变化——这代表我们已经靠近第二处宝藏。我们可以使用倍增跳跃（步长取2的幂）定位到该变化发生的位置，再通过一次二分查找精确找到那个查询指向变为上/下（朝向第二处宝藏）的格子。由此确定第二处宝藏所在列，再在该列内二分查找得到所在行。

需要留意边界情况：两处宝藏位于同一行，或是两处宝藏分别处于某个正方形的对角顶点。

子任务 3 寻找三处宝藏

上文已经给出寻找第一处宝藏 TT 的方案，该方案在存在三处宝藏时依然适用。

搜索第二处宝藏时，可能在同一个区域（例如右侧）内存在多处宝藏。
在前文两处宝藏的方案中，我们从 TT 出发、沿同一行寻找包含第二处宝藏的列。现在我们需要提高精度，找到距离最近的宝藏。
设 BB 是第一处宝藏右侧、首个查询结果不单纯指向左侧的格子。我们已知：另外两处宝藏其中之一，一定落在以 BB 为中心的菱形范围内。我们可以在该行上，从 BB 向右二分查找，找到包含第二处宝藏的列，随后在该列上下二分，定位宝藏。

假设我们在点 CC 找到第二处宝藏，该点落在预期的菱形区域内。接下来我们可以从 CC 出发，在三个区域（上、下、右）内用类似方式寻找第三处宝藏。
如果没能找到，说明第三处宝藏位于某条线段上；但我们在点 DD 找到了另一处宝藏。我们可以从 DD 出发，在两个方向继续搜索——因为由点 BB 确定的菱形边界线段，最多与 DD 的两个搜索区域相交。最终宝藏位置由两条线段的交点确定。

需要小心一种特殊情形：TT 与 UU 在同一条对角线上。此时你有可能互相找到二者，但始终无法找到第三处宝藏。

这套方案最多需要 17log⁡n17\log n 次查询；我们还能进一步优化至最多 11log⁡n11\log n 次查询。
例如，利用前两处宝藏的方位特性，减少寻找最后一处宝藏所需的二分次数。其中一种优化思路：将第二处宝藏投影至网格边界，对这些投影点发起查询，从而快速判断第三处宝藏位于哪个区域，或是与 UU 在同一行/同一列。

Réflexion

Searched 1 website

Worked for 5m 59s

Réponse

先说最关键的一点：

**官方题解中的 17log⁡n→11log⁡n17\log n\to11\log n 并不是只靠“投影到边界”这一个技巧完成的。**公开的满分 model_code 中明确写着“11 log n”，但代码注释说，边界投影这个技巧本身是把已经优化到的 12log⁡n12\log n 再降到 11log⁡n11\log n。也就是说，完整过程应理解成：

17log⁡n  →更精细的摊还分析、利用线段信息  12log⁡n  →边界投影  11log⁡n.17\log n \;\xrightarrow{\text{更精细的摊还分析、利用线段信息}}\; 12\log n \;\xrightarrow{\text{边界投影}}\; 11\log n.

官方文字题解只写了最后一步的大意；下面是根据公开满分参考实现还原出的具体逻辑。(InfosBG)

1. 先统一记号

令

L=⌈log⁡2N⌉.L=\lceil\log_2 N\rceil.

已经找到第一个宝藏 AA、第二个宝藏 BB，最后一个宝藏记为 CC。

过一个点 BB 作两条对角线，将平面划成四个锥形区域：

R(B)={P:Px−Bx≥∣Py−By∣},L(B)={P:Bx−Px≥∣Py−By∣},D(B)={P:Py−By≥∣Px−Bx∣},U(B)={P:By−Py≥∣Px−Bx∣}.\begin{aligned} R(B)&=\{P:P_x-B_x\ge |P_y-B_y|\},\\ L(B)&=\{P:B_x-P_x\ge |P_y-B_y|\},\\ D(B)&=\{P:P_y-B_y\ge |P_x-B_x|\},\\ U(B)&=\{P:B_y-P_y\ge |P_x-B_x|\}. \end{aligned}

这就是题解所说的右、左、下、上四个区域。

把从已知宝藏 TT 向某个区域搜索的过程记为 FindNext(T,dir)。

参考实现中的查询预算大致可以这样记：

情形花费
该区域没有新宝藏至多 LL
找到一个宝藏，但没有留下第三个宝藏所在的对角线段至多约 3L3L
找到一个宝藏，同时得到第三个宝藏所在的一条对角线段至多约 4L4L
已知只剩一个宝藏，且已经确定它在哪个区域至多 2L2L

最后一种是“便宜版 FindNext”：不再需要倍增寻找第一个变化位置，因为我们已经通过边界查询获得了远端证据，只需要至多两次二分。参考代码也明确解释了 skipB=true 时可以从 3L3L 降到 2L2L。(oj.uz)

2. 从 17L17L 到 12L12L：不要给每一次搜索都收最坏费用

粗糙的 17L17L 算法会把很多区域搜索都当成完整的二维搜索来收费。但实际上有两个重要的摊还性质。

性质一：空区域只花 LL

从 AA 沿某个方向倍增，如果一直只看到指向 AA 的反方向箭头，直到边界仍然如此，就已经证明这个区域没有新宝藏。

这里不需要：

  • 找变化点后二分；
  • 再沿垂直方向二分。

所以一个失败方向只花一个倍增阶段，也就是至多 LL。

性质二：昂贵搜索会留下“线段证书”

如果一次 FindNext(A,dir) 花到了约 4L4L，却只实际找到 BB，那么它通常不会毫无收获地结束，而会额外得到：

第三个宝藏 CC 必须位于某条斜率为 11 或 −1-1 的对角线段 SS 上。

这就是题解中“如果找到的是更远处的 DD，则可以得到另一宝藏所在的一条线段”的信息。

有了第一条线段 SS 后，不应该重新从 BB 在三个方向各做完整搜索。只需选择一个包含 SS 的 BB-区域，再做一次特别便宜的搜索，得到第二条线段 S′S'，最后算

C=S∩S′.C=S\cap S'.

公开参考代码明确写道：已有一条线段后，只需 2L2L 得到第二条线段。(oj.uz)

于是这一类最坏情况为

2L⏟找到 A+3L⏟最多三个空方向+4L⏟找到 B 并得到线段+2L⏟得到第二条线段=11L.\underbrace{2L}_{\text{找到 }A} + \underbrace{3L}_{\text{最多三个空方向}} + \underbrace{4L}_{\text{找到 }B\text{ 并得到线段}} + \underbrace{2L}_{\text{得到第二条线段}} = 11L.

事实上这个分支已经直接达到 11L11L。

3. 真正麻烦的分支：找到了 A,BA,B，但没有线段

假设从 AA 搜索后：

  • 找到了 BB；
  • 没找到 CC；
  • 也没有得到包含 CC 的对角线段。

这种情况下，从 AA 开始的生产性搜索比“留下线段”的情况便宜，至多约 3L3L。所以此前总花费最多可以按

2L+3L+3L=8L2L+3L+3L=8L

来估计：

  • 2L2L：找到 AA；
  • 3L3L：找到 BB；
  • 3L3L：其他至多三个空区域。

因此最后必须在至多约 3L3L 内找到 CC。

如果直接从 BB 搜三个区域，每个区域先倍增判断是否为空，就可能超预算。这里才用到题解最后说的“把 BB 投影到边界”。

4. 边界投影的核心几何结论

以从 BB 向右搜索为例。

令右边界投影点为

Z=(N−1,By),h=N−1−Bx=d(Z,B).Z=(N-1,B_y), \qquad h=N-1-B_x=d(Z,B).

对任意点 PP，有

d(Z,P)−d(Z,B)=(N−1−Px)+∣Py−By∣−h=∣Py−By∣−(Px−Bx).\begin{aligned} d(Z,P)-d(Z,B) &=(N-1-P_x)+|P_y-B_y|-h\\ &=|P_y-B_y|-(P_x-B_x). \end{aligned}

因此：

当 PP 在右区域内部

即

Px−Bx>∣Py−By∣,P_x-B_x>|P_y-B_y|,

有

d(Z,P)<d(Z,B).d(Z,P)<d(Z,B).

所以 PP 比 BB 更接近 ZZ。

当 PP 在右区域的两条对角边界上

即

Px−Bx=∣Py−By∣,P_x-B_x=|P_y-B_y|,

有

d(Z,P)=d(Z,B).d(Z,P)=d(Z,B).

如果 P≠BP\ne B，从 ZZ 前往 PP 除了向左，还必须向上或向下。因此罗盘结果不可能只是 LEFT。

当 PP 在右区域之外

有

d(Z,P)>d(Z,B).d(Z,P)>d(Z,B).

它不会影响 ZZ 的最近宝藏答案。

唯一的退化情况：PP 和 BB 在同一行

如果

Py=By,Px>Bx,P_y=B_y,\qquad P_x>B_x,

那么虽然 PP 可能比 BB 更接近 ZZ，但从 ZZ 前往二者的第一步都只有向左。

因此查询 ZZ 仍然可能只返回：

{LEFT}.\{\text{LEFT}\}.

所以得到下面这个关键判定：

查询右边界投影 ZZ。
如果返回结果不只是 LEFT，则右区域中一定存在第三个宝藏。
如果结果只有 LEFT，则右区域内部没有第三个宝藏，唯一可能的例外是：CC 位于 BB 到 ZZ 的水平线段上。

其他三个方向完全对称。

这正是官方题解中“快速判断第三处宝藏位于哪个区域，或与 BB 在同一行/同一列”的准确含义。(InfosBG)

5. 如何利用这个判定省掉一整个 log⁡n\log n

假设 AA 位于 BB 的左区域，那么需要优先检查 BB 的：

  • 右区域；
  • 上区域；
  • 下区域。

这些都是“背离 AA”的区域。不能直接对朝向 AA 的区域使用这个简单判定，因为查询结果可能由已知宝藏 AA 造成。

对这三个区域分别取边界投影：

ZR=(N−1,By),ZU=(Bx,0),ZD=(Bx,N−1).Z_R=(N-1,B_y),\qquad Z_U=(B_x,0),\qquad Z_D=(B_x,N-1).

它们只需要 O(1)O(1) 次查询。

情形 A：某个投影并非只指向 BB

例如：

Query⁡(ZR)≠{LEFT}.\operatorname{Query}(Z_R)\ne\{\text{LEFT}\}.

那么已经严格证明：

C∈R(B).C\in R(B).

现在只剩一个未知宝藏，而且已经知道区域，所以调用便宜版搜索：

FindNextCheap(B,RIGHT).\text{FindNextCheap}(B,\text{RIGHT}).

它不需要再做倍增：

  1. 边界点 ZRZ_R 已经是“远端不再纯指向 BB”的证据；
  2. 第一次二分找沿 B→ZRB\to Z_R 的关键变化位置；
  3. 如果还不能直接算出 CC，再沿垂直方向做一次二分。

总计至多 2L2L。

参考实现正是先查询最远的 ZZ，若结果不纯粹指回 BB，便立即调用 FindNext3(..., skipB=true)。(oj.uz)

情形 B：三个投影都只指回 BB

那么 CC 不可能位于这三个区域的二维内部。

它只能位于以下几条线段之一：

BZR,BZU,BZD,BZ_R,\qquad BZ_U,\qquad BZ_D,

也就是与 BB 同行或同列。

问题已经从“在三个二维区域中找宝藏”降成：

在至多三条已知线段上找一个点。

参考实现对每条仍可能的轴线执行专门的一维 Bisection；每条只收一个二分阶段，最多 3L3L。其代码是在投影全部失败后，对各条 B→ZB\to Z 线段执行一次二分，并直接查询所得候选点。(oj.uz)

这里有一个很容易写错的细节：

沿 B→ZB\to Z 直接二分“是否指回 BB”并不单调，因为若 CC 与 BB 同行，则方向序列可能是

向后  →  向前或前后同时  →  C  →  向后.\text{向后} \;\to\; \text{向前或前后同时} \;\to\; C \;\to\; \text{向后}.

所以不能简单写成：

cpp
if (result contains opposite_direction)

来普通二分。

参考实现寻找的是中间那个“含有向前箭头”的块的右端点；找到右端点后就是 CC。实现时应保留前面搜索得到的区间信息，或者直接仿照参考代码中 pass == 1 的判定逻辑。

6. 为什么非对角情形不必再认真搜索“朝向 AA”的区域

若 A,BA,B 不在同一条对角线上，假设 BB 是从 AA 的右区域找到的。

从 BB 看，左区域是朝向 AA 的区域。

如果第三个宝藏 CC 真在这个左区域中，并且不与 A,BA,B 形成退化边界关系，那么从 AA 看，CC 会落入另一个已经搜索过的区域；此前从 AA 搜索时就应当已经找到它或得到对应线段。

所以普通非对角情况下，最后的主要候选就是三个背离 AA 的区域。

参考实现也利用了这一性质：若从 AA 朝某方向只找到 BB，而没有任何 CC 的迹象，则通常没有必要从 BB 沿相反方向再搜索；否则 CC 之前已经会在 AA 的其他方向中暴露。(oj.uz)

7. 对角线特殊情况为什么还要单独处理

当

∣Ax−Bx∣=∣Ay−By∣,|A_x-B_x|=|A_y-B_y|,

A,BA,B 位于同一条对角线上。

此时可能发生：

  • 从 AA 的某个方向找到 BB；
  • 从 BB 的对应方向又只找到 AA；
  • CC 藏在 A,BA,B 对应的两个“角落矩形”中；
  • 普通的四区域搜索会一直在 A,BA,B 之间来回。

假设 BB 在 AA 的右下方，则两个危险矩形大致是：

  • A,BA,B 包围盒的右上方向；
  • 左下方向。

参考实现为每个危险矩形设计了 FindInRectangle：

  • 先查询矩形的两个关键边界角点；
  • 若两个角点不能同时被矩形内的 CC 影响，O(1)O(1) 排除；
  • 若两个角点都表明矩形内有宝藏，再用两次二分找到 CC。

一次矩形检查要么花 O(1)O(1) 并失败，要么花至多 2L2L 并成功。(oj.uz)

更重要的是顺序：

必须先检查这两个角落矩形，再做从 BB 朝 AA 的昂贵搜索。

如果先做昂贵搜索，之后才检查矩形，最坏会达到 12L12L；参考实现明确说，提前检查矩形将对角情形从 12L12L 降到了 11L11L。(oj.uz)

8. 完整预算总结

分支一：已经得到包含 CC 的线段

步骤费用找到 A2L三个空方向3L找到 B 并产生一条线段4L从 B 得到第二条线段2L总计11L\begin{array}{c|c} \text{步骤}&\text{费用}\\ \hline \text{找到 }A&2L\\ \text{三个空方向}&3L\\ \text{找到 }B\text{ 并产生一条线段}&4L\\ \text{从 }B\text{ 得到第二条线段}&2L\\ \hline \text{总计}&11L \end{array}

分支二：找到 BB，但没有线段

此前至多：

2L+3L+3L=8L.2L+3L+3L=8L.

最后：

  • 边界投影：O(1)O(1)；
  • 投影确定了区域：至多 2L2L；
  • 所有投影都纯指回 BB：降成至多三条轴线的一维问题，至多 3L3L。

所以：

8L+3L=11L.8L+3L=11L.

分支三：A,BA,B 共对角线

由于一个 BB 往往同时属于 AA 的两个方向，前面实际少搜索了一个独立方向，省下一个 LL。把危险矩形检查提前，可以保证不会同时支付“完整回搜”和“矩形搜索”的最坏费用，最终仍控制在 11L11L。

9. 最后的优化阶段可以写成这样的框架

cpp
// 已知 A, B，只剩 C，且当前没有 C 所在线段

vector<Direction> away = directions_away_from_A(B, A);

// 对角特殊情况可以先做两个角落矩形的 O(1) 预检查
if (A_and_B_are_diagonal()) {
    if (try_corner_rectangles(A, B)) return;
}

// 先查询各个方向的边界投影
for (Direction d : away) {
    Point Z = project_to_border(B, d);
    int r = query(Z);

    if (r == TREASURE) return;

    if (r != only(opposite(d))) {
        // C 确定在这个区域
        find_next_cheap(B, d);  // <= 2L
        return;
    }
}

// 所有二维区域都被排除。
// C 只能与 B 同行或同列，处理对应的轴线候选。
for (Direction d : away) {
    if (axis_segment_is_still_possible(d)) {
        if (find_on_axis_segment(B, d)) return; // 一个专门的一维阶段
    }
}

// 仅对角退化情形还可能需要朝 A 的方向处理
handle_diagonal_bounce_case(A, B);

实现时最重要的两个提醒

第一，一定要缓存每个坐标的查询结果。参考实现的接口层对查询进行了缓存，重复查询同一点不再真正调用交互库。很多端点、宝藏点和二分边界会被重复访问；不缓存可能使理论上的 11L11L 因常数项超限。(oj.uz)

第二，边界投影的结论不是：

投影只指回 BB，所以该区域没有 CC。

正确结论是：

投影只指回 BB，所以该区域的二维内部没有 CC，但 CC 仍可能在投影射线本身，即与 BB 同行或同列。

这正是整个优化中最容易漏掉的退化情况。

Partager cette Q&R