「NOIP模拟赛」高级打字机

2014年3月15日4,1549

高级打字机(type.cpp/c/pas)

「题目描述」

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。

请为这种高级打字机设计一个程序，支持如下3种操作：

1.T x：在文章末尾打下一个小写字母x。(type操作)

2.U x：撤销最后的x次修改操作。（Undo操作）

（注意Query操作并不算修改操作）

3.Q x：询问当前文章中第x个字母并输出。（Query操作）

文章一开始可以视为空串。

「输入格式」

第1行：一个整数n，表示操作数量。

以下n行，每行一个命令。保证输入的命令合法。

「输出格式」

每行输出一个字母，表示Query操作的答案。

「样例输入」

T a

T b

T c

Q 2

U 2

T c

Q 2

「样例输出」

「数据范围」

对于40%的数据 n<=200;

对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

题解

蒟蒻只会前100模拟

#include<iostream>
#include<cstdio>
using namespace std;
int n,top;
char a[100001];
int main()
{
    //freopen("type.in","r",stdin);
    //freopen("type.out","w",stdout);
    scanf("%d",&n);
    while(n--)
    {
         char ch[2];
         scanf("%s",ch);
         if(ch[0]=='T')cin>>a[++top];
         else if(ch[0]=='U')
         {
              int x;
              scanf("%d",&x);
              top-=x;
              }
         else 
         {
              int x;
              scanf("%d",&x);
              cout<<a[x]<<endl;
              }
         } 
    return 0;
    }