ARC103D Robot Arms 题解

作者: xht37 分类: 题解 发布时间: 2020-04-21 20:15

点击数:46

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注