题解 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| 之和严格小于当前的步长，就是可以拼出来的。不难知道这样做是对的。 

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