专栏文章

题解：CF639B Bear and Forgotten Tree 3

RRex01
CF639B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipovzks
此快照首次捕获于
2025/12/03 15:32
3 个月前
此快照最后确认于
2025/12/03 15:32
3 个月前
查看原文

CF639B 题目传送门

题目大意

请你构造一棵包含 nn 个节点，其中节点编号从 11 到 nn，并以 11 号节点为根节点，直径为 dd，高度 hh 的树。其中树的直径为树上两节点之间的最大距离，树的高度指的是根节点到其它节点的最大距离。若满足，则按任意顺序输出每一条边，否则输出 −1-1。

解决方法

首先考虑特殊情况：
  • 特判一：当 n=2n=2 时，只有 h=1h=1 且 d=1d=1 可以。
  • 特判二：当 2×h<d2 \times h < d 时，因为无解，所以输出 −1−1。
其他情况正常考虑：构造一棵 nn 个点，深度 hh，最长链长度为 dd 的树。先从根构造两条长度分别为 d−hd-h 和 hh 的链，然后剩下的点如果 d≠hd\not=h 就挂在根上，输出 11 即可，如果 d=hd=h 就随便挂在除根和叶子以外的位置上，输出 22 即可。

代码展示

CPP
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, d, h;//建议scanf,更快
	scanf("%d%d%d", &n, &d, &h);
	if(d > (2 * h) || (d == h && h == 1 && n > 2))
	//1.通过样例可知d必须<=2h若不满足就输出-1
	//2.当d=h=1且n>2时，也输出-1
	{
		printf("-1\n");//建议printf,更快
		return 0;
	}
	for(int i = 2; i <= h + 1; i++)
		printf("%d %d\n", i-1, i);
	for(int i = h + 2; i <= d + 1; i++)
  //分类讨论
		if(i == h + 2) printf("1 %d\n", i);
		else printf("%d %d\n", i-1, i);
	for(int i = d + 2; i <= n; i++)
		if(d != h) printf("1 %d\n", i);
		else printf("2 %d\n", i);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...