共42道题,当前是第23

初赛真题

题目给出 $m$ 颗非空有根(根节点编号为 )区分左右儿子的二叉树。
将某一棵给出二叉树的叶子节点换成任意一棵非空二叉树称为一次变换,即给出的二叉树变
换到新二叉树。
同一棵二叉树进行多次变换是指在每次变换后得到的新二叉树上继续进行变换。
若 任意一棵大小超过 $1$ 的二叉树都可以由给出的这 $m$ 棵二叉树中的至少一棵通过 有限次变换得到,则输出 `Almost Complete` ,否则输出 `No` 。
题目第一行首先读入一个数 $m$ ,表示二叉树的棵数。
接下来进行 $m$ 次这样的操作。

读入一个数 $n$ ,接下来 $n$ 行每行 $2$ 个数 $l_i$ 和 $r_i$ 分别表示这棵二叉树第 $i$ 个点的左右儿子编号,若没有左儿子,则 $l_i=0$ ,若没有右儿子,则 $r_i=0$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, m, tot;
vector < int > t;
int lc[N], rc[N];
inline bool isleaf(int u) {
	return ___(1)___;
}
inline bool solve(vector<int> t) {
	if (t.empty()) return false;
	for (auto o: t)
		if (isleaf(o)) return true;
	vector < int > t1, t2, t3, t4;
	for (auto o: t) {
		if (!lc[o]) t2.push_back(rc[o]);
		if (!rc[o]) t1.push_back(lc[o]);
		if (___(2)___) {
			if (isleaf(lc[o])) t3.push_back(rc[o]);
			if (isleaf(rc[o])) t4.push_back(lc[o]);
		}
	}
	___(3)___;
}
int main() {
	scanf("%d", & m);
	for (int i = 1; i <= m; ++i) {
		int n;
		scanf("%d", &n);
		___(4)___;
		for (int j = 1; j <= n; ++j) {
			scanf("%d", &lc[tot + j]);
			if (lc[tot + j]) lc[tot + j] += tot;
			scanf("%d", &rc[tot + j]);
			if (rc[tot + j]) rc[tot + j] += tot;
		}
		___(5)___;
	}
	if (solve(t)) printf("Almost Complete\n");
	else printf("No\n");
	return 0;
}


1. D。
2. D。
3. C。
4. B。
5. B。

首先建立 $m$ 棵树的森林,通过递归判断是否存在任意一棵大小超过 $1$ 的二叉树都可以由给出的某一棵给出的二叉树通过有限次变换得到。

Question

1. (1) 处应填( )。

2. (2) 处应填( )。

3. (3) 处应填( )。

4. (4) 处应填( )。

5. (5) 处应填( )。

陈伦制作 版权所无 粤ICP备16127491号-1