「ARC 103B」Robots Arms

题目链接:ARC 103B

Snuke 正在向他的工厂介绍一款机械臂:

  • 机械臂由 $m$ 个部分和 $m + 1$ 个关节组成,关节标号为 $0$ 到 $m$。第 $i$ 个部分连着第 $i - 1$ 和 $i$ 个关节。第 $i$ 个部分的长度为 $d_i$。
  • 对于每个部分,可以单独指定其动作。现在有 $4$ 种模式:$\text{L}$、$\text{R}$、$\text{D}$ 和 $\text{U}$。如果我么把工厂视为坐标平面,那么关节 $i$ 的位置将通过如下方法确定(我么将它的坐标表示为 $(x_i, y_i)$):

    • $(x_0, y_0) = (0, 0)$。
    • 如果第 $i$ 个模式为 $\text{L}$,那么 $(x_i, y_i) = (x_{i - 1} - d_i, y_{i - 1})$。
    • 如果第 $i$ 个模式为 $\text{R}$,那么 $(x_i, y_i) = (x_{i - 1} + d_i, y_{i - 1})$。
    • 如果第 $i$ 个模式为 $\text{D}$,那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} - d_i)$。
    • 如果第 $i$ 个模式为 $\text{U}$,那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} + d_i)$。

Snuke 想要引入一种机械臂,以便通过正确的指定模式,使得关节 $m$ 可以到达所有的 $n$ 个点 $(X_1, Y_1), (X_2, Y_2),\cdots, (X_n, Y_n)$。请判断这是否可行。如果可行,那么请你构造一个满足条件的机械臂,并分别给出到达 $n​$ 个点的模式方案。

在你构造出的方案中,必须满足 $1 \le m \le 40$,$1 \le d_i \le 10 ^ {12}​$。

数据范围:$1 \le n \le 1000$,$-10 ^ 9 \le X_i, Y_i \le 10 ^ 9$。


Solution

首先我们判断无解情况:很显然无解当且仅当 $X_i + Y_i​$ 的奇偶性不全相同。

由于这是构造题,我们首先想到二进制拆分。使用 $\{2 ^ 0, 2 ^ 1, 2 ^ 2, \cdots 2 ^ k\}$ 的边进行构造。可以用数学归纳法证明:用边长 $\{2 ^ 0, 2 ^ 1, 2 ^ 2, \cdots 2 ^ k\}$ 的边可以达到所有 $\lvert x \rvert + \lvert y \rvert < 2 ^ {k + 1}$ 且 $x + y$ 为奇数的点。具体证明可以参考这篇博客

如果 $x + y$ 为偶数则只需要再加上一条长度为 $1$ 的边即可。模式方案的构造只需要贪心移动 $x, y​$ 坐标中绝对值较大的一者。在上述博客中也有归纳证明过程。

时间复杂度:$\mathcal O(n \log (X_i + Y_i))$。


Code

#include <cstdio>
#include <algorithm>
#define fail return puts("-1"), 0

const int N = 1e3 + 5;

int n, sz;
long long x[N], y[N], bin[33];

void solve(long long x, long long y) {
    for (int i = sz - 1; i >= 0; i--) {
        if (std::labs(x) > std::labs(y)) {
            putchar(x < 0 ? 'L' : 'R');
            x < 0 ? x += bin[i] : x -= bin[i];
        } else {
            putchar(y < 0 ? 'D' : 'U');
            y < 0 ? y += bin[i] : y -= bin[i];
        }
    }
    puts("");
}
int main() {
    scanf("%d", &n);
    bool flg1 = false, flg2 = false;
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", &x[i], &y[i]);
        ((x[i] + y[i]) & 1 ? flg1 : flg2) = true;
    }
    if (flg1 && flg2) fail;
    if (flg1) {
        printf("%d\n", sz = 32);
        for (int i = sz - 1; i >= 0; i--) {
            printf("%lld%c", bin[i] = 1LL << i, " \n"[i == 0]);
        }
    } else {
        printf("%d\n", sz = 33);
        for (int i = sz - 1; i >= 1; i--) {
            printf("%lld ", bin[i] = 1LL << (i - 1));
        }
        printf("%lld\n", bin[0] = 1);
    }
    for (int i = 1; i <= n; i++) solve(x[i], y[i]);
    return 0;
}

发表评论