题解 P1383 【高级打字机】

芬特 · 2017-05-07 15:18:23 · 题解

前50分栈模拟非常好想，先给出100分ac离线做法，我们可以使用前向星法建立一个邻接链表，把所有操作下的情况强行建一个版本，然后每次遇到undo操作就把邻接链表的指针向上指x个版本，这样可以使用一个搜索从上搜下去，然后按照输入的query命令将答案放到一个数组里，最后输出这个数组

说起来容易，实现过程很重要，建议自己手打一遍，代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100010;
int n,q,x,v,sz,tot;
int father[maxn],head[maxn],Next[maxn],point[maxn];
int ans[maxn];
char ch,a[maxn],sk[maxn];

vector <int> maint[maxn];

void Ins(int u,int v)
{
    Next[++sz]=head[u];head[u]=sz;point[sz]=v;
}
void Type()
{
    scanf("%s",&ch);
    a[tot]=ch;
    tot++;
    father[tot]=tot-1;

}
void Undo()
{
    scanf("%d",&x);
    tot++;
    Ins(tot-x-1,tot);
    father[tot]=tot-x-1;
}
void Query()
{
    scanf("%d",&x);
    maint[tot].push_back(q);
    ans[q++]=x;
}

void init()
{
    tot=x=0;
    for(x=0;;)
    {
        if (head[x])
        {
            v=point[head[x]];
            head[x]=Next[head[x]];
            x=v;continue;
        }
        if (a[x])
        {
            sk[++tot]=a[x];
            a[x]=0;
            x++;continue;
        }
        rep(i,maint[x].size())
        {
            v=maint[x][i];
            ans[v]=sk[ans[v]];
        }
        if (father[x]+1==x) tot--;
        if (!x) return;
        x=father[x];
    }
}
int main()
{
    //freopen("type.in","r",stdin);
    //freopen("type.out","w",stdout);
    scanf("%d\n",&n);
    rep(i,n)
    {
        scanf("%s",&ch);
        switch (ch)
        {
            case 'T':Type();break;
            case 'U':Undo();break;
            case 'Q':Query();break;
        }
    }
    init();
    rep(i,q) printf("%c\n",ans[i]);
    return 0;
}

IOI挑战可以用主席树做，但是并不会……