自动搬运

查看原文

来自洛谷，原作者为

	hema5177 (^u^)｜关注651883谢谢喵qwq |互关私信qwq，都会同意的qwq |但是必须要私信QAQ

搬运于2025-08-24 22:51:59，当前版本为作者最后更新于2025-07-21 10:56:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道模拟题，但不能硬模拟。如果你想硬模拟的话，可以试试这道题。

思路

题解中很多大佬都提到了时间戳。简而言之，时间戳像就是记录蛇的足迹，只不过将足迹标注了蛇最近经过的时间，而通过这个时间就可以判断现在蛇在不在询问的坐标上。

那么如何判断呢？这时可以计算经过询问点与蛇头现在所在的点的时间差。时间差可以看作是如果蛇尾恰好刚离开询问点，而蛇头在当前位置时，这一条蛇的长度（不是真正的蛇）。

用 $now$ 表示当前时间，用 $t[x][y]$ 表示经过询问点的时间，则时间差为 $now-t[x][y]$。由上面对于时间差的假设可得，如果蛇尾恰好在询问点上的话，这条蛇的长度应为 $now-t[x][y]+1$。而如果蛇的真正长度小于这个长度，则询问点上没有蛇身，输出 $-1$。

如果有蛇身怎么表示呢？我们知道了蛇尾恰好在询问点上时蛇身的长度应为 $now-t[x][y]+1$，而蛇的编号是从蛇尾到蛇头依次编号，所以易得 $l-(now-t[x][y]+1)+1$ 是当前蛇身的编号（如果下标从 $1$ 开始）。化简得 $l-now+t[x][y]$ 是询问点蛇身的编号，输出即可。

其余细节不赘述了，还不理解可以看代码注释。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int m,p,n,check[2001][2001],t[2001][2001],now=1;
int snake[1000001],l=1,nowx=1,nowy=1;
//snake表示蛇，l为蛇的长度，nowx，nowy表示现在蛇头所在的坐标（操作完成后） 
void check_code()
{
	cout<<"Food:\n";
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(check[i][j]) cout<<check[i][j]-1<<" ";
			else cout<<check[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	cout<<"Move time:\n";
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++) cout<<t[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	cin>>m>>p>>n;
	t[1][1]=1;
	while(p--)
	{
		int x,y,v;
		cin>>x>>y>>v;
		check[x][y]=v+1;//要+1是因为要与没有食物的区分开来，后面再减就行了 
	}
	while(n--)
	{
		char a;
		cin>>a;
		if(a=='Z')
		{
			int x,y;
			cin>>x>>y;
			if(l<now-t[x][y]+1) cout<<"-1\n";
			else cout<<snake[l-(now-t[x][y])]<<endl;
			continue;//询问操作蛇没有动，所以不能更新now 
		}
		now++;
		if(a=='G') nowx--;
		if(a=='D') nowx++;
		if(a=='L') nowy--;
		if(a=='P') nowy++;
		t[nowx][nowy]=now;//时间戳，记录蛇头到达此位置时的时间 
		if(check[nowx][nowy])
		{
			snake[++l]=check[nowx][nowy]-1;//有食物就更新食物为蛇头 
			check[nowx][nowy]=0;//食物不能重复吃 
		}
		//check_code();
		//可以用上面的函数帮助理解qwq 
	}
}//希望模拟萌新能看懂qwq