ARC103D Robot Arms 题解

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