作者:浅笑那段情2502918773 | 来源:互联网 | 2023-10-10 08:33
题目大意:给定n和n个元素1到n,要求构造若干集合,使得每个元素出现在恰好两个集合中,并且任意两个集合交集大小恰好是1.
题解:假定有k个集合,那么就会有k(k-1)/2个交集。显然这k(k-1)/2个交集两两不同,并且由于任意一个元素都出现了恰好两次,因此至少两个集合的交集似乎它。因此k(k-1)/2=n。反过来的构造也是很显然的,对每个元素钦定两两不同的一对无序集合即可。
#include
#define gc getchar()
#define rep(i,a,b) for(int i&#61;a;i<&#61;b;i&#43;&#43;)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"&#61;"<
#define sp <<" "
#define ln <
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{int x,ch;while((ch&#61;gc)<&#39;0&#39;||ch>&#39;9&#39;);x&#61;ch^&#39;0&#39;;while((ch&#61;gc)>&#61;&#39;0&#39;&&ch<&#61;&#39;9&#39;)x&#61;(x<<1)&#43;(x<<3)&#43;(ch^&#39;0&#39;);return x;
}
const int N&#61;100010;vector<int> v[N];
int main()
{int n&#61;inn(),k&#61;0,cnt&#61;0;if(n&#61;&#61;1) return !printf("Yes\n2\n1 1\n1 1\n");rep(i,1,n) if((lint)i*(i-1)/2&#61;&#61;n) { k&#61;i;break; }if(!k) return !printf("No\n");rep(i,1,k) rep(j,i&#43;1,k) cnt&#43;&#43;,v[i].pb(cnt),v[j].pb(cnt);printf("Yes\n%d\n",k);rep(i,1,k){printf("%d ",(int)v[i].size());Rep(j,v[i]) printf("%d ",v[i][j]);printf("\n");}return 0;
}