1124-1127
徐仓仓 Lv3
  2022-08-22 22:00:44 2022-08-22 22:00    

📅time:8.21 - 8.22

🍔题目：

1124 Raffle for Weibo Followers
1125 Chain the Ropes
1126 Eulerian Path
1127 ZigZagging on a Tree 中序+后序=>回旋输出

附录

1124 Raffle for Weibo Followers

简单到无语

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<set>
using namespace std;
int M, N, S;
string s[1010];
set<string> P;
int main() {
	cin >> M >> N >> S;
	for (int i = 1; i <= M; i++) {
		cin >> s[i];
	}
	int i = S;
	while (i <= M) {
		while (P.count(s[i]) != 0) i++;
		cout << s[i] << endl;
		P.insert(s[i]);
		i = i + N ;
	}
	if (P.size() == 0)
		cout << "Keep going...\n";
}

1125 Chain the Ropes

没重新做

1126 Eulerian Path

注意要判断是否是连通图

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
#include<iostream>
using namespace std;
int N, M;
int G[510][510];
bool flag[510];
int vertex[510];
int cnt = 0;
void DFS(int r) {
	cnt++;
	flag[r] = true;
	for (int i = 1; i <= N; i++) {
		if (!flag[i] && G[r][i]) {
			DFS(i);
		}
	}
}
int main() {
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		vertex[a]++;
		vertex[b]++;
		G[a][b] = 1;
		G[b][a] = 1;
	}
	DFS(1);
	int n = 0, flag = 1;
	for (int i = 1; i <= N; i++) {
		printf("%d", vertex[i]);
		if (i != N) printf(" ");
		else printf("\n");
		if (vertex[i] % 2 != 0) {
			n++;
		}
	}
	if (cnt == N && n == 0) cout << "Eulerian\n";
	else if (cnt == N && n == 2) cout << "Semi-Eulerian\n";
	else cout << "Non-Eulerian\n";
}

1127 ZigZagging on a Tree

注意travel的参数

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
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int N;
int in[35];
int post[35];
struct node {
	int data;
	node* left = NULL, * right = NULL;
};
stack<node*>zigL;
stack<node*>zigR;
node* travel(int inL, int inR, int postL, int postR) {
	if (inR < inL) return NULL;
	int i = inL;
	for (; i <= inR; i++) {
		if (in[i] == post[postR]) {
			break;
		}
	}
	node* p = new node();
	p->data = in[i];
	p->left = travel(inL, i - 1, postL, postL + i - 1 - inL );
	p->right = travel(i + 1, inR, postL + i - inL, postR - 1);
	return p;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> in[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> post[i];
	}
	node* root = NULL;
	root = travel(0, N - 1, 0, N - 1);
	zigL.push(root);
	cout << root->data;
	int num = 1;
	if (num != N) printf(" ");
	while (!zigL.empty() || !zigR.empty()) {
		while (!zigL.empty()) {
			node* top = zigL.top();
			zigL.pop();
			if (top->left != NULL) {
				num++;
				cout << top->left->data ;
				if (num != N) printf(" ");
				zigR.push(top->left);
			}
			if (top->right != NULL) {
				num++;
				cout << top->right->data ;
				if (num != N) printf(" ");
				zigR.push(top->right);
			}
		}
		while(!zigR.empty() ){
			node* top = zigR.top();
			zigR.pop();
			if (top->right != NULL) {
				num++;
				cout << top->right->data ;
				if (num != N) printf(" ");
				zigL.push(top->right);
			}
			if (top->left != NULL) {
				num++;
				cout << top->left->data ;
				if (num != N) printf(" ");
				zigL.push(top->left);
			}
		}
	}
}
 Comments