USACO44 TimeTravel 时间旅行（链表）

第一眼看到这题，woc，这不是主席树！？旁边HZ也表示同意，然后cGh队长就慢悠悠的过来：“想什么，USACO会有主席树！？”

↓打脸不解释，大家可以去%ta的博客(这样ta就不会D飞我了~)http://blog.csdn.net/cgh_andy/article/details/53012348

既然师兄都说链表了，如果用主席树（就是可持久化线段树啦）水，不是很不给面子......

所以就学了一发，果然又快又短~其实代码很好理解的（强行引用）

我们设c[i]为i位置最近买的牛 f[i]表示上一个状态是哪个位置

对于三个操作买：c[i]=x f[i]=i-1

卖：c[i]=c[ f[i-1] ] f[i]=f[ f[i-1] ]

跳：c[i]=c[k-1] f[i]=f[k-1]

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

using namespace std;

int f[],c[];

char ss[];

int main()

{

    freopen("ttravel.in","r",stdin);

    freopen("ttravel.out","w",stdout);

    int n,x;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%s",ss+);

        if(ss[]=='a')

            scanf("%d",&x), f[i]=i-, c[i]=x;

        else if(ss[]=='s')

            f[i]=f[f[i-]], c[i]=c[f[i-]];

        else

            scanf("%d",&x), f[i]=f[x-], c[i]=c[x-];

        if(c[i]!=)printf("%d\n",c[i]);

        else printf("-1\n");

    }

    return ;

}

巴特西

USACO44 TimeTravel 时间旅行（链表）

最新文章

热门文章