XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 6-1UVa673 6-2UVa712 6-3UVa536

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

这三题比较简单，只放代码了。

题目：6-1 UVa673 - Parentheses Balance 

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
//UVa673 - Parentheses Balance
//Accepted 0.000s
//#define _XIENAOBAN_
#include<iostream>
using namespace std;

int N;
char line[130];
bool st[130];
bool cal() {
	if (*line == '\0') return true;
	auto *p = line;
	auto *top = st;
	do {
		switch (*p)
		{
		case '(': *++top = false;break;
		case '[': *++top = true;break;
		case ')':
			if (top == st || *top) return false;
			--top;
			break;
		default:
			if (top == st || !*top) return false;
			--top;
			break;
		}
	} while (*++p != '\0');
	return top == st;
}


int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 129)
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	scanf("%d",&N);
	getchar();
	while (N--) {
		gets(line);
		cout << (cal() ? "Yes" : "No") << '\n';
	}

	return 0;
}

题目：6-3 UVa712 - S-Trees

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
//UVa712 - S-Trees
//Accepted 0.000s
//#define _XIENAOBAN_
#include<iostream>
using namespace std;

int N(0);
int n, m, ord[10], run[10], val[130];

int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 129)
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif

	while (scanf("%d", &n) != EOF && n != 0) {
		printf("S-Tree #%d:\n", ++N);
		int num(1 << n);
		for (int i(1);i <= n;++i) {
			while (getchar() != 'x');
			ord[i] = getchar() - 48;
		}
		while (getchar() != '\n');
		for (int i(0);i < num;++i)
			val[i] = getchar() - 48;
		scanf("%d", &m);
		for (int i(0);i < m;++i) {
			while (getchar() != '\n');
			for (int j(1);j <= n;++j)
				run[j] = getchar() - 48;
			int ans(1);
			for (int j(1);j <= n;++j)
				ans = (ans << 1) + run[ord[j]];
			printf("%d", val[ans - num]);
		}
		printf("\n\n");
	}
	return 0;
}

题目：6-3 UVa536 - Tree Recovery

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
//UVa536 - Tree Recovery
//Accepted 0.000s
//#define _XIENAOBAN_
#include<iostream>
#include<cstring>
using namespace std;

char pre[30], in[30];

void cal(char *pre, char *in, int len) {
	int root(0);
	while (*(in + root) != *pre) ++root;
	if (root) cal(pre + 1, in, root);
	if (len - root - 1) cal(pre + root + 1, in + root + 1, len - root - 1);
	printf("%c", *pre);
}


int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 129)
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif

	while (scanf("%s%s", pre, in) != EOF) {
		cal(pre, in, strlen(in));
		puts("");
	}
	return 0;
}