数据结构day42

总结：DFS还没有掌握，前几天期中考，耽搁了好久，这个day42写了3天可以说；
题目详情 - 1102 Invert a Binary Tree (pintia.cn)

思路：用数组储存，-用-1表示；输入时就更换左右孩子即可，然后用hash标记出现的数字，如果没出现就是root，最后遍历即可；

#include<iostream>
#include<cctype>
#include<queue>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
 
struct node {
	int left;//- equals to -1
	int right;
}arr[10];
void level_traverse(int root) {
	queue<int>q;
	if (root != -1) {
		q.push(root);
	}
	int flag = 1;
	while (!q.empty()) {
		if (flag) {
			cout << root;
			flag = 0;
		}
		else
		{
			cout << ' ' << root;
		}
		if (arr[root].left != -1) {
			q.push(arr[root].left);
		}
		if (arr[root].right != -1) {
			q.push(arr[root].right);
		}
		q.pop();
		root = q.front();
	}
}
int f = 1;
void in_traverse(int root) {
	if (root == -1) {
		return;
	}
	in_traverse(arr[root].left);
	if (f) {
		f = 0;
		cout << root;
	}
	else
	{
		cout << ' ' << root;
	}
	in_traverse(arr[root].right);
}
int main() {
	int n;
	cin >> n;
	int hash[10] = { 0 };
	char c1, c2;
	for (int i = 0; i < n; i++) {
		cin >> c1 >> c2;
		arr[i].right = isdigit(c1) ? c1 - '0' : -1;
		arr[i].left = isdigit(c2) ? c2 - '0' : -1;
		if (arr[i].left != -1) {
			hash[arr[i].left] = 1;
		}
		if (arr[i].right != -1) {
			hash[arr[i].right] = 1;
		}
	}
	int root = 0;
	for (int i = 0; i < n; i++) {
		if (hash[i] == 0) {
			root = i;
			break;
		}
	}
	level_traverse(root);
	cout << '\n';
	in_traverse(root);
	return 0;
}

题目详情 - 1053 Path of Equal Weight (pintia.cn)

思路：测试点6尚未通过；原因是sort只保证了儿子节点，未保证孙子节点从大到小；需要多写两次掌握DFS；

#include<iostream>
#include<cctype>
#include<stack>
#include<vector>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
 
struct node {
	int data;
	vector<int>son;
}arr[100];
int n, m, s;
int path[100];
 
bool cmp(int a, int b) {
	return arr[a].data > arr[b].data;
}
void dfs(int index,int num_node,int sum) {
	if (sum > s) {
		return;
	}
	if (sum == s) {
		if (arr[index].son.size() != 0) {
			return;
		}
		for (int i = 0; i < num_node; i++) {
			cout << arr[path[i]].data;
			if (i < num_node - 1) {
				cout << ' ';
			}
			else
			{
				cout << '\n';
			}
		}
		return;
	}
	for (int i = 0; i < arr[index].son.size(); i++) {
		int child = arr[index].son[i];
		path[num_node] = child;
		dfs(child, num_node + 1, sum + arr[child].data);
	}
}
int main() {
	cin >> n >> m >> s;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].data;
	}
	int id, num, son_id;
	for (int i = 0; i < m; i++) {
		cin >> id >> num;
		for (int j = 0; j < num; j++) {
			cin >> son_id;
			arr[id].son.push_back(son_id);
		}
		sort(arr[id].son.begin(), arr[id].son.end(), cmp);//输出时从大到小
	}
	dfs(0, 1, arr[0].data);
	return 0;
}

题目详情 - 1079 Total Sales of Supply Chain (pintia.cn)

思路：使用了BFS，先建树，然后用累加叶子节点层数对应的钱*个数得到答案；

#include<iostream>
#include<cctype>
#include<queue>
#include<vector>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
 
struct node {
	int data;
	int layer;
	vector<int>son;
}arr[100000];
int n;
double p, r, res;//default: 0
double rate[100000];
void layer() {
	queue<int>q;
	q.push(0);
	while (!q.empty()) {
		int root = q.front();
		q.pop();
		for (int i = 0; i < arr[root].son.size(); i++) {
			q.push(arr[root].son[i]);
			arr[arr[root].son[i]].layer = arr[root].layer + 1;
		}
	}
}
void bfs() {
	queue<int>q;
	q.push(0);
	while (!q.empty()) {
		int root = q.front();
		q.pop();
		if (!arr[root].son.size()) {
			res += rate[arr[root].layer] * arr[root].data;
		}
		else
		{
			for (int i = 0; i < arr[root].son.size(); i++) {
				q.push(arr[root].son[i]);
			}
		}
	}
 
}
int main() {
	cin >> n >> p >> r;
	rate[0] = p;
	for (int i = 1; i < n; i++) {//打表
		rate[i] =rate[i-1]*(1 + r / 100);
	}
 
	int num, id;
	arr[0].layer = 0;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num == 0) {
			cin >> arr[i].data;
		}
		else
		{
			for (int j = 0; j < num; j++) {
				cin >> id;
				arr[i].son.push_back(id);
			}
		}
	}
	layer();
	bfs();
	printf("%.1f", res);
	return 0;
}

题目详情 - 1090 Highest Price in Supply Chain (pintia.cn)

思路：和上题几乎一样，这次选择熟悉DFS；

#include<iostream>
#include<cmath>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
 
 
int n, num, max_depth;
double p, r;
vector<int>v[100000];
void dfs(int index, int depth) {
	if (v[index].size() == 0) {
		if (depth > max_depth) {
			max_depth = depth;
			num = 1;
		}
		else if (depth == max_depth) {
			num++;
		}
	}
	for (int i = 0; i < v[index].size(); i++) {
		dfs(v[index][i], depth + 1);
	}
}
int main() {
	cin >> n >> p >> r;
	r /= 100;//r/100
	int father, root;
	for (int i = 0; i < n; i++) {
		cin >> father;
		if (father == -1) {
			root = i;
		}
		else
		{
			v[father].push_back(i);//储存儿子的下标
		}
	}
	dfs(root, 0);
	printf("%.2f %d", p * pow(1 + r, max_depth), num);
	return 0;
}

题目详情 - 1094 The Largest Generation (pintia.cn)

思路：和上题一样，用DFS，甚至根节点已经给定为1； 

#include<iostream>
#include<cmath>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
 
vector<int>v[100];
int max_num[100];
int n, m;
//dfs记录个数和层数
void dfs(int index, int layer) {
	max_num[layer]++;
	for (int i = 0; i < v[index].size(); i++) {
		dfs(v[index][i], layer + 1);
	}
}
int main() {
	cin >> n >> m;
	int num, id, child;
	for (int i = 0; i < m; i++) {
		cin >> id >> num;
		for (int j = 0; j < num; j++) {
			cin >> child;
			v[id].push_back(child);
		}
	}
	dfs(1, 1);
	int max_ctn = 0, layer = 1;
	for (int i = 1; i < 100; i++) {
		if (max_num[i] > max_ctn) {
			max_ctn = max_num[i];
			layer = i;
		}
	}
	cout << max_ctn << ' ' << layer;
	return 0;
}

复习题： 

题目详情 - 1075 PAT Judge (pintia.cn) 

思路：对sort的熟悉，用时1小时，模拟题的速度快了不少；第一次写完测试点2和4出错，测试点2是要区分-1和0；测试点4我错误的原因是对满分个数情况，比如多次同一题满分不能叠加个数；

这里有比较详细的对测试点4的分析：

(25条消息) PAT 甲级 1075 PAT Judge 最后一个测试点未通过（C语言版本）_Xaiver_97的博客-CSDN博客

这次写的代码比上一次逻辑好了不是一点点了；

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
 
struct node {
	int score[6];//0储存总分
	bool ctn[6];//0是-,1正常打印分数; ctn[0]代表是否提交过不为-1的答案,测试点2：区分-1和0
	int flag;//判断是否没有提交，或者全-1
	int full;//满分个数
	int id;
}arr[10001];
int max_score[6];//下标从1开始
 
bool cmp(node s1, node s2) {
	if (s1.score[0] != s2.score[0]) {
		return s1.score[0] > s2.score[0];
	}
	else if (s1.full != s2.full) {
		return s1.full > s2.full;
	}
	else if(s1.flag!=s2.flag) {
		return s1.flag > s2.flag;
	}
	else
	{
		return s1.id < s2.id;
	}
}
int main() {
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 1; i <= k; i++) {
		cin >> max_score[i];
	}
	int ur_id, problem_id, score;
	for (int i = 0; i < m; i++) {//10^5
		cin >> ur_id >> problem_id >> score;
		arr[ur_id].id = ur_id;
		arr[ur_id].ctn[problem_id] = 1;
		if (score != -1) {
			arr[ur_id].ctn[0] = 1;
		}
		//提交多次满分答案，只能full++一次;
		if (score == max_score[problem_id]&&max_score[problem_id]!=arr[ur_id].score[problem_id]) {
			arr[ur_id].full++;
		}
		if (score > arr[ur_id].score[problem_id]) {//default: 0 so not to attn to -1
			arr[ur_id].score[0] += (score - arr[ur_id].score[problem_id]);//total score
			arr[ur_id].score[problem_id] = score;
		}
		if (arr[ur_id].ctn[0] != 0) {
			arr[ur_id].flag = 1;//提交过至少一次,且总分不为0
		}
	}
	sort(arr, arr + 10001, cmp);
	int rank = 1;
	for (int i = 0; i < n; i++) {
		if (arr[i].flag == 0)
		{
			break;
		}
		if (i > 0 && arr[i].score[0] < arr[i - 1].score[0]) {
			rank = i + 1;
		}
		printf("%d %05d %d", rank, arr[i].id, arr[i].score[0]);
		for (int j = 1; j <= k; j++) {
			if (arr[i].ctn[j] != 0) {
				printf(" %d", arr[i].score[j]);
			}
			else
			{
				printf(" -");
			}
		}
		printf("\n");
	}
	return 0;
}