Tenka1 Programmer Contest 2018 D – Crossing 题解【构造】【模拟】

点击量：187

    一道比较基础的构造题，需要正确的思路方向。

目录

Problem Statement

You are given an integer \(N\). Determine if there exists a tuple of subsets of \(\{1,2,\dots ,N\}, (S_1,S_2,…,S_k)\), that satisfies the following conditions:

Each of the integers \(1,2,…,N\) is contained in exactly two of the sets \(S_1,S_2,\dots ,S_k\).

Any two of the sets \(S_1,S_2,\dots ,S_k\) have exactly one element in common.

If such a tuple exists, construct one such tuple.

Constraints

\(1\le N\le 10^5\)

\(N\) is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If a tuple of subsets of \(\{1,2,\dots ,N\}\) that satisfies the conditions does not exist, print No. If such a tuple exists, print Yes first, then print such subsets in the following format:

k
|S1| S1,1S1,2 … S1,|S1|
:
|Sk| Sk,1Sk,2 … Sk,|Sk|

where \(S_i=S_{i,1},S_{i,2},\dots ,S_{i,|S_i|}.

If there are multiple such tuples, any of them will be accepted.

Sample Input 1

3

Sample Output 1

Yes
3
2 1 2
2 3 1
2 2 3

It can be seen that \((S_1,S_2,S_3)=(\{1,2\},\{3,1\},\{2,3\})\) satisfies the conditions.

Sample Input 2

4

Sample Output 2

No

题意：

    有\(1\sim N\) \(N\) 个数字，每个数字出现两次，现在要求把这些数字分成若干集合，使得任意两个集合之间有且仅有一个相同的元素。问是否存在这样的划分方案，如果不存在，输出No，如果存在，输出Yes并按输出格式构造出任意一种答案。

题解：

    一开始以为只有\(1\)和\(3\)合法，于是其他输出No，然后貌似只过了No的点和\(1,3\)的特判。。。接着就没时间写了。后来发现不止\(1\)跟\(3\)合法，诸如\(6,10,15\)等数也合法。

    我们如果把集合看成一个点，存在相同元素这一关系看作一条边，那么\(k\)个集合就会构成\(\frac{k(k-1)}2\)条边，又因为每个数字出现两次，所以每个数字会贡献一条边，所以情况有解当且仅当\(\frac{k(k-1)}2=n\)存在正整数解。

    接下来是构造。首先第一个集合没有约束，但是由于上面所说共有\(n\)条边，那么对于关于\(k\)的方程\(\frac{k(k-1)}2=n\)的正整数解\(k\)就是集合数，即图中的点数。那么点的度数是\(k-1\)，每个集合中的元素个数就是\(l=k-1\)(每个点出现两次所以\(2\)被约掉了)。

    第二个集合仅和第一个集合有一个相同的元素，那么令这个元素为第一个，我们还剩下\(l-1\)个位置，为了不和上面再次重复，都必须要放新元素；第三个集合的前两个元素需要分别和第一、二个相同，但是由于第二个集合中已经用完了第一个元素，所以第三个集合的前两个位置就要匹配第一、二个集合的第二个元素了，此时第三个集合剩下\(l-2\)个位置，继续填新元素。

    依此类推，在第\(k-1\)行的时候所有元素就至少出现了一次(\(\frac {k(k-1)}2=n\)，第\(i\)行出现\(n-i+1\)个新元素)，可以发现每个元素第一次出现的位置形成了一个上三角。最后一行不出现新元素，与上面每一行唯一只出现一次（还没有被匹配）的数相照应。画个图应该更好理解。

    第\(i\)行前\(i-1\)个数总是匹配着前\(i-1\)行每一行的第\(i-1\)列。由于每一行需要额外拿出\(i-1\)个来匹配别人，所以每行产生\(k-1-(i-1)=k-i\)个新元素，这样一来，把相同颜色的匹配上，就是一种构造方案了。

    时间复杂度\(O(n)\)。

Code：

#include<cstdio>
int vali[100100];
int a[1000][1000];
int main()
{
    for(int i=1;i*(i-1)/2<=100000;++i)//先把合法的情况列出来
        vali[i*(i-1)/2]=i;
    int n;
    scanf("%d",&n);
    if(!vali[n])
    {
        puts("No");
        return 0;
    }
    puts("Yes");
    printf("%d\n",vali[n]);
    int t=1,l=2*n/vali[n];
    for(int i=1;i<=vali[n];++i)
    {
        printf("%d ",l);
        for(int j=1;j<i;++j)
        {
            printf("%d ",a[j][i-1]);
            a[i][j]=a[j][i-1];
        }
        for(int j=i;j<=l;++j)
        {
            printf("%d ",t);
            a[i][j]=t++;
        }
        puts("");
    }
    return 0;
}