题目大意
初始在 \((0,0)\) 点,有 \(n\) 组数据,需要在走 \(m\) 步后到达,\((x_i,y_i)\),每组的步长相同,每步的方向可以任意
要求构造一种合法方案
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;
}