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

a 5

a 3

a 7

t 2

a 2

t 4

a 4

t 7

-1

【数据范围】

40% N<=100

60% N<=5000

100%  1 <= N <= 80,000 ，1 <= K <= 1,000,000.

思路：

前两个询问很水，但是第三个询问就有技术含量了。

60%可以用二维数组来搞；是80000的数据二维数组是存不下的。

那么问题来了。

怎样才能保存各种版本的栈。

当！当！！当！！！

“可持续优化”闪亮登场。

什么是“可持续优化”？

就是用邻接表一样的东西。把每一次更新的状态储存，以便下一次调用。

就是酱紫：

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<string>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<ctime>

 #include<queue>

 #include<iomanip>

 using namespace std;

 const int maxn=;

 char q;

 int n,k,top=;

 int len=,linkk[maxn];

 int a[maxn];

 struct node

 {

     int x,y;

 }e[maxn];

 /*void init(int xx,int yy)

 {

     e[++len].y=linkk[xx];linkk[xx]=len;

     e[len].x=yy;

 }*/

 int main()

 {

     freopen("array.in","r",stdin);

     freopen("array.out","w",stdout);

     ios::sync_with_stdio(false);

     cin>>n;

     for(int i=;i<=n;i++)

     {

         cin>>q;

         if(q=='a')

         {

             cin>>k;

             a[++top]=k;

             e[i].x=e[i-].y;e[i].y=top;

             linkk[top]=e[i].x;

         }

         if(q=='s')

         {

             e[i].x=e[i-].y;e[i].y=linkk[e[i-].y];

         }

         if(q=='t')

         {

             cin>>k;

             e[i].x=e[i-].y;

             e[i].y=e[k].x;

         }

         if(a[e[i].y]==)

             cout<<"-1"<<endl;

         else

             cout<<a[e[i].y]<<endl;

     }

     return ;

 }

巴特西

11.12模拟考T1（可持续优化）PS：神奇的东西

最新文章

热门文章