很trivial的构造题
首先上来判掉一些显然无解的情况,然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来
考虑在链上接一些点使得直径不会变长,对于链上的某个点,它最多能接上的链的长度就是它到两个端点距离的最小值
不妨设计递归函数求解,设solve(x,dis,lim)
表示在\(x\)点,最多能接长为\(dis\)的链,\(x\)这个点还能接上\(lim\)个点
最后看下把能加的位置都加完是否用完了\(n\)个点即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=400005;
int n,d,k,idx; vector <pi> ans;
inline void solve(int now,CI dis,CI lim)
{
if (dis==0) return; for (RI i=1;i<=lim;++i)
if (idx<n) ans.push_back(pi(now,++idx)),solve(idx,dis-1,k-1); else break;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; if (scanf("%d%d%d",&n,&d,&k),d>n-1) return puts("NO"),0;
if (k==1&&d>1) return puts("NO"),0;
for (i=1;i<=d;++i) ans.push_back(pi(i,i+1)); idx=d+1;
for (i=2;i<=d;++i) if (idx<n) solve(i,min(i-1,d+1-i),k-2);
if (idx<n) return puts("NO"),0; puts("YES");
for (auto [x,y]:ans) printf("%d %d\n",x,y);
return 0;
}
标签:typedef,Constructing,int,dis,Tree,long,CF1003E,include,define
From: https://www.cnblogs.com/cjjsb/p/17777257.html