题解 P2069 【松鼠吃果子】

· · 题解

推荐一波数组模拟链表的讲解

一道不错的链表题，看到题解里没有数组模拟链表写法，特意补充一发

这道题呢，数组写的话不好删除（因为后面要接过来），自然想到链表

对于一个果子，我们可以维护其前驱和后继，我们不妨记与一个点相邻的上面的点为其前驱，下面的点为其后继

观察到题目要求我们完成两种操作

1，跳，即遍历链表

2，吃，即删除链表中元素

具体来讲

删除就是普通的删除，不再赘述

跳

for(;s&&pos;s--,pos=fa[pos]);   //s为步数

把最上面果子的前驱设为0

跳过了，就把松鼠的位置pos移至1重新跳

观察到这题1号果子是不会被吃的，即head指针不会发生变化

初始化等具体的细节见代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=210;
int n,m,son[maxn],fa[maxn],pos=1;   //son记录后继、fa记录前驱、pos记录松鼠位置
void skip(int s)    //往上跳
{
    for(;s&&pos;s--,pos=fa[pos]);
}
void del(int x)     //链表的删除操作
{
    pos=fa[x];      //更新松鼠的位置
    fa[son[x]]=fa[x];
    son[fa[x]]=son[x];
    fa[x]=son[x]=-1;    //被删之后扔掉它
}
int main()
{
    cin>>n>>m;
    fa[1]=2,son[n]=n-1;
    for(int i=2;i<n;i++)
        fa[i]=i+1,son[i]=i-1;   //初始化
    for(int i=1;i<=m;i++)
    {
        int s=i*i*i%5+1;
        skip(s);
        if(!pos)    //跳出去，重新跳
        {
            pos=1;
            skip(s);
        }
        if(i==m)    //第m次
        {
            cout<<pos<<endl;
            return 0;
        }
        del(pos);
    }
    return 0;
}