526互联

AtCoder Regular Contest 109 D L

发布时间 2023-04-18 17:23:15作者: zltzlt

洛谷传送门

AtCoder 传送门

这种题根本做不出来……

考虑一个 L 形怎么方便地表示出来。可以发现对于组成 L 形的三个点 \((x_1,y_1),(x_2,y_2),(x_3,y_3)\)，只要知道 \(x = x_1 + x_2 + x_3\) 和 \(y = y_1 + y_2 + y_3\)，就能确定三个坐标。证明是设折点坐标为 \((p,q)\)，则其余两个点的坐标可以用 \((p+u,q),(p,q+v)\) 表示，其中 \(u,v \in \{-1,1\}\)。那么 \(x = 3p + u, y = 3q + v\)，\(p\) 可以通过 \(\frac{x}{3}\) 四舍五入得出，\(q\) 同理。

那么答案就是把坐标和从 \((1,1)\) 变成 \((ax + bx + cx, ay + by + cy)\) 的最小步数。考虑把 \((1,1)\) 到达小范围内的点的最小步数打个表：

 7,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 7,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 6,  , 6,
 7,  , 6, 5,  , 4, 4,  , 4, 4,  , 4, 4,  , 4, 4,  , 5, 5,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 5,  , 4, 3,  , 3, 3,  , 3, 3,  , 3, 4,  , 4, 5,  , 6,
 7,  , 6, 5,  , 4, 3,  , 2, 2,  , 2, 2,  , 3, 3,  , 4, 5,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 5,  , 4, 3,  , 2, 1,  , 1, 1,  , 2, 3,  , 4, 5,  , 6,
 7,  , 6, 5,  , 4, 3,  , 2, 1,  , 0, 1,  , 2, 3,  , 4, 5,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 5,  , 4, 3,  , 2, 2,  , 1, 1,  , 2, 3,  , 4, 5,  , 6,
 7,  , 6, 5,  , 4, 3,  , 3, 2,  , 2, 2,  , 2, 3,  , 4, 5,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 5,  , 4, 4,  , 3, 3,  , 3, 3,  , 3, 3,  , 4, 5,  , 6,
 7,  , 6, 5,  , 5, 4,  , 4, 4,  , 4, 4,  , 4, 4,  , 4, 5,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 7,  , 6, 6,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 5, 5,  , 6,
 7,  , 7, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6, 6,  , 6,
  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,
 8,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7, 7,  , 7,

中间的 0 是 \((1,1)\)，空白点表示这个点不存在。

发现空白点把其他点划分成了 \(2 \times 2\) 的块，并且相邻块的边界点可以互相到达，块内的点也可以互达。

考虑删除空白的行列，然后把 0 点看作 \((0,0)\)。此时相当于若位于 \((x,y)\)，令 \(u = (-1)^{1 - x \bmod 2}, v = (-1)^{1 - y \bmod 2}\)，则 \((x,y)\) 可一步到达除 \((x + u, y + v)\) 外的七个方向的任一点。如果能走八个方向，答案就是 \(\max(|x|,|y|)\)；加了限制后发现主对角线的点有一些特殊，例如 \((-1,-1)\)，想到达它必须得先向左再向下，多走一步。那么答案就是 \(\max(|x|,|y|) + [x=y]\)。特判 \((x,y) = (0,0)\) 或 \((1,1)\) 的情况。