AT4432 [ARC103B] Robot Arms

给一个和大家都不太一样的做法？

判无解，如果奇偶不同就无解，因为加减满足奇偶性不变

然后考虑数据范围，观察到 $10^{12}\approx2^{40}$，可以想到倍增构造，于是就让机械臂长为 $1,2,4,8...2^{39}$

然后这里需要注意的是如果 $x+y$ 为奇数的情况，这时需要额外补一个长度为 $1$ 的机械臂补全

从大到小安排机械臂，使用贪心构造，横纵坐标中离目标点差最小的优先，因为有 $2^{k+1}-2^k=2^k$，所以可以知道一定能构造出解

// Problem: AT4432 [ARC103B] Robot Arms
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT4432
// Memory Limit: 1000 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
const int N=1010;
int x[N],y[N],cnt,d[N],pd[2];
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;cin>>n;
	rep(i,1,n){cin>>x[i]>>y[i];pd[(x[i]+y[i])&1]++;}
	if(pd[0]&&pd[1]){cout<<"-1";return 0;}
	pre(i,38,0)d[++cnt]=1ll<<i;
	if(pd[0])d[++cnt]=1;
	cout<<cnt<<'\n';rep(i,1,cnt)cout<<d[i]<<' ';cout<<'\n';
	rep(i,1,n){
		rep(j,1,cnt){
			if(abs(x[i])>abs(y[i])){
				if(x[i]<0){cout<<"L";x[i]+=d[j];}
				else{cout<<"R";x[i]-=d[j];}
			}
			else{
				if(y[i]<0){cout<<"D";y[i]+=d[j];}
				else{cout<<"U";y[i]-=d[j];}
			}
		}
		cout<<'\n';
	}
}