首页 > 代码库 > 11.12模拟考T1（可持续优化）PS：神奇的东西
11.12模拟考T1（可持续优化）PS：神奇的东西
1．数列操作
(array.pas/c/cpp)
【问题描述】
现在有一个数列，最初包含0个数。现在要对数列操作n次，操作有3类。
1） a k,在数列的最后插入一个整数k
2） s 将最近插入的数删除。
3） t k 将数列恢复第k次操作前的状态
下面是一个例子，有12个操作
1 a 5 -> [5] => 5 加入数5
2 a 3 -> [5,3] => 3 加入数3
3 a 7 -> [5,3,7] => 7 加入数7
4 s -> [5,3] => 3 删除数7
5 t 2 -> [5] => 5 回到操作2之前
6 a 2 -> [5,2] => 2 加入数2
7 t 4 -> [5,3,7] => 7 回到操作4之前
8 a 4 -> [5,3,7,4] => 4 加入数4
9 s -> [5,3,7] => 7 删除数4
10 t 7 -> [5,2] => 2 回到操作7之前
11 s -> [5] => 5 删除数2
12 s -> [] => -1 删除数5，数列空，输出-1.
【输入】
第一行一个整数N。
接下来N行，每行一个命令，格式如题目描述。
【输出】
N行，每次输出数列最后一个数的值，如果数列为空，输出-1。
【输入输出样例1】
array.in | array.out |
12 a 5 a 3 a 7 s t 2 a 2 t 4 a 4 s t 7 s s | 5 3 7 3 5 2 7 4 7 2 5 -1 |
【数据范围】
40% N<=100
60% N<=5000
100% 1 <= N <= 80,000 ，1 <= K <= 1,000,000.
思路：
前两个询问很水，但是第三个询问就有技术含量了。
60%可以用二维数组来搞；是80000的数据二维数组是存不下的。
那么问题来了。
怎样才能保存各种版本的栈。
当！当！！当！！！
“可持续优化”闪亮登场。
什么是“可持续优化”？
就是用邻接表一样的东西。把每一次更新的状态储存，以便下一次调用。
就是酱紫：
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<string> 5 #include<cstdio> 6 #include<cstdlib> 7 #include<algorithm> 8 #include<ctime> 9 #include<queue>10 #include<iomanip>11 using namespace std;12 const int maxn=500001;13 char q;14 int n,k,top=0;15 int len=0,linkk[maxn];16 int a[maxn];17 struct node18 {19 int x,y;20 }e[maxn];21 22 23 /*void init(int xx,int yy)24 {25 e[++len].y=linkk[xx];linkk[xx]=len;26 e[len].x=yy;27 }*/28 29 int main()30 {31 freopen("array.in","r",stdin);32 freopen("array.out","w",stdout);33 ios::sync_with_stdio(false);34 cin>>n;35 for(int i=1;i<=n;i++)36 {37 cin>>q;38 if(q==‘a‘)39 {40 cin>>k;41 a[++top]=k;42 e[i].x=e[i-1].y;e[i].y=top;43 linkk[top]=e[i].x;44 }45 if(q==‘s‘)46 {47 e[i].x=e[i-1].y;e[i].y=linkk[e[i-1].y];48 }49 if(q==‘t‘)50 {51 cin>>k;52 e[i].x=e[i-1].y;53 e[i].y=e[k].x;54 }55 if(a[e[i].y]==0)56 cout<<"-1"<<endl;57 else58 cout<<a[e[i].y]<<endl;59 }60 return 0;61 }
11.12模拟考T1（可持续优化）PS：神奇的东西