Tenka1 Programmer Contest D

链接 Tenka1 Programmer Contest D - Crossing

给定\(n\)，要求构造\(k\)个集合\({S_k}\)，使得\(1\)到\(n\)中每个元素均在集合中出现两次，且每两个元素的交集有且仅有一个数。\(n\leq 10^5\)
小清新构造，考虑且每两个元素的交集有且仅有一个数意味着什么，我们把每个集合看作一个点，交集大小看作一条边，那么每两点之间就有且仅有一条边。
也就是\(k\)个集合构成了一个完全图。
那么\(n\)个数就构成了\(n\)条边，那么\(k\)满足\(k*(k-1)=2*n\)，如果找不到合法的\(k\)就是非法的。
最后枚举两点之间的每一条边，把对应的数分别填到两个集合里面去即可。
EF两题不会，告辞。

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int mod=1000000007;

const int N=100001;

int n,w[N],res[N],vis[N];

int le,ri,z,y,tot;ll ans;

vector<int>G[N];

int gi(){

    R x=0,k=1;char c=getchar();

    while(c!='-'&&(c<'0'||c>'9'))c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

void work(R k){

	puts("Yes"),printf("%d\n",k);

	for(R i=1;i<=k;++i)

		for(R j=i+1;j<=k;++j)

			tot++,G[i].push_back(tot),G[j].push_back(tot);

	for(R i=1;i<=k;++i){

		printf("%d ",k-1);

		for(R j=0;j<k-1;++j)

			printf("%d ",G[i][j]);

		puts("");

	}

	exit(0);

}

int main(){

	cin>>n;

	if(n==1){

		puts("Yes");

		puts("2");

		cout<<1<<' '<<1<<endl;

		cout<<1<<' '<<1<<endl;

		return 0;

	}

	for(R k=1;k<=n;++k)

		if(k*(k-1)/2==n)

			work(k);

	puts("No");

    return 0;

}

巴特西

Tenka1 Programmer Contest D - Crossing

链接 Tenka1 Programmer Contest D - Crossing

最新文章

热门文章