GPLT团体程序设计天梯赛分类练习3：树

摘要

L2-2 小字辈 - 团体程序设计天梯赛练习3：树：BFS求树的最大深度

L2-4 秀恩爱分得快 - 团体程序设计天梯赛练习3：树：模拟

L2-3 完全二叉树的层序遍历 - 团体程序设计天梯赛练习3：树：完全二叉树

7-5 病毒溯源 - 团体程序设计天梯赛练习3：树：DFS最小序列

L2-2 小字辈

有N个人，现在给定1-N个人各自的父亲。根的辈分为1，依次向下递增。

按递增顺序输出辈分最小的成员的编号。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

struct node{
	int idx,dep;
};

int n,root,max_;
vector<int > e[maxn],ans;
queue<node> q;

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		int f;cin>>f;
		if(f != -1) e[f].push_back(i);
		else root = i;
	}
	q.push({root, 1});
	while(!q.empty()){
		int dep = q.front().dep;
		int idx = q.front().idx;
		q.pop();
		if(dep > max_){
			max_ = dep;
			ans.clear();
			ans.push_back(idx);
		}else if(dep == max_){
			ans.push_back(idx);
		}
		for(auto it : e[idx]){
			q.push({it, dep+1});
		}
	}
	cout<<max_<<"\n";
	if(!ans.empty()) cout<<ans[0];
	for(int i = 1 ; i < ans.size(); i ++){
		cout<<" "<<ans[i];
	}
	return 0;
}

L2-4 秀恩爱分得快

给定M张照片，每张照片上每对异性的亲密度为1/K。这里的K是照片上的人数。

给一对情侣，求这一对情侣是否是亲密度最高的。若不是，依次输出亲密度最高的异性。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;
const int maxm = 1050;

double val[maxn][maxn];
bool g[maxn];
int n,m;
vector<vector<int> > pic;
vector<int > af,bf;
string s1,s2;
int a,b;
double max_a_f, max_b_f, max_a_b;

int getInt(string s){
	if(s[0] == '-') s = s.substr(1,s.length()-1);
	int res = 0;
	for(int i = 0 ; i < s.length() ; i ++){
		res = res*10 + s[i] - '0';
	}
	return res;
}

void init(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
	cin>>n>>m;
	while(m--){
		int k;cin>>k;
		vector<int > v;
		for(int i = 1 ; i <= k ; i ++){
			string s; cin>>s;
			int idx = getInt(s);
			g[idx] = (s[0] != '-');
			v.push_back(idx);
		}
		pic.push_back(v);
	}
}

void solve(){
	cin>>s1>>s2;
	a = getInt(s1);
	b = getInt(s2);
	for(auto v : pic){
		bool ia = false;
		bool ib = false;
		for(auto it : v){
			if(it == a) ia = true;
			if(it == b) ib = true;
		}
		if(ia){
			for(auto it : v){
				val[a][it] += 1.0/v.size();
			}
		}
		if(ib){
			for(auto it : v){
				val[b][it] += 1.0/v.size();
			}
		}
	}
	for(int i = 0 ; i < n ; i ++){
		if(g[i] != g[a]){
			if(val[a][i] > max_a_f){
				max_a_f = val[a][i];
				af.clear();
				af.push_back(i);
			}else if(val[a][i] == max_a_f){
				af.push_back(i);
			}
		}
		if(g[i] != g[b]){
			if(val[b][i] > max_b_f){
				max_b_f = val[b][i];
				bf.clear();
				bf.push_back(i);
			}else if(val[b][i] == max_b_f){
				bf.push_back(i);
			}
		}
	}
}

void print(){
	sort(af.begin(),af.end());
	sort(bf.begin(),bf.end());
	if(val[a][b] == max_a_f && val[a][b] == max_b_f){
		cout<<s1<<" "<<s2;
		return;
	}
	for(auto it : af){
		cout<<s1<<" ";
		if(!g[it]) cout<<'-';
		cout<<it<<"\n";
	}
	for(auto it : bf){
		cout<<s2<<" ";
		if(!g[it]) cout<<'-';
		cout<<it<<"\n";
	}
}

int main(void){
	init();
	solve();
	print();
	return 0;
}

L2-3 完全二叉树的层序遍历

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

tip：若使用数组存储，完全二叉树将完全填充于1-N的数组空间中，顺序输出后恰是层序遍历。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;

int n;
int tree[maxn];

void create(int x){
	if(x > n) return;
	create(2*x);
	create(2*x + 1);
	cin>>tree[x];
}

int main(void){
	cin>>n;
	create(1);
	for(int i = 1 ; i <= n ; i ++){
		cout<<tree[i]<<(i != n ? " ": "\n");
	}
	return 0;
}

7-5 病毒溯源

我们将所有病毒从 0 到 N−1 进行编号。

随后 N 行，每行按以下格式描述一种病毒的变异情况：

k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数。

输出从源头开始最长变异链的长度。如果最长链不唯一，则输出最小序列。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;

int n,root,max_;
vector<int > e[maxn],v,ans;
bool ind[maxn];

void dfs(int x){
	if(v.size() > max_){
		max_ = v.size();
		ans = v;
	}
	for(auto it : e[x]){
		v.push_back(it);
		dfs(it);
		v.pop_back();
	}
}

int main(void){
	cin>>n;
	for(int i = 0 ; i < n ; i ++){
		int k; cin>>k;
		for(int j = 0 ; j < k ; j ++){
			int t; cin>>t;
			e[i].push_back(t);
			ind[t] = true;
		}
		sort(e[i].begin(), e[i].end());
	}
	for(int i = 0 ; i < n ; i ++){
		if(!ind[i]){
			root = i; break;
		}
	}
	dfs(root);
	cout<<max_+1<<"\n";
	cout<<root;
	for(int i = 0 ; i < ans.size() ; i ++){
		cout<<" "<<ans[i];
	}
}