题目描述

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

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

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

U x：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作）

Q x：询问当前文章中第x个字母并输出。（Query操作）文章一开始可以视为空串。

输入

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

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

输出

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

数据

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

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

<高级挑战>

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

蒟蒻分析

其实IOI挑战那部分对限制也没啥帮助。。。看这数据点，幸好他不卡数据。

我们可以设个[1..20000]的滚动数组(This is why I said that just now)l[i]表示第i个状态时的字符串。撤回操作只用将状态设回前面就够了。

好奇宝宝倾情赞助提问时间

上面那题目都是瞎搞，你自己点开我职业看看我才中学生好伐。。。

为甚只用20000？

数据不想卡死你。

为什么你能过？

因为我长得帅。

能发源码吗？

哎呀，你想得太天真啦！我是那种让你们一点思考空间都没有直接复制的人吗？我像吗？

var

        n,i,p,g,m:longint;

        l:array[0..20000]of ansistring;

        s,x:char;

begin

        readln(n);

        for i:=1 to n do

        begin

                read(s);

                read(x);

                if (s='T') then

                begin

                        readln(x);

                        g:=p mod 20000+1;

                        l[g]:=l[p]+x;

                        p:=g;

                end;

                if (s='U') then

                begin

                        readln(m);

                        p:=p mod 20000+1;

                        l[p]:=l[(p-m+19999)mod 20000];

                end;

                if (s='Q') then

                begin

                        readln(m);

                        writeln(l[p,m]);

                end;

        end;

end.

巴特西

【NOIP2014模拟】高级打字机

题目描述

输入

输出

数据

蒟蒻分析

好奇宝宝倾情赞助提问时间

最新文章

热门文章