poj 1363 Rails 卡塔兰数 栈

缘起

【1】中讲述了组合数学中的卡塔兰数, 自然是需要找题目练一下的. poj 1363 Rails

分析

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
按1~n进栈，然后给出一个顺序，看能否按照这个顺序出栈

【输入】
多样例. 每个样例首先是n（<=1000）, 然后每行都是一个序列. 要你判断是否可能. 每个样例以0结束, 
整个输入以0结束

【输出】
Yes或者No, 不同样例空行分隔

【样例输入】
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

【样例输出】
Yes
No

Yes

【限制】
1s

开一个栈来模拟整个操作. 然后开一个bool数组ins表示某个数是否曾经入栈过. 则如果当前要出栈的数是x, 则首先看看ins[x]是否为true. 如果是的话, 则此时它一定要是栈顶元素. 如果ins[x]为false的话, 则一定要先将<x的所有ins为false的元素都入栈（即不曾入过栈的元素入栈）. 然后将x出栈. 例如 1 2 3 4 5 的出栈顺序为 1 5 … 则5不曾入栈过, 则要将<5的未曾入过栈的2、3、4都入栈. 然后5才出栈。 整个题其实就是一个模拟. 遂写下如下代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include "stdafx.h"
#include <stdio.h>
#include <stack>
using namespace std;
#include <string.h>
//#define LOCAL

const int maxn = 1005;
int n,a[maxn];
bool ins[maxn];

bool judge()
{
	stack<int> s;
	for (int i = 1; i<=n; i++)
	{
		if (ins[a[i]]) // 如果a[i]曾经入栈过
		{
			if (s.empty() || s.top()!=a[i]) // 则当前栈顶必须是a[i]
			{
				return false;
			}
			s.pop(); // 出栈
		}
		else // 如果a[i]不曾入栈过
		{
			int j = a[i];
			while(j&&!ins[j])
			{
				j--;
			} // 最后要么j=0要么ins[j]为true
			while(++j<a[i])
			{
				ins[j] = true;
				s.push(j);
			} // 入栈, a[i]就不必入栈了,反正入了也是要马上出栈的
			ins[a[i]] = true; // 虽然不必进栈, 但是依旧要记录a[i]曾经进栈过
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(scanf("%d", &n), n)
	{
		if (kase++)
		{
			puts("");
		}
		while(scanf("%d", a+1), a[1])
		{
			for (int i = 2; i<=n; i++)
			{
				scanf("%d", a+i);
			}
			memset(ins, 0, sizeof(ins));
			judge()?puts("Yes"):puts("No");
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 79ms
Memory 544kB
Length 1014
Lang G++
Submitted 2019-10-01 20:44:39
Shared
RemoteRunId 20915550

参考

【1】https://yfsyfs.github.io/2019/05/24/Catalan%E6%95%B0/