hdu 1022 Train Problem I 卡塔兰数 栈

缘起

继续学习出栈次序. hdu 1022 Train Problem I

分析

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
输入n列火车，然后分别输入火车的入站顺序和出站顺序，问能否出站。

【输入】
多样例. 每个样例开始于一个N(N<=9),表示火车的数量. 然后是一个字符串表示入栈顺序, 然后是一个字符串表示
出栈顺序,

【输出】
对每个样例输出Yes或者No, 对于Yes的情形, 输出方案

【样例输入】
3 123 321
3 123 312

【样例输出】
Yes.
in
in
in
out
out
out
FINISH
No.
FINISH

【限制】
1s

和【1】差不多. 只不过入栈的顺序未必是1,…,n, 纵观【1】的代码, 这点区别其实不是本质的（完全可以在读入的时候进行预处理, 例如213为入栈顺序,则可以预处理将2映射为1, 1映射为2, 3映射为3, 自然out也要做相应的改变, 做这种预处理不是必要的, 但是为了复用【1】的代码更加顺手而已）. 但是还需要在可行的时候输出方案。这只需要在判断的时候维护一下即可.

代码没怎么写注释, 注释详见【1】

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//#include "stdafx.h"
#include <stdio.h>
#include <stack>
using namespace std;
#include <string.h>
//#define LOCAL

int n, ans[50000], top, map[15], outt[15]; // 18中选9个位置
char in[15], out[15];
bool ins[15];

bool judge()
{
	stack<int> s;
	for (int i = 1; i<=n ;i++)
	{
		if (ins[outt[i]])
		{
			if (s.empty()||s.top()!=outt[i])
			{
				return false;
			}
			ans[top++] = 0; // 出栈
			s.pop();
		}
		else
		{
			int j = outt[i];
			while(j && !ins[j])
			{
				j--;
			}
			while(++j<outt[i])
			{
				ins[j] = true;
				s.push(j);
				ans[top++] = 1; // 入栈
			}
			ins[outt[i]] = true;
			ans[top++] = 1; // outt[i]入栈
			ans[top++] = 0; // outt[i]出栈
		}
	}
}

void process() // 将in进行映射成1~n, 相应的,out也要进行映射为outt
{
	for (int i = 0; in[i]; i++)
	{
		map[in[i]-'0'] = i+1;
	}
	for (int i = 0; out[i]; i++)
	{
		outt[i+1] = map[out[i]-'0'];
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		scanf("%s%s", in, out);
		process();
		memset(ins, 0, sizeof(ins));
		top = 0;
		if (!judge())
		{
			puts("No.");
		}
		else
		{
			puts("Yes.");
			for (int i = 0; i<top; i++)
			{
				ans[i]?puts("in"):puts("out"); // ans为1代表入,0代表出
			}
		}
		puts("FINISH");
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 1264kB
Length 1256
Lang G++
Submitted 2019-10-07 21:10:36
Shared
RemoteRunId 30793448

参考

【1】https://yfsyfs.github.io/2019/10/01/poj-1363-Rails-%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0-%E6%A0%88/