题解 CF538G 【Berserk Robot 】

> [CF538G Berserk Robot](https://codeforces.com/contest/538/problem/G) ## 题意 - 有一个机器人，第 $0$ 秒时在 $(0,0)$ 位置。 - 机器人会循环执行一个长度为 $l$ 的指令序列，每秒执行一个指令。 - 指令有 `ULDR` 四种，分别代表向上/左/下/右移动一格。 - 你不知道这个指令序列具体是什么，但是你知道 $n$ 条信息，第 $i$ 条信息为「第 $t_i$ 秒时机器人在 $(x_i,y_i)$」，保证 $t$ 递增。 - 你需要构造一个满足这些信息的指令序列，或判断不存在。 - $n \le 2 \times 10^5$，$l \le 2 \times 10^6$，$t_i,|x_i|,|y_i| \le 10^{18}$。 ## 题解 上下左右比较不好做，横纵坐标有关联。 考虑将坐标系逆时针旋转 $45^{\circ}$，同时放大到原来的 $\sqrt 2$ 倍。 这样 `ULDR` 对应的就是 $(1,1),(-1,1),(-1,-1),(1,-1)$，可以分开考虑横纵坐标了。 此时原来的 $(x_i,y_i)$ 则对应着 $(x_i + y_i, y_i - x_i)$。 但这样还不够方便，我们考虑将 $t$ 时刻的横纵坐标都加上 $t$ 再除以 $2$。 这样 `ULDR` 对应的就是 $(1,1),(0,1),(0,0),(1,0)$，此时原来的 $(x_i,y_i)$ 对应成 $(\frac{x_i+y_i+t}2, \frac{y_i-x_i+t}2)$。 先判掉奇偶性不合法的情况，剩下的只用考虑距离上的约束。 设 $s_i$ 表示时刻 $i$ 的位置，一个周期的位移 $v = s_{l}$。 对于第 $i$ 条信息，设 $k_i = \lfloor \frac{t_i}l \rfloor$，$w_i = t_i \bmod l$，则有 $(x_i, y_i) = s_{t_i} = k_i v + s_{w_i}$。 为了方便后面的操作，我们加上 $k_i = 0, w_i = 0$ 和 $k_i = -1, w_i = l$ 这两条信息，显然这两条信息中 $t_i = x_i = y_i = 0$。 对 $w_i$ 排序然后差分，对于前后差分的 $i,j$，设 $k = k_j - k_i$，可以得到 $kv + (s_{w_j} - s_{w_i}) = (x_j - x_i, y_j - y_i)$。 将 $x,y$ 分开考虑，在这里以 $x$ 为例。 由于每次只能 $+0/1$，设 $w = w_j - w_i$，有 $0 \le (s_{w_j} - s_{w_i})_x \le w$。 即 $x_j - x_i - w \le kv_x \le x_j-x_i$。 若 $k = 0$，如果不满足 $x_j - x_i - w \le 0 \le x_j - x_i$，则无解。 若 $k > 0$，得到 $\lceil \frac{x_j - x_i - w}{k}\rceil \le v_x \le \lfloor \frac{x_j - x_i}{k} \rfloor$，同理有 $\lceil \frac{y_j - y_i - w}{k}\rceil \le v_y \le \lfloor \frac{y_j - y_i}{k} \rfloor$。 若 $k < 0$，得到 $\lceil \frac{x_i - x_j}{-k}\rceil \le v_x \le \lfloor \frac{x_i - x_j+w}{-k} \rfloor$，同理有 $\lceil \frac{y_i - y_j}{-k}\rceil \le v_x \le \lfloor \frac{y_i - y_j+w}{-k} \rfloor$。 一共有 $\mathcal O(n)$ 个这样的不等式，形成的不等式组如果有解即可任选一组解构造。 具体构造的方法是，确定 $v$ 之后根据 $(x_i, y_i) = s_{t_i} = k_i v + s_{w_i}$ 确定所有 $s_{w_i}$。 对于差分后相邻的两项，可以先从 $s_i$ 最快地走到 $s_j$，有多余的步数在 $s_j$ 附近反复横跳即可，由于判掉了奇偶性不合法的情况，这样一定可以消耗尽所有多余的步数同时最终停在 $s_j$。 总时间复杂度 $\mathcal O(n \log n)$。 ## 代码 ```cpp #define Fail prints("NO"), exit(0) const int N = 2e5 + 7; const ll inf = 4e18; int n, l; ll lx = -inf, rx = inf, ly = -inf, ry = inf; struct P { ll t, x, y, k; int w; inline void in() { ll p, q; rd(t), rd(p), rd(q); if ((t ^ p ^ q) & 1) Fail; k = t / l, w = t % l; x = (p + q + t) / 2, y = (q - p + t) / 2; } inline bool operator < (const P &o) const { return w < o.w; } } p[N]; int main() { rd(n), rd(l); for (int i = 1; i <= n; i++) p[i].in(); sort(p + 1, p + n + 1); p[++n].k = -1, p[n].w = l; for (int i = 1; i <= n; i++) { ll k = p[i].k - p[i-1].k; int w = p[i].w - p[i-1].w; if (!k) { if (p[i].x - p[i-1].x - w > 0 || p[i].x - p[i-1].x < 0) Fail; if (p[i].y - p[i-1].y - w > 0 || p[i].y - p[i-1].y < 0) Fail; } else if (k > 0) { lx = max(lx, (ll)ceil(1.0L * (p[i].x - p[i-1].x - w) / k)); rx = min(rx, (ll)floor(1.0L * (p[i].x - p[i-1].x) / k)); ly = max(ly, (ll)ceil(1.0L * (p[i].y - p[i-1].y - w) / k)); ry = min(ry, (ll)floor(1.0L * (p[i].y - p[i-1].y) / k)); } else { k *= -1; lx = max(lx, (ll)ceil(1.0L * (p[i-1].x - p[i].x) / k)); rx = min(rx, (ll)floor(1.0L * (p[i-1].x - p[i].x + w) / k)); ly = max(ly, (ll)ceil(1.0L * (p[i-1].y - p[i].y) / k)); ry = min(ry, (ll)floor(1.0L * (p[i-1].y - p[i].y + w) / k)); } } if (lx > rx || ly > ry) Fail; for (int i = 1; i <= n; i++) { int dx = (p[i].x - p[i].k * lx) - (p[i-1].x - p[i-1].k * lx); int dy = (p[i].y - p[i].k * ly) - (p[i-1].y - p[i-1].k * ly); int t = p[i].w - p[i-1].w, x = 0, y = 0; while (t--) if (x < dx) { ++x; if (y < dy) putchar('U'), ++y; else putchar('R'); } else { if (y < dy) putchar('L'), ++y; else putchar('D'); } } return 0; } ```