AGC062D

lsj2009 · 2025-09-16 10:49:32 · 题解

首先曼哈顿转切比雪夫，每次可以走到一个正方形边框上。有解的一个必要条件是 \sum D_i\ge 2\max{D_i}，否则走一次 \max{D_i} 长的步永远都回不到原点；其实这也是充分的，我们先给出一个重要引理：

• 若 \max{a_i}\le r 且 \sum a_i\ge r，则必然可以通过 a 的一个子集走到距离起点 =r 的正方形边框所有点上。

证明：

• 先尝试可以走到边框上：取 b\subseteq a 且 \sum b_i\le r，笔直地走向边框一侧，再取一个 d\in a\setminus b 且 d+\sum b_i\ge r，向旁边走 d，由于 d\le r 这肯定可以做到，朝原来的方向走 r-\sum b_i 即可来到边框上。

• 根据事先走的 b，走 d 的方向可以增加或者是减去任意 \left[0,\sum b_i\right] 的值，那也就是当 d>\sum b_i 时有些点走不到，那为什么不在最开始把 d 放到 b 里呢？然后可以再反转 b/d 走的方向即可走到边框上所有点。

再回头看最开始的结论，我们只需要通过一些不含 \max{D_i} 的步走到 \max{D_i} 的正方形边框上，然后可以浪费掉一些无用步（相当于在当前位置每次画一个正方形边框，然后走到其和 \max{D_i} 的正方形边框相交处，由于其边长 \le \max{D_i} 肯定有交），最后再通过 \max{D_i} 一步回到原点。进一步的，可以发现最终答案 r 在 \left[\frac{\max{D_i}}{2},\max{D_i}\right] 中，因为 r<\max{D_i} 无论如何走一个 \max{D_i} 都走出正方形了。

接下来考虑 r 的判定性问题。继承上面的思路，走的过程形如：

• 走一些步到 r 的边框上。

• 在边框上浪费一些不用步（因为 r 取值范围的限制，这里肯定有交）。

• 走一些步回到原点。

那其实就是找两条无交的从原点到 r 边框上的路径了（其实应该要求终点相同，但我们下面仍然会说明，如果可以走到边框，那就可以走到边框上的任意点）。考察一个集合 S 是否可以通过其的一个子集走到 r 的边框上：

• 若 \sum\limits_{x\in S,x\le r}x\ge r，根据上面的引理，肯定可以做到，且可以走到边框上任意点。

• 否则必然会走 >r 的步，先来看看只走一次 >r 的步 d 的情况。那肯定是形如往一个方向走了一些步，然后再通过 d 一步折返直接到边框上。如此要求走的 d-r 的边框上，由于仅要求走的点在 r 边框内，这里充要条件为 \sum\limits_{x\in S,x\le r}x\ge d-r。再找到最小的 d，就是只走一步 >r 情况下的充要条件——实际上也是全部情况下的！如果不满足这个条件根本走不了 >r 的步。进一步的，因为 d>r，你只需调整 d 这一步在另一侧的步幅大小就可以走到边框上任意点。

由于 d\le \max{D_i}\le 2r\Rightarrow d-r\le r，即当 \sum\limits_{x\in S,x\le r}x 相同时，有 >r 的步候选总比没有 >r 的步限制更松。从小到大扫 r，我们想要找到两条合法路径，肯定是 >r 的数中最小值和次小值留分别给两条路径，对于 \le r 的数做一个背包即可，容易判定合法性。复杂度 \mathcal{O}\left(\frac{nV}{w}\right)。