题解 AT4432 【[ARC103B] Robot Arms】
CYJian
2020-02-20 16:14:40
先考虑判断不合法：
如果对于两个点，$x+y$ 的奇偶性不相同，则一定不合法。因为从 $(0, 0)$ 走到 $(x,y)$，至少需要长度为 $x+y$ 的机械臂。若机械臂增长，则需要保证延长出去的要能收回来。也就是说，你多往左走一格，也就需要再往右走回去一格。这样的话是不能改变奇偶性的。
那么现在我们就能判断出不能构造解的条件了。
若不存在不合法的情况，考虑如何构造：
注意到 $m$ 的限制大约是 $\log (x+y)$，则考虑倍增构造：
先考虑只有一个长度为 $1$ 的机械臂能干啥：
（下面用 `.` 描述的坐标系默认中心为原点）
```plain
...........
...........
...........
...........
.....#.....
....#.#....
.....#.....
...........
...........
...........
...........
```
然后再画出有 $1$ 和 $2$ 的能到达的格点：
（用 `&` 表示第一步 $2$ 到的点，然后 `#` 再表示第二步 $1$ 能到的点）
```plain
...........
...........
.....#.....
....#&#....
...#.#.#...
..#&#.#&#..
...#.#.#...
....#&#....
.....#.....
...........
...........
```
不难发现，这相当于是将 $1$ 的 $3 \times 3$ 的小方格复制了四份，以 `&` 为中心放在 $2$ 到达的 $4$ 个点上。
再加上 $4, 8, \ldots$ 也是同理。不难发现，加到 $2^{30}$ 就能满足题目的要求了。
考虑如何构造。
我们从大到小考虑每个机械臂。设当前到达的点为 $(nx, ny)$，目标点为 $(x, y)$。考虑当前这个机械臂沿着让 $x,y$ 坐标差值和最小的那个方向摆放。若有多个则可以随便摆放。不难发现，这样一定能构造出解。
$\rm Code$：
```cpp
int x[1010];
int y[1010];
int len[33];
int main() {
int n = ri;
for(int i = 1; i <= n; i++)
x[i] = ri, y[i] = ri;
int tmp = abs(x[1] + y[1]) & 1;
for(int i = 1; i <= n; i++)
if((abs(x[i] + y[i]) & 1) != tmp)
return puts("-1"), 0;
printf("%d\n1", 32 - tmp);
len[1] = 1; int N = 1;
if(tmp) {
for(int i = 1; i <= 30; i++) printf(" %d", len[++N] = 1 << i);
puts("");
} else {
for(int i = 0; i <= 30; i++) printf(" %d", len[++N] = 1 << i);
puts("");
} char s[40];
memset(s, 0, sizeof(s));
for(int i = 1; i <= n; i++) {
ll nx = 0, ny = 0;
for(int j = N; j; --j) {
ll dx = x[i] - nx, dy = y[i] - ny;
if(abs(dx) > abs(dy)) {
if(dx > 0) nx += len[j], s[j] = 'R';
else nx -= len[j], s[j] = 'L';
} else {
if(dy > 0) ny += len[j], s[j] = 'U';
else ny -= len[j], s[j] = 'D';
}
} printf("%s\n", s + 1);
}
return 0;
}
```