Codeforces Round 726 (Div. 2) B. Bad Boy

发布时间 2023-10-09 17:35:52作者: zsxuan

给一个 \(n \times m\) 的平面,一个初始位置 \((i, j)\)

需要放两个废弃物在平面上,位置为 \((x_1, y_1), (x_2, y_2)\)

使得从 \((i, j)\) 出发,捡起两个废弃物后,回到原位置,所经过的曼哈顿距离最长。

询问一组合法的 \((x_1, y_1), (x_2, y_2)\)

性质:二维平面上有关的曼哈顿距离问题,可以从两个一维考虑。

考虑第一维,有 \(n\) 个节点。若废弃物放在 \(0, n\) 的位置,则无论初始位置 \(j\) 位于何处,都需要产生 \(2(n-1)\) 的曼哈顿距离,同时也是最长距离。

同理,第二维最长一定会产生 \(2(m - 1)\) 的曼哈顿距离。

于是只需要让 \((x_1, y_1) = (1, 1)\)\((x_2, y_2) = (n, m)\) ,便可产生最长的 \(2(n - 1) + 2(m - 1)\) 的曼哈顿距离。

view