LOJ540 - 「LibreOJ NOIP Round #1」游戏

2017/11/06

题面

给一个正整数 n ,请你构造一个无向简单图使得其三元环个数为 n

做法

考虑一个有 N 个顶点的完全图,随便选一条边,再随便选一个不属于边的端点的点, 一定构成一个三元环。

也就是说点数为 N 的无向完全图上的三元环数量有 个。

考虑贪心多个互不联通的无向完全图使得他们的三元环计数之和等于给定值即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;

int G[501][501]; int gpos;

inline
int calc(int x) {
    return x * (x-1) * (x-2) / 6;
}

int main() {
    int N, K; scanf("%d", &N);
    for(K=1;calc(K)<=N;K++);

    for(K-=1;K>=3;K--) {
        while(calc(K) <= N) {
            N -= calc(K);
            for(int j=1;j<=K;j++)
                for(int k=j+1;k<=K;k++)
                    G[gpos+j][gpos+k] = 1;
            gpos += K;
        }
    }

    assert(N == 0);

    printf("%d\n", gpos);
    for(int i=1;i<=gpos;i++) {
        for(int j=i+1;j<=gpos;j++)
            printf("%d ", G[i][j]);
        puts("");
    }
}