AT4432 [ARC103B] Robot Arms 题解

题目大意

初始在 \((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;
}
上一篇:cf1607 F. Robot on the Board 2(搜索)


下一篇:每个男孩的机械梦「GitHub 热点速览 v.21.41」