专栏文章

AGC062D

llsj2009Isj2OO9
AT_agc062_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minw0m42
此快照首次捕获于
2025/12/02 09:16
3 个月前
此快照最后确认于
2025/12/02 09:16
3 个月前
查看原文
首先曼哈顿转切比雪夫，每次可以走到一个正方形边框上。有解的一个必要条件是 ∑Di≥2max⁡Di\sum D_i\ge 2\max{D_i}，否则走一次 max⁡Di\max{D_i} 长的步永远都回不到原点；其实这也是充分的，我们先给出一个重要引理：
  • 若 max⁡ai≤r\max{a_i}\le r 且 ∑ai≥r\sum a_i\ge r，则必然可以通过 aa 的一个子集走到距离起点 =r=r 的正方形边框所有点上。
证明：
  • 先尝试可以走到边框上：取 b⊆ab\subseteq a 且 ∑bi≤r\sum b_i\le r，笔直地走向边框一侧，再取一个 d∈a∖bd\in a\setminus b 且 d+∑bi≥rd+\sum b_i\ge r，向旁边走 dd，由于 d≤rd\le r 这肯定可以做到，朝原来的方向走 r−∑bir-\sum b_i 即可来到边框上。
  • 根据事先走的 bb，走 dd 的方向可以增加或者是减去任意 [0,∑bi]\left[0,\sum b_i\right] 的值，那也就是当 d>∑bid>\sum b_i 时有些点走不到，那为什么不在最开始把 dd 放到 bb 里呢？然后可以再反转 b/db/d 走的方向即可走到边框上所有点。
再回头看最开始的结论，我们只需要通过一些不含 max⁡Di\max{D_i} 的步走到 max⁡Di\max{D_i} 的正方形边框上，然后可以浪费掉一些无用步（相当于在当前位置每次画一个正方形边框，然后走到其和 max⁡Di\max{D_i} 的正方形边框相交处，由于其边长 ≤max⁡Di\le \max{D_i} 肯定有交），最后再通过 max⁡Di\max{D_i} 一步回到原点。进一步的，可以发现最终答案 rr 在 [max⁡Di2,max⁡Di]\left[\frac{\max{D_i}}{2},\max{D_i}\right] 中，因为 r<max⁡Dir<\max{D_i} 无论如何走一个 max⁡Di\max{D_i} 都走出正方形了。
接下来考虑 rr 的判定性问题。继承上面的思路，走的过程形如：
  • 走一些步到 rr 的边框上。
  • 在边框上浪费一些不用步（因为 rr 取值范围的限制，这里肯定有交）。
  • 走一些步回到原点。
那其实就是找两条无交的从原点到 rr 边框上的路径了（其实应该要求终点相同，但我们下面仍然会说明，如果可以走到边框，那就可以走到边框上的任意点）。考察一个集合 SS 是否可以通过其的一个子集走到 rr 的边框上：
  • 若 ∑x∈S,x≤rx≥r\sum\limits_{x\in S,x\le r}x\ge r，根据上面的引理，肯定可以做到，且可以走到边框上任意点。
  • 否则必然会走 >r>r 的步，先来看看只走一次 >r>r 的步 dd 的情况。那肯定是形如往一个方向走了一些步，然后再通过 dd 一步折返直接到边框上。如此要求走的 d−rd-r 的边框上，由于仅要求走的点在 rr 边框内，这里充要条件为 ∑x∈S,x≤rx≥d−r\sum\limits_{x\in S,x\le r}x\ge d-r。再找到最小的 dd，就是只走一步 >r>r 情况下的充要条件——实际上也是全部情况下的！如果不满足这个条件根本走不了 >r>r 的步。进一步的，因为 d>rd>r，你只需调整 dd 这一步在另一侧的步幅大小就可以走到边框上任意点。
由于 d≤max⁡Di≤2r⇒d−r≤rd\le \max{D_i}\le 2r\Rightarrow d-r\le r，即当 ∑x∈S,x≤rx\sum\limits_{x\in S,x\le r}x 相同时，有 >r>r 的步候选总比没有 >r>r 的步限制更松。从小到大扫 rr，我们想要找到两条合法路径，肯定是 >r>r 的数中最小值和次小值留分别给两条路径，对于 ≤r\le r 的数做一个背包即可，容易判定合法性。复杂度 O(nVw)\mathcal{O}\left(\frac{nV}{w}\right)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...