自动搬运

查看原文

来自洛谷，原作者为

	Ymy1201 一只正在摸鱼的蒟蒻||100%回关||忘关私我||暑假后小学六年级||玩火影Q区44439234846（是个小白）阿玛特拉斯

搬运于2025-08-24 23:18:01，当前版本为作者最后更新于2025-08-08 13:02:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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