CF538G Berserk Robot

题意:一个机器人在一个无穷大的网格图中,每秒能够上下左右走一步。它的行走方向序列是长度为l的循环。给你n个线索,包括ti:时间,xi,yi走到的坐标。让你构造出行走的方向序列?

标程:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll; 
 4 const int N=2000005;
 5 ll t,x,y,nx,ny;
 6 int n,l[N],r[N],len;
 7 struct node{ll ty,tz,x;node(){} node(ll A,ll B,ll C){ty=A;tz=B;x=C;}}a[N],b[N];
 8 bool operator < (const node &A,const node &B) {return A.ty<B.ty;}
 9 ll ceil(ll x,ll y)
10 {
11     if (x<0) x=-x,y=-y;
12     if (x==0) return 0;
13     if (y>0) return (x-1)/y+1;
14     else return x/y;
15 }
16 ll floor(ll x,ll y)
17 {
18    if (x<0) x=-x,y=-y;
19    if (x==0) return 0;
20     if (y>0) return x/y;
21     else return (x-1)/y-1;
22 }
23 void solve(node *a,int *ans)
24 {
25     sort(a+1,a+n+1);
26     ll L=0,R=len;    
27     a[n+1]=node(len,-1,0);//设置边界!!!
28     for (int i=0;i<=n;i++)//要统计入最后一个限制S[len]=0-S*(-1) 
29     {
30         ll d=a[i+1].ty-a[i].ty,q=a[i+1].x-a[i].x,p=a[i].tz-a[i+1].tz;
31         if (p>0)
32         {
33             L=max(L,ceil(-q,p));
34             R=min(R,floor(d-q,p));
35         }else if (p<0) {
36             L=max(L,ceil(d-q,p));
37             R=min(R,floor(-q,p));
38         }
39         if (L>R||p==0&&(q<0||q>d)) {puts("NO");exit(0);}
40     }
41     ll s=L,si=0;
42     for (int i=0,j=1;i<=n;i++)
43     {
44         si=(a[i+1].x-s*a[i+1].tz)-(a[i].x-s*a[i].tz);
45         while (si--) ans[j++]=1;
46         j=a[i+1].ty+1;//a[i+1]而不是a[i] 
47     }
48 }
49 int main()
50 {
51     scanf("%d%d",&n,&len);
52     for (int i=1;i<=n;i++)
53     {
54         scanf("%lld%lld%lld",&t,&x,&y);
55         nx=x+y+t;ny=x-y+t;
56         if (nx&1) return puts("NO"),0;
57         nx/=2;ny/=2;
58         a[i]=node(t%len,t/len,nx);
59         b[i]=node(t%len,t/len,ny);
60     }
61     solve(a,l);
62     solve(b,r);
63     for (int i=1;i<=len;i++) 
64       printf("%c","LDUR"[l[i]<<1|r[i]]);//此题的方向与常识相异! 
65     return 0;
66 }

易错点:1.注意设置l处的边界,要统计入最后一个限制S[len]=0-S*(-1),否则不等式不完整。

2.注意负数和0的上下取整。 

题解:转换+不等式构造

这道题思路非常喵!

将x,y坐标分开考虑,每次x坐标+-1,或y坐标+-1。难以处理。

设置(x+y,x-y)为新的参数,这样每次两个参数都会有+-1的变化。

再进一步,((x+y+t)/2,(x-y+t)/2)设置,每次要么+1,要么+0。

——以上是坐标和时间结合题的某种套路。

之后就是构造合法解的事情了。

这样对于一系列的t,由于l是循环节长度,设Sl为单位循环加了多少个1,S[i]表示i时间内加了多少个1,可以列出等式S[t%l]=Xi-Sl*[t/l]。

以及由相邻依次递增的t%i列出一系列不等式:0<=Sb-Sa<=b-a。整体化成0<=p*Sl+q<=d的形式,可以解出Sl的取值范围,取范围中的任意值皆可。

这样可以解出所有S[t%l],直接按区间填上对应数量的1即可。

原文地址:https://www.cnblogs.com/Scx117/p/9089100.html