自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:18:08，当前版本为作者最后更新于2025-06-18 21:40:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议升蓝啊，想了一整天，感觉比隔壁的 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]$ 的图。

$0$ 的显然直接扔掉，于是变成 $k$ 个点连出一张图使得度数集合大小为 $k-2$。

这是一个和原问题一模一样的子问题，用类似递归的思想做就行了。

还是很巧妙的呀！

另外注意本题小数据时的特判，详细见代码。

#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;
}