1144-1147
徐仓仓 Lv3
  2022-08-26 13:00:44 2022-08-26 13:00    

📅time:8.26

🍔题目：

1144 The Missing Number
1145 Hashing - Average Search Time 题目不懂
1146 Topological Order
1147 Heaps

Quadratic ：平方

附录

1144 The Missing Number

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
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
set<int>num;
int main() {
	int N;
	cin >> N;
	int a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		num.insert(a);
	}
	auto it = num.begin();
	for (; it != num.end(); it++) {
		if (*it > 0)break;
	}
	int n = 1;
	while (it != num.end()) {
		if (*it != n) {
			break;
		}
		it++;
		n++;
	}
	cout << n;
}

1145 Hashing - Average Search Time

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
#include<iostream>
using namespace std;
int Tsize, N, M;
bool prime[10010];
int num[10010];
void cal_prime() {
	for (int i = 2; i < 10010; i++) {
		if (!prime[i]) {
			for (int j = i + i; j < 10010; j += i) {
				prime[j] = true;
			}
		}
	}
}
void insert(int n) {
	for (int i = 0; i < Tsize; i++) {
		if (num[(n + i * i)%Tsize] == -1) {
			num[(n + i * i) % Tsize] = n;
			return;
		}
	}
	printf("%d cannot be inserted.\n",n);
}
int cnt = 0;
void find(int n) {
	for (int i = 0; i < Tsize; i++) {
		cnt++;
		if (num[(n+i*i)%Tsize]==-1||num[(n + i * i) % Tsize] == n) {
			return;
		}
	}
	cnt++;
}
int main() {
	cal_prime();
	cin >> Tsize >> N >> M;
	if (prime[Tsize]) {
		for (int i = Tsize; i < 10010; i++) {
			if (!prime[i]) {
				Tsize = i;
				break;
			}
		}
	}
	int a;
	fill(num, num + Tsize, -1);
	for (int i = 0; i < N; i++) {
		cin >> a;
		insert(a);
	}
	for (int i = 0; i < M; i++) {
		cin >> a;
		find(a);
	}
	printf("%.1f\n", 1.0 * cnt / M);
}

1146 Topological Order

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
#include<iostream>
#include<vector>
using namespace std;
int N, M;
vector<int>G[1010];
bool flag[1010];
int num[1010];
int main() {
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		G[b].push_back(a);
	}
	int n;
	cin >> n;
	vector<int>seque;
	for (int i = 0; i < n; i++) {
		fill(flag, flag + N, false);
		bool ans = true;
		for (int j = 0; j < N; j++) {
			cin >> num[j];
		}
		for (int j = 0; j < N; j++) {
			flag[num[j]] = true;
			for (int k = 0; k < G[num[j]].size(); k++) {
				if (!flag[G[num[j]][k]]) {
					ans = false;
					break;
				}
			}
			if (!ans) { break; }
		}
		if (!ans)seque.push_back(i);
	}
	for (int i = 0; i < seque.size(); i++) {
		cout << seque[i];
		if (i != seque.size() - 1) cout << " ";
		else cout << endl;
	}
}

1147 Heaps

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
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1010;
int M, N;
int tree[maxn];
bool maxh = true;
void maxHeap(int root) {
	if (!maxh) return;
	if (root > N) return;
	if (root * 2 <= N) {
		if (tree[root * 2] < tree[root])
			maxHeap(root * 2);
		else {
			maxh = false;
			return;
		}
	}
	if (root * 2 + 1 <= N) {
		if (tree[root * 2 + 1] < tree[root])
			maxHeap(root * 2 + 1);
		else {
			maxh = false;
			return;
		}
	}
}
bool minh = true;
void minHeap(int root) {
	if (!minh) return;
	if (root > N) return;
	if (root * 2 <= N) {
		if (tree[root * 2] > tree[root])
			minHeap(root * 2);
		else {
			minh = false;
			return;
		}
	}
	if (root * 2 + 1 <= N) {
		if (tree[root * 2 + 1] > tree[root])
			minHeap(root * 2 + 1);
		else {
			minh = false;
			return;
		}
	}
}
vector<int>postorder;
void post(int r) {
	if (r * 2 <= N) post(r * 2);
	if (r * 2 + 1 <= N) post(r * 2 + 1);
	postorder.push_back(tree[r]);
}
int main() {
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		maxh = true;
		minh = true;
		postorder.clear();
		for (int j = 1; j <= N; j++) {
			cin >> tree[j];
		}
		maxHeap(1);
		if (maxh) cout << "Max Heap\n";
		else {
			minHeap(1);
			if (minh) cout << "Min Heap\n";
			else cout << "Not Heap\n";
		}
		post(1);
		for (int i = 0; i < postorder.size(); i++) {
			cout << postorder[i];
			if (i != postorder.size() - 1) cout << " ";
			else cout << endl;
		}
	} 
}
 Comments