题解 AT4432 【[ARC103B] Robot Arms】

大概是给出了和cyj不同的另一种证明方法和另一种构造方式？但其实本质是一样的。 _____ 首先无解很容易判断。因为多走一步和少走一步之间的差值总是 $2\times$步长 ，所以如果 $x_i+y_i$ 的奇偶性不同的话，就不能同时满足条件。 发现这个题的本质是拆分问题。那么大概可以引导到「二进制拆分」这种泛式的拆分方式上。不妨考虑对于一组 $\{1,2,4\cdots 2^k\}$ 可以拼出哪些坐标。那么考虑对于一组坐标 $(x,y)$ ，他可以被通达，那么可以知道如果想要减小某一维坐标，比如 $x\to x'$，那有两种情况： 1、只是单纯地拿掉几个元素。比如 $16\to11$ 就是简单地拆出 $4$ 和 $1$ 。 2、拿出几个元素并且换进去几个元素。比如 $12\to11$ 就是拆出 $2$ 和 $1$ 放进一个 $4$ 。 可以看出，这是可以相互通达的。 更详细一点。因为对于四个象限，情况都是等价的。所以只考虑第一象限。发现对于 $\{1,2,4\cdots 2^k\}$ ，它可以维护到的位置至少是所有 $|x+y|=\sum _{i=0}^k 2^i=2^{k+1}-1$。但是不仅限于此。发现如果将将其中某个元素的贡献取负，那么就可以访问到所有 $|x+y| - \sum 2^p$ 的格子。换句话说，这个方式可以访问到所有与 $2^{k+1}-1$ 奇偶性相同的格子。 到这一步就已经很完美了，但是依然存在问题。如果 $|x+y|$ 都是偶数，这就挂了。所以此时可以随便向 $x$ 轴或者 $y$ 轴偏移 $1$ ，比如把 $(1,0)$ 变换成原点，就解决了。 实现方面，发现最合法区域后是个内部镂空的菱形。找出来之后，对于一组坐标 $(x,y)$ ，考虑对称着找。反向从大到小枚举每一个步长，如果新的点的 $|x|+|y|$ 之和严格小于当前的步长，就是可以拼出来的。不难知道这样做是对的。 ```cpp int n ; int cnt ; int _eve ; ll nx, ny ; int bc[N] ; struct rg{ int l ; int r ; int t ; }base[N] ; //D R U L int dx[4] = {0, 1, 0, -1} ; int dy[4] = {-1, 0, 1, 0} ; char s[4] = {'U', 'L', 'D', 'R'} ; int main(){ cin >> n ; bc[0] = 1 ; for (int i = 1 ; i <= n ; ++ i){ cin >> base[i].l >> base[i].r ; base[i].t = abs(base[i].l + base[i].r) & 1 ; } for (int i = 2 ; i <= n ; ++ i) if (base[i].t != base[1].t) return puts("-1"), 0 ; for (int i = 1 ; i <= 30 ; ++ i) bc[++ cnt] = 1 << i ; cout << cnt + 1 + (bool)(!(base[1].t & 1)) << '\n' ; if (!(base[1].t & 1)) cout << 1 << " " ; for (int i = cnt ; ~i ; -- i) printf("%d%c", bc[i], " \n"[!i]) ; for (int i = 1 ; i <= n ; ++ i){ nx = base[i].l ; ny = base[i].r ; if (!(base[i].t & 1)) ny -= 1, putchar('U') ; //cout << nx << " " << ny << endl ; for (int j = cnt ; ~j ; -- j){ for (int k = 0 ; k < 4 ; ++ k){ ll kx = nx + (ll)dx[k] * bc[j] ; ll ky = ny + (ll)dy[k] * bc[j] ; if (abs(kx) + abs(ky) < bc[j]){ nx = kx ; ny = ky ; //cout << nx << " " << ny << endl ; printf("%c", s[k]) ; break ; } } } puts("") ; } return 0 ; } ``` #