题解 CF538G 【Berserk Robot 】

xht · 2020-02-15 01:03:39 · 题解

CF538G Berserk Robot

题意

• 有一个机器人，第 0 秒时在 (0,0) 位置。
• 机器人会循环执行一个长度为 l 的指令序列，每秒执行一个指令。
• 指令有 ULDR 四种，分别代表向上/左/下/右移动一格。
• 你不知道这个指令序列具体是什么，但是你知道 n 条信息，第 i 条信息为「第 t_i 秒时机器人在 (x_i,y_i)」，保证 t 递增。
• 你需要构造一个满足这些信息的指令序列，或判断不存在。

题解

上下左右比较不好做，横纵坐标有关联。

考虑将坐标系逆时针旋转 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;
}