[atARC103D]Robot Arms

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

令$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 }

巴特西

[atARC103D]Robot Arms

最新文章

热门文章