题解：P9804 [POI 2022/2023 R1] kol

· · 题解

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

思路

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

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

用 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