比赛：USACO 2024 JAN G

· · 题解

Walking in Manhattan

首先发现一个显然但重要的性质，

考虑把题目中的直线互相划分，形成一个网格图，然后我们以每个格子的边为单位，进行移动，

发现从一个格点开始走，当且仅当走过一段奇数长度的段，下一步会变向。

也就是说移动的过程相当于，从一个格点开始，不断地跳到下一个奇数段的末尾。当然，忽略一开始走到的格点之前的路径，和，最后走到的格点之后的路径，因为这些边界部分是可以快速计算的。

一般这类优化暴力移动的问题，我们可以考虑倍增。

设 f(i,j) 表示从第 i 个横坐标开始，向东走的第 2^j 个奇数段。g(i,j) 表示从第 i 个纵坐标开始，向北走的第 2^j 个奇数段。

由于起点可能不在格点上，先把它走到第一个格点。然后由于走的时候一定是 "向东 向北 向东 向北 ..." 交替着走的，于是 f 和 g 一起跳即可。最后再计算剩余走的情况，要么是 "向东 + 向北一点"，要么是 "向北 + 向东一点"，可以 O(1) 计算。

时空复杂度 O(n\log n)。

Code

Cowmpetency

My Solution

Nap Sort

My Solution