CF1773J-King‘s Puzzle【构造】

这篇具有很好参考价值的文章主要介绍了CF1773J-King‘s Puzzle【构造】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

正题

题目链接:https://codeforces.com/contest/1773/problem/K

题目大意

要求构造一张 $n$ 个点的无向图满足。

不存在重边和自环，且图连通
所有点的度数恰好有 $k$ 个不同的值

$1\leq k\leq n\leq 500$

解题思路

非常好构造，爱来自复建人

考虑构造 $k = n - 1$ 的情况，理论上如果这种情况可行，且存在度数为 $1$ 的点，那么我们可以考虑先构造 $n = k + 1$ 个点，把剩下的点连在度数最大的点上。

接下来考虑如何构造 $k = n - 1$ 且存在度数为 $1$ 的点。我们尝试手玩一下，因为要联通我们直接先拉一条链，此时的度数是 $1, 2, 2..., 2, 1$

然后我们保留一个度数为 $1$ 的点，然后让第二个点对其他所有点连边，那么此时链上的度数就为 $1, n - 1, 2, 3, ..., 3, 3, 2$

会发现后面有一段 $2, 3, 3, ..., 3, 3, 2$ 的点，也就是变成了一个 $n = n - 2$ 的子问题，重复上述过程就好了。

时间复杂度： $O(k^2+n)$ 文章来源地址https://www.toymoban.com/news/detail-497598.html

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define mp(x,y) make_pair(x,y)
using namespace std;
int n,k;
vector<pair<int,int> >e;
void solve(int n){
	if(n<=3)return;
	for(int i=1;i<n-2;i++)
		e.push_back(mp(i,n-1));
	solve(n-2);
}
int main()
{
	scanf("%d%d",&n,&k);
	if(n==1){puts("YES");puts("0");return 0;} 
	if(k==n){puts("NO");return 0;}
	if(k==1){
		puts("YES");
		for(int i=1;i<n;i++)e.push_back(mp(i,i+1));
		if(n!=2)e.push_back(mp(1,n));
		printf("%d\n",e.size());
		for(int i=0;i<e.size();i++)
			printf("%d %d\n",e[i].first,e[i].second);
		return 0;
	}
	puts("YES");k++;
	for(int i=1;i<k;i++)e.push_back(mp(i,i+1));
	solve(k);
	for(int i=k+1;i<=n;i++)e.push_back(mp(k-1,i));
	printf("%d\n",e.size());
	for(int i=0;i<e.size();i++)
		printf("%d %d\n",e[i].first,e[i].second);
	return 0;
}