Visits: 238

ARC103D Robot Arms

题意

• 平面上有 $n$ 个整点 $(x_i, y_i)$。
• 要求构造出一个长度为 $m(\in [1,40])$ 的整数序列 $d(\in [1,10^{12}])$，满足 $d$ 可以生成所有整点。
• 称一个整数序列 $d_{1\dots m}$ 可以生成一个整点 $(x_i,y_i)$，当且仅当可以从 $(0,0)$ 开始，每次往上下左右中的一个方向走一个 $d_i$，最终可以恰好在 $(x_i,y_i)$。
• $n \le 10^3$，$|x_i|,|y_i| \le 10^9$。

题解

有解当且仅当所有 $x_i + y_i$ 的奇偶性相同。

若 $x_i + y_i \equiv 1 \pmod 2$，则 $2^0,2^1,\cdots,2^{30}$ 即可；若 $x_i + y_i \equiv 0 \pmod 2$，则再加一个 $1$ 即可。

构造时从大到小考虑，走距离更远的方向。

代码

const int N = 1e3 + 7;
int n;
ll x[N], y[N], z[N];

inline char work(ll x, ll y, ll &X, ll &Y, ll k) {
    if (abs(x - X) > abs(y - Y)) {
        if (x > X) return X += k, 'R';
        return X -= k, 'L';
    }
    if (y > Y) return Y += k, 'U';
    return Y -= k, 'D';
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++)
        rd(x[i], y[i]), z[i] = abs(x[i] + y[i]) % 2;
    for (int i = 1; i <= n; i++)
        if (z[i] != z[1]) return print(-1), 0;
    vector<ll> d;
    for (int i = 30; ~i; i--) d.pb(1ll << i);
    if (!z[1]) d.pb(1ll);
    print(d.size());
    for (ll k : d) print(k, ' ');
    prints("");
    for (int i = 1; i <= n; i++) {
        ll X = 0, Y = 0;
        for (ll k : d)
            printc(work(x[i], y[i], X, Y, k));
        prints("");
    }
    return 0;
}