Atcoder(Crossing)

链接：https://tenka1-2018.contest.atcoder.jp/tasks/tenka1_2018_d
思路：构造题，首先我们要考虑清楚一个问题，任意两个集合公有元素只有一个，那么可以看为从k个集合中选2个集合得到一个共有元素，那么一共有k（k-1）/2种选择方法，而由于每个元素刚好属于两个集合，所以每种选法得到的元素应该恰好都不同，所以n = k（k-1）/2，满足时有解否则无解。构造方法如下：（k=6）可正好保证要求

image.png
按照如下构造方式即可得到最终答案。
代码：

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a[1010];

int main(){
    scanf("%d",&n);
    int t = sqrt(2*n+0.5);
    if(t*(t+1)==2*n){
        printf("Yes\n%d\n",t+1);
        int cnt = 1;
        for(int i=1;i<=t;i++){
            for(int j=1;j<=i;j++){
                a[i].push_back(cnt);
                if(j==i)a[t+1].push_back(cnt);
                else
                a[j].push_back(cnt);
                cnt++;
            }
        }
        for(int i=1;i<=t+1;i++){
            printf("%d",t);
            for(int j=0;j<a[i].size();j++){
                printf(" %d",a[i][j]);
            }
            printf("\n");
        }
    }
    else printf("No\n");
}