CF538G Berserk Robot 题解

CF538G Berserk Robot

题意

• 有一个机器人，第 $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)$。

代码

#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;
}