CF1003E Tree Constructing 构造+树论
正解:构造
解题报告:
这题麻油翻译鸭,,,那就先大概港下题意趴QAQ
构造一棵n个点,直径为d,每个点点度不超过k的树
这题其实我jio得还是比较简单的趴,,,
首先构造出一条直径,就是一条链,不说
然后思考,多的点要加哪儿呢,就是加在分支上嘛
那就是,能加就加,然后唯一的限制是保证分支加了之后不能长于直径
没了
做完辣
还是比较简单的嘛所以说
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define il inline
#define rg register
#define mp make_pair
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
ll n,d,k,hd;
vector< pair<ll,ll> >as;
il ll read()
{
rg char ch=getchar();rg ll x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
if(ch=='-')ch=getchar(),y=0;
while(ch<='9' && ch>='0')x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
return y?x:-x;
}
void dfs(ll nw,ll dep,ll mxdp)
{
if(dep==mxdp)return;
for(rg ll i=0;i<k-1-(dep==0) && hd<n;++i)as.push_back(mp(nw,++hd)),dfs(hd,dep+1,mxdp);
}
int main()
{
n=read();d=read();k=read();hd=d+1;
if(n<=d || (d>1 && k<2))return printf("NO\n"),0;
rp(i,1,d)as.push_back(mp(i,i+1));
rp(i,2,d)dfs(i,0,min(i-1,d-i+1));
if(hd<n)return printf("NO\n"),0;
printf("YES\n");rp(i,0,n-2)printf("%d %d\n",as[i].first,as[i].second);
return 0;
}