atcodertenka12018D结论构造

题目大意&＃xff1a;给定n和n个元素1到n&＃xff0c;要求构造若干集合&＃xff0c;使得每个元素出现在恰好两个集合中&＃xff0c;并且任意两个集合交集大小恰好是1.
题解&＃xff1a;假定有k个集合&＃xff0c;那么就会有k(k-1)/2个交集。显然这k(k-1)/2个交集两两不同&＃xff0c;并且由于任意一个元素都出现了恰好两次&＃xff0c;因此至少两个集合的交集似乎它。因此k(k-1)/2&＃61;n。反过来的构造也是很显然的&＃xff0c;对每个元素钦定两两不同的一对无序集合即可。

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