1116-1118

📅time:8.21 - 8.22

🍔题目：

1116 Come on! Let’s C 判断素数
1117 Eddington Number sort
1118 Birds in Forest 并查集
1119 Pre- and Post-order Traversals 二叉树，前序+后序是否能确定中序 不会，懒得想，只想睡觉

素数

千万别忘了调用函数

void check() {
	for (int i = 2; i < N; i++) {
		if (prime[i])
			for (int j = i + i; j < N; j += i)
				prime[j] = false;
	}
}

二叉树的序列转化

需要再去看一下前中后序的转换

附录

1116 Come on! Let’s C 20分

很简单的排序

#include<iostream>
#include<map>
using namespace std;
int N;
map<int, int>p;
bool prime[10010];
bool printed[10010];
void check() {
	for (int i = 2; i < N; i++) {
		if (prime[i])
			for (int j = i + i; j < N; j += i)
				prime[j] = false;
	}
}
int main() {
	cin >> N;
	fill(prime, prime + N, true);
	int id;
	for (int i = 1; i <= N; i++) {
		cin >> id;
		p[id] = i;
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> id;
		printf("%04d: ", id);
		if (p.find(id) == p.end()) {
			printf("Are you kidding?\n");
			continue;
		}
		if (printed[id]) {
			printf("Checked\n");
			continue;
		}
		printed[id] = true;
		if (p[id] == 1) {
			printf("Mystery Award\n");
		}
		else if (prime[p[id]]) {
			printf("Minion\n");
		}
		else {
			printf("Chocolate\n");
		}
	}
}

1117 Eddington Number 25分

sort()很简单的题目

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int num[100010];
int main() {
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> num[i];
	}
	sort(num, num + N);
	int pos = N / 2;
	int ans = 0;
	for (int i = 0; i < pos; i++) {
		ans += num[i];
	}
	int b = 0;
	for (int i = pos; i < N; i++) {
		b += num[i];
	}
	cout << N % 2 << " " << b - ans;
}

1118 Birds in Forest 20分

并查集

做了一百遍的并查集还是有问题，注意寻找一个结点的根节点不是Fa[x]，而是findfather(x)，即使进行了路径压缩，也可能导致树有三层高。

#include<iostream>
#include<set>
using namespace std;
const int maxn = 10010;
int N;
int Fa[maxn];
bool flag[maxn];
set<int>birds;
int findfather(int a) {
	int x = a;
	while (x != Fa[x]) {
		x = Fa[x];
	}
	//x是根结点
	while (Fa[a] != x) {
		int temp = Fa[a];
		Fa[a] = x;
		a = temp;
	}
	return x;
}
void Union(int a, int b) {
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb) {
		flag[fb] = false;
		Fa[fb] = fa;
	}
}
int main() {
	cin >> N;
	for (int i = 1; i < maxn; i++) {
		Fa[i] = i;
		flag[i] = true;
	}
	int n, first, other;
	for (int i = 0; i < N; i++) {
		cin >> n;
		cin >> first;
		birds.insert(first);
		for (int j = 1; j < n; j++) {
			cin >> other;
			birds.insert(other);
			Union(first, other);
		}
	}
	int tree = 0;
	for (auto it : birds) {
		if (flag[it]) tree++;
	}
	cout << tree << " " << birds.size() << endl;
	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		if (findfather(a) == findfather(b)) {//注意不是Fa[a]==Fa[b]
			cout << "Yes\n";
		}
		else cout << "No\n";
	}
}

1119 Pre- and Post-order Traversals 0分

直接抄答案

#include<iostream>
#include<vector>
using namespace std;
const int maxn = 31;
int N;
int pre[maxn];
int post[maxn];
vector<int>in;
bool unique = true;
void travel(int preL,int preR,int postL,int postR){
	if (preL == preR) {
		in.push_back(pre[preL]);
		return;
	}
	if (pre[preL] == post[postR]) {
		int i = preL + 1;
		while (i <= preR && pre[i] != post[postR - 1]) {
			i++;
		}
		//i:下一次的根节点
		if (i - preL > 1) {//左子树
			travel(preL + 1, i - 1, postL, postL + (i - preL - 1) - 1);
		}
		else unique = false;//i与上一个根节点preR之间的结点是左子树，若i-preL=1,则preR只有一颗子树，不知道到底是左子树还是右子树
		in.push_back(post[postR]);//根节点
		travel(i, preR, postL + (i - preL - 1), postR - 1);//右子树
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> pre[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> post[i];
	}
	travel(0, N - 1, 0, N - 1);
	printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
	for (int i = 1; i < in.size(); i++)
		printf(" %d", in[i]);
	printf("\n");
	return 0;
}