题目链接：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;
}