AHSOFNU NOIP模拟题-1 T1(模拟)

对于100%的数据,根据题目模拟即可
对于200%的数据,弃坑了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "type"
using namespace std;
const int MAXN = 100000 + 5;
int n, x, top;
char s[10], a[MAXN];
void clean() {
top = 0;
}
void solve() {
clean();
scanf("%d", &n);
for (int i=1;i<=n;i++) {
scanf("%s", s);
if (s[0]=='T') {
scanf("%s", s);
a[++top] = s[0];
} else if (s[0]=='U') {
scanf("%d", &x);
top -= x;
} else if (s[0]=='Q') {
scanf("%d", &x);
printf("%c\n", a[x]);
}
}
}
int main() {
freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
solve();
fclose(stdin), fclose(stdout);
return 0;
}

Problem 1 高级打字机
【题目描述】
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。
请为这种高级打字机设计一个程序,支持如下3种操作:
1.T x:在文章末尾打下一个小写字母x。(type操作)
2.U x:撤销最后的x次修改操作。(Undo操作)
(注意Query操作并不算修改操作)
3.Q x:询问当前文章中第x个字母并输出。(Query操作)
文章一开始可以视为空串。

【输入格式】
第1行:一个整数n,表示操作数量。
以下n行,每行一个命令。保证输入的命令合法。

【输出格式】
每行输出一个字母,表示Query操作的答案。

【样例输入】
7
T a
T b
T c
Q 2
U 2
T c
Q 2
【样例输出】
b
c
【数据范围】
对于40%的数据 n<=200;
对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。
<高级挑战>
对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。


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

------ 本文结束 ------