AtCoder

Luogu

分析

首先，如果存在 $i,j$ 满足 $|x_i+y_i|$ 与 $|x_j+y_j|$ 的奇偶性不同，则无解。因为走到 $(x,y)$ 的步数一定与 $|x_i+y_i|$ 的奇偶性相同。

先考虑 $|x_i+y_i|$ 全部为奇数的情况。

先考虑步长的问题。可以利用二进制进行构造，即令步长为 $2^0,2^1,\cdots$。容易发现最大只需要到 $2^{30}$ 即可表示出 $10^9$ 内所有坐标。

考虑如何进行构造。从大到小枚举步长，每一步在四个方向中选择最近的即可。正确性不难理解。

$|x_i+y_i|$ 的情况类似，只要再多加一步 $1$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const char ch[4]={'L','R','D','U'};
const char dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

int n,x[N],y[N];
vector<int> c;

int main() {
    n=read();
    for (int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    for (int i=2;i<=n;++i)
        if ((abs(x[i]+y[i])&1)!=(abs(x[1]+y[1])&1)) {
            puts("-1"); return 0;
        }
    for (int i=30;~i;--i) c.push_back(1<<i);
    if (!(abs(x[1]+y[1])&1)) c.push_back(1);
    printf("%lu\n",c.size());
    for (int i:c) printf("%d ",i); puts("");
    for (int i=1;i<=n;++i) {
        ll nx=0,ny=0;
        for (int j:c) {
            vector<pair<ll,int> > o;
            for (int d=0;d<4;++d) {
                ll tx=nx+dx[d]*j,ty=ny+dy[d]*j;
                o.push_back(make_pair(abs(x[i]-tx)+abs(y[i]-ty),d));
            }
            sort(o.begin(),o.end());
            int d=o.begin()->second;
            putchar(ch[d]),nx+=dx[d]*j,ny+=dy[d]*j;
        }
        puts("");
    }
    return 0;
}