题解：P12800 [NERC 2022] King' s Puzzle
fish_love_cat
·
·
题解
建议升蓝啊，想了一整天，感觉比隔壁的 Ad-hoc 构造难多了 /fad
说不上来怎么想到的，类似于灵光乍现写写画画突然得到的构造。Ad-hoc 让我怎么告诉你思维过程。
显然度数最大不超过 n-1，所以若有解必有 k<n。
想不到其他无解情况了，于是着手对于 n=k+1 的极限情况进行构造。
假设能构造出来吧，那么 n-(k+1) 的这么多点可以用链的形式挂在后面保证连通。
这样题目转变为了 n=k+1 时的情况。
此时合法度数集内的数显然就是 [1,k]。
不知道怎么回事想到连一个菊花，然后把这个点扔掉。
此时我们少了度为 k 的点的需求，并且剩余点的度数需求均有减一。
此时剩下的构造等价于用 k 个点连出一个度数集为 [0,k-2] 的图。
这是一个和原问题一模一样的子问题，用类似递归的思想做就行了。
还是很巧妙的呀！
另外注意本题小数据时的特判，详细见代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
pair<int,int>ve[300005];
int top;
int main(){
int n,k;
cin>>n>>k;
if(n==1&&k==1){
puts("YES\n0");
return 0;
}
if(n==2&&k==1){
puts("YES\n1\n1 2");
return 0;
}
if(n<=k){
puts("NO");
return 0;
}
if(k<=2){
puts("YES");
cout<<n-(k==2)<<'\n';
for(int i=1;i<n;i++)cout<<i<<' '<<i+1<<'\n';
if(k==1)cout<<1<<' '<<n<<'\n';
return 0;
}
for(int i=k+1,j=1;i>=j;i--,j++)
for(int k=j;k<i;k++)ve[++top]=make_pair(i,k);
for(int i=k+2;i<=n;i++)
ve[++top]=make_pair(i-1,i);
puts("YES");
cout<<top<<'\n';
for(int i=1;i<=top;i++)
cout<<(ve[i].first)<<' '<<(ve[i].second)<<'\n';
return 0;
}
```