题目大意

初始在 \((0,0)\) 点，有 \(n\) 组数据，需要在走 \(m\) 步后到达，\((x_i,y_i)\)，每组的步长相同，每步的方向可以任意

要求构造一种合法方案

AT4432 [ARC103B] Robot Arms

solve

先判断是否无解，显然，对于每组数据，走完后的 \(x_i+y_i\)的奇偶性是不变的，所以如果 \(x_i+y_i\) 的奇偶性不同的话就无解

然后考虑如何构造步长

通过观察我们发现，\(m\) 最大只有 \(40\) 左右，所以考虑二进制拆分坐标

也就是说，我们要用 \(1,2,4,...,2^k\) 的步长来构造

显然，四个象限是等价的，所以只需要考虑第一象限，发现对于 \(\{1,2,4\cdots 2^k\}\)，它可以维护到的位置至少是所有 \(|x+y|=\sum _{i=0}^k 2^i=2^{k+1}-1\)，

如果可以正负的话，那么可以访问到的格子久变成了 |\(x+y| - \sum 2^p\)

所以构造方法就很显然了

反过来思考，从大到小放，如果 \(x\) 坐标的偏移量大就放 \(x\)，如果 \(y\)坐标的偏移量大就放 \(y\) ，那么肯定能存在一种构造方式

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int N,x[maxn],y[maxn],tmp,n;
typedef long long LL;
LL len[40];
char s[40];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int main(){
	N=read();n=N;
	for(int i=1;i<=N;i++)x[i]=read(),y[i]=read();
	tmp=abs(x[1]+y[1])&1;
	for(int i=2;i<=N;i++){
		if((abs((x[i]+y[i])&1))!=tmp) return printf("%d\n",-1),0;
	}
	printf("%d\n1 ",32-tmp);len[1]=1;N=1;
	if(!tmp)for(int i=0;i<=30;i++)printf("%d ",len[++N]=1<<i);
	else for(int i=1;i<=30;i++)printf("%d ",len[++N]=1<<i);
	printf("\n");
	for(int i=1;i<=n;i++){
		LL now_x=0,now_y=0;
		memset(s,0,sizeof s);
		for(int j=N;j;j--){
			LL dx=x[i]-now_x,dy=y[i]-now_y;
			if(abs(dx)>abs(dy)){
				if(dx>0)now_x+=len[j],s[j]='R';
				else now_x-=len[j],s[j]='L';
			}
			else {
				if(dy>0)now_y+=len[j],s[j]='U';
				else now_y-=len[j],s[j]='D';
			}
		}
		printf("%s\n",s+1);
	}
	return 0;
}