1120-1123
徐仓仓 Lv3
  2022-08-22 14:00:44 2022-08-22 14:00    

📅time:8.21 - 8.22

🍔题目：

1120 Friend Numbers
1121 Damn Single
1122 Hamiltonian Cycle
1123 Is It a Complete AVL Tree 💖💖💖

AVL树

🎈1123 Is It a Complete AVL Tree

层序遍历时判断是否是完全二叉树

基本的插入操作

附录

1120 Friend Numbers 20分

简单到无语

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
#include<iostream>
#include<set>
using namespace std;
int N;
int num;
set<int>ans;
int cal(int num) {
	int a = 0;
	while (num != 0) {
		a += num % 10;
		num = num / 10;
	}
	return a;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		ans.insert(cal(num));
	}
	cout << ans.size() << endl;
	int i = 0;
	for (auto it = ans.begin(); it != ans.end();it++) {
		cout << *it;
		i++;
		if (i != ans.size()) cout << " ";
	}
}

1121 Damn Single 25分

简单得离谱

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
#include<iostream>
#include<set>
#include<vector>
#include<map>
using namespace std;
int N, M;
map<int, int>marry;
set<int>alone;
bool first[100010];
int main() {
	cin >> N;
	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		marry[a] = b;
		marry[b] = a;
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a;
		if (marry.count(a) == 0) {
			alone.insert(a);
		}
		else if (first[marry[a]] == false) {
			first[a] = true;
			alone.insert(a);
		}
		else {
			alone.erase(marry[a]);
		}
	}
	cout << alone.size() << endl;
	int i = 0;
	for (auto it = alone.begin(); it != alone.end(); it++) {
		printf("%05d", *it);
		i++;
		if (i != alone.size()) printf(" ");
	}
}

1122 Hamiltonian Cycle 25分

很简单

唯一的难点是题目的意思需要想一想

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
#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
int G[202][202];
bool flag[202];
int main() {
	int N, M;
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		G[a][b] = 1;
		G[b][a] = 1;
	}
	int K, num;
	cin >> K;
	for (int i = 0; i < K; i++) {
		bool cycle = true;
		cin >> num;
		if (num != N + 1) {
			cycle = false;
			string s;
			getline(cin, s);
		}
		else {
			fill(flag, flag + 202, false);
			int start, p;
			cin >> start;
			int pre = start;
			for (int i = 1; i < num; i++) {
				cin >> p;
				if (!G[pre][p]||flag[p]) { 
					cycle = false; 
					//break;
				}
				pre = p;
				flag[p] = true;
			}
			if (p != start) cycle = false;
		}
		if (!cycle) cout << "NO\n";
		else cout << "YES\n";
	}
}

1123 Is It a Complete AVL Tree 26分

很简单，但是我忘记AVL树了，偷看了一下笔记

测试点4、5：判断是否为完全二叉树出错。我通过计算左子树高度减右子树高度，若小于0或者大于1则不是二叉树。但对于倒数第二层，每个结点有一个左结点的情况会出错。

正确方法：层序遍历时若是有一个结点没有左子树或右子树，flag=true,继续遍历，若是接下来的结点有左子树或右子树，则不是完全二叉树。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
struct node {
	int data;
	int hight = 1;//注意初始高度为1
	node* left = NULL, * right = NULL;
};
queue<node*>layer;
vector<int>ans;
int gethight(node* r) {
	if (r == NULL) return 0;//注意对于NULL的判断
	else return r->hight;
}
int balance(node *r) {
	return gethight(r->left) - gethight(r->right);
}
void update(node* r) {
	r->hight = max(gethight(r->left), gethight(r->right)) + 1;//注意最后高度要+1
}
void R(node* &r) {
	node* temp = r->left;
	r->left = temp->right;
	temp->right = r;
	update(r);//注意更新结点高度
	update(temp);
	r = temp;
}
void L(node* &r) {
	node* temp = r->right;
	r->right = temp->left;
	temp->left = r;
	update(r);
	update(temp);
	r = temp;
}
void insert(node* &root,int n) {
	if (root == NULL) {
		root = new node();
		root->data = n;
		return;
	}
	if (n < root->data) {
		insert(root->left, n);
		update(root);
		if (balance(root)>=2) {
			if (balance(root->left) < 0) {
				L(root->left);
			}
			R(root);
		}
	}
	else {
		insert(root->right, n);
		update(root);
		if (balance(root) <= -2) {
			if (balance(root->right) > 0) {
				R(root->right);
			}
			L(root);
		}
	}
}
int main() {
	cin >> N;
	node* root = NULL;//注意要置root为NULL，不然第一步插入if (root == NULL)就出错
	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		insert(root, num);
	}
	layer.push(root);
	bool flag = true;
	int after = 0;
	while (!layer.empty()) {
		node* top = layer.front();
		layer.pop();
		ans.push_back(top->data);
		if (top->left != NULL) {
			layer.push(top->left);
			if (after) flag = false;
		}
		else after = 1;
		if (top->right != NULL) {
			layer.push(top->right);
			if (after) flag = false;
		}
		else after = 1;
	}
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i];
		if (i != ans.size() - 1) cout << " ";
	}
	cout << endl;
	if (flag) cout << "YES";
	else cout << "NO";
}
 Comments