Ural 1220 Stacks 题解

发表于 更新于 分类于 ，
本文字数： 1.1k 阅读时长 ≈ 1 分钟

Ural 1220 Stacks 题解

题意

模拟若干个栈。

给定$n(1\le n\le 10^5)$个操作，每个操作有如下两个类型

  • PUSH a b，意为把b插入第a个栈中。
  • POP a，意为输出第a个栈的栈顶元素，并弹出栈顶。

$1\le a \le 10^3,0\le b\le 10^9$，保证操作无误，内存限制为0.75MB=768KB​。

题解

纯模拟会MLE(不知道有没有神仙可以卡过去)，不管是vector，stack还是其它的。

很容易想到用静态链表$v$维护，把所有的元素存储在同一个数组：

  • $v_i$有一个指针$p_i$指向这个栈中前一个元素。
  • 每个栈有$l_i$表示栈顶元素的下标。

但是这样仍然会MLE。

把$p$数组的类型换成unsigned short($[0,65536]$)，观察到$0\le v_i$。

若$p_i>65536$，让$v_i=-v_i$，$p_i=p_i-65536$。

执行POP操作时转换一下即可。

Tip: G++ 7.1还是MLE(796KB)，选用Visual C++ 2017可以通过(760KB)。

程序

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
38
39
40
41
42
43
44
#include <stdio.h>
#include <math.h>
using namespace std;

const int maxn=100001,maxm=1001,maxnum=65536;

int n,a,b,v[maxn],len,lst[maxm];
unsigned short poi[maxn];
char op[5];

int main()
{
	scanf("%d",&n);

	for(int i=0;i<n;i++)
	{
		scanf("%s%d",op,&a);

		if(op[1]=='U')
		{
			scanf("%d",&b);
			v[len++]=b;

			int id=len-1;

			if(lst[a]>maxnum)
			{
				poi[id]=lst[a]-maxnum;
				v[id]=-v[id];
			}
			else poi[id]=lst[a];

			lst[a]=id;
		}
		else
		{
			printf("%d\n",abs(v[lst[a]]));

			if(v[lst[a]]<0) lst[a]=poi[lst[a]]+maxnum; else lst[a]=poi[lst[a]];
		}
	}

	return 0;
}
__EOF__