题解：P12776 [POI 2018/2019 R1] 小机器人 Robby the little robot

· · 题解

吐槽：我竟然是第一个过的入，但好像不是正解。

P12776 [POI 2018/2019 R1] 小机器人 Robby the little robot

题目大意

这道题要我们模拟一个机器人移动，第 i 次移动走 d_i 格，然后右转 90^\circ，耗时 d_i+1 秒，问 t 秒后经过 (a,b) 这个点多少次。

分析

如果直接模拟，只通过了 1，2 子任务，连 0 子任务测试点都 TLE 了一个点，那有哪可以优化呢？

看这组样例：
4 30 2 3 2 3 3 2

是不是发现了什么？对！一轮下来后机器人又回到了 (0,0)，并且方向是北，那么就会一直转圈圈！

如果 n 是 4 的倍数并且一轮过后回到了 (0,0) 或者 n 不是 4 的倍数，4 轮过后一样可以转圈圈。

那我们就可以写出这份代码：

#include<bits/stdc++.h>
using namespace std;
long long n,t,t2,d[100001],a,b,x,y,z,ans,ans2,e;
/*t2是备份
  a是列，b是行
  x是行，y是列
  z是应该走d数组的哪一个
  ans是次数
  ans2是特殊情况（x=0，y=0）
  e是方向
*/
int main() {
//  freopen("a.in","r",stdin);
    scanf("%lld%lld",&n,&t);
    t2=t;
    for(int i=1; i<=n; i++)scanf("%lld",d+i);
    scanf("%lld%lld",&a,&b);
    if(a==0&&b==0)ans2=1;
    while(t>0) {
        z++;
        if(z>n) {
            z=1;
            //重复的话ans就直接乘会重复多少组，再把多出来的算一下
            if(x==0&&y==0&&e==0) {
                ans*=t/(t2-t)+1;
                t%=t2-t;
            }
        }
        if(e==0) {//北（上）
            long long v=x;
            x+=d[z];
            t-=abs(x-v);
            if(t<0)x+=t;//d[z]大于t的情况
            if(x>=b&&y==a&&/*经过*/v<b)ans++;
        } else if(e==1) {//东（右）
            long long v=y;
            y+=d[z];
            t-=abs(y-v);
            if(t<0)y+=t;//同上
            if(x==b&&y>=a&&/*经过*/v<a)ans++;
        } else if(e==2) {//南（下）
            long long v=x;
            x-=d[z];
            t-=abs(v-x);
            if(t<0)x-=t;//同上
            if(x<=b&&y==a&&/*经过*/v>b)ans++;
        } else {//西（左）
            long long v=y;
            y-=d[z];
            t-=abs(v-y);
            if(t<0)y-=t;//同上
            if(x==b&&y<=a&&/*经过*/v>a)ans++;
        }
        (e+=1)%=4;
        t--;
    }
    printf("%lld",ans+ans2);
    return 0;
}

完美的 TLE 了。

ber，怎么还是 TLE，注意，前面说的是：
如果 n 是 4 的倍数并且一轮过后回到了 (0,0) 或者 n 不是 4 的倍数，4 轮过后一样可以转圈圈。

如果 n 是 4 的倍数，但一轮过后没有回到 (0,0) 呢？

那咱们只要弄个计数器，如果循环的次数大于 10^{9}，就可以输出了。

完整代码

#include<bits/stdc++.h>
using namespace std;
long long n,t,t2,d[100001],a,b,x,y,z,ans,ans2,e,sum;
int main() {
//  freopen("a.in","r",stdin);
    scanf("%lld%lld",&n,&t);
    t2=t;
    for(int i=1; i<=n; i++)scanf("%lld",d+i);
    scanf("%lld%lld",&a,&b);
    if(a==0&&b==0)ans2=1;
    while(t>0) {
        z++;
        if(z>n) {
            z=1;
            if(x==0&&y==0&&e==0) {
                ans*=t/(t2-t)+1;
                t%=t2-t;
            }
        }
        if(e==0) {
            long long v=x;
            x+=d[z];
            t-=abs(x-v);
            if(t<0)x+=t;
            if(x>=b&&y==a&&v<b)ans++;
        } else if(e==1) {
            long long v=y;
            y+=d[z];
            t-=abs(y-v);
            if(t<0)y+=t;
            if(x==b&&y>=a&&v<a)ans++;
        } else if(e==2) {
            long long v=x;
            x-=d[z];
            t-=abs(v-x);
            if(t<0)x-=t;
            if(x<=b&&y==a&&v>b)ans++;
        } else {
            long long v=y;
            y-=d[z];
            t-=abs(v-y);
            if(t<0)y-=t;
            if(x==b&&y<=a&&v>a)ans++;
        }
        (e+=1)%=4;
        t--;
        if(++sum>1e9)break;
    }
    printf("%lld",ans+ans2);
    return 0;
}
\cancel{2.58秒}