P9592 「Daily OI Round 1」Tree

题目描述

给定三个正整数参数 $n,d,k$，你需要构造出一棵根节点为 $1$ 的树，满足这棵树有 $n$ 个节点，每个节点到根节点的距离和为 $d$，除了叶节点以外每个节点的直接儿子数量至少 $k$ 个，且所有节点的最大深度最小。

注意事项：

• 距离：两个点之间的简单路径上的边的条数。
• 叶子节点：没有儿子的非根节点。
• 根节点深度为 $0$。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。
对于每组数据：共一行三个正整数 $n,d,k$，含义如题所示。

输出格式

对于每次询问，如果有解，第一行输出 YES，然后一行 $n-1$ 个正整数，第 $i$ 个正整数 $a_i$ 表示 $a_i$ 是 $i+1$ 的父亲节点，且 $a_i\le i$；如果无解，输出 NO。

如果有多组合法的答案，可以任意输出其中一组。

特别地，如果 $n=1$ 且有解，方案输出一行空行即可。

输入输出样例 #1

输入 #1

3
5 4 1
5 6 1
5 7 1

输出 #1

YES
1 1 1 1
YES
1 1 3 3
YES
1 2 2 2

输入输出样例 #2

输入 #2

3
5 4 2
5 6 2
5 7 2

输出 #2

YES
1 1 1 1
YES
1 1 3 3
NO

说明/提示

样例解释

对于第二组样例的第二组询问，$n=5,d=6,k=2$，即需要构造出含有 $5$ 个节点，各个节点到节点 $1$ 的距离和为 $6$ 且除叶节点外的节点至少有 $k$ 个儿子节点。

下面是样例构造的图：

其中编号为 $1,2,3,4,5$ 的点到根节点 $1$ 的距离分别为 $0,1,1,2,2$，和为 $6$，满足条件。而且非叶子节点 $1,3$ 都含有至少 $2$ 个儿子节点，可以证明这是所有合法构造中节点的最大深度最小的解法，在此处为 $2$。

数据范围

本题开启捆绑测试。

$\text{Subtask}$	分值	$n\le$	特殊性质
$0$	$5$	$10$	无
$1$	$5$	$20$	无
$2$	$5$	$10^5$	$k=n-1$
$3$	$5$	$10^5$	$k=n-1$ 或 $n-2$
$4$	$10$	$10^5$	$T=1$
$5$	$70$	$10^5$	无

对于全部数据，保证：$1\le n\le 10^5$，$1\le T\le 10^5$，$1\le k\le 10^5$，$\sum n\le 10^6$，$1\le d\le 10^{10}$。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define int long long
int n,m,i,j,ans,d,k,a[N],s,l[N],flg,dep,t,f;
signed main(){
	scanf("%lld",&t);
	while(t--){
		for(i=1;i<=n;i++) a[i]=l[i]=0;
		scanf("%lld%lld%lld",&n,&d,&k),f=2,l[1]=1,flg=0,dep=1;
		while(1){
			int nxt=f;
			if(d==0) break;
			for(i=1;i<=k;i++){
				if(f>n){flg=1;break;}
				a[f++]=l[dep];	
			}	
			d-=k*dep;
			if((n-f+1)*dep>=d) break;
			else l[++dep]=nxt;
		}
		if(flg==1 || d<n-f+1) printf("NO\n");
		else{
			printf("YES\n");
			for(i=f;i<=n;i++){
				while(1){
					if(d<dep || d-dep<n-i) dep--;
					else break;
				}
				a[i]=l[dep],d-=dep;
			}
			for(i=2;i<=n;i++) printf("%lld ",a[i]);
			printf("\n");
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容