合法的必要条件是每个点两维坐标和奇偶性相同，同时这也是充分条件

令$d_{i}=\{2^{0},2^{1},...,2^{m-1}\}$，归纳其可以走到任意满足$|x|+|y|<2^{m}$的$(x,y)$，考虑先确定其最后一步，即对于$|x|+|y|<2^{m+1}$，通过$d=2^{m}$使其走到$|x'|+|y'|<2^{m}$的位置

不妨假设$|x|<|y|$，则有$|x|<2^{m}$，然后令$y'=y-sign(y)\cdot 2^{m}$，对$|y|$分类讨论：

1.$|y|<2^{m}$，此时$|x|+|y'|=|x|+2^{m}-|y|<2^{m}$

2.$|y|\ge 2^{m}$，此时$|x|+|y'|=|x|+|y|-2^{m}<2^{m+1}-2^{m}=2^{m}$

还有初始条件，当$d=\{2^{0}\}$，发现要保证$|x|+|y|=1$才合法，换言之若两个数和为偶数则不合法，对于这种情况，强制先走到$(1,0)$即可

由此，即证明上述结论，同时得出构造方法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1005
 4 int n,x[N],y[N];
 5 int sign(int k){
 6     if (k>0)return 1;
 7     return -1;
 8 }
 9 int main(){
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
12     int p=(abs(x[1]+y[1])&1);
13     for(int i=2;i<=n;i++)
14         if ((abs(x[i]+y[i])&1)!=p){
15             printf("-1");
16             return 0;
17         }
18     printf("%d\n",(31+(!p)));
19     for(int i=30;i>=0;i--)printf("%d ",(1<<i));
20     if (!p){
21         printf("1");
22         for(int i=1;i<=n;i++)x[i]--;
23     }
24     printf("\n");
25     for(int i=1;i<=n;i++){
26         for(int j=30;j>=0;j--){
27             if (abs(x[i])<abs(y[i])){
28                 if (y[i]>0)printf("U");
29                 else printf("D");
30                 y[i]=y[i]-sign(y[i])*(1<<j);
31             }
32             else{
33                 if (x[i]>0)printf("R");
34                 else printf("L");
35                 x[i]=x[i]-sign(x[i])*(1<<j);
36             }
37         }
38         if (!p)printf("R");
39         printf("\n");
40     }
41 } 

View Code