Dyd's Blog

He who has a strong enough why can bear almost any how.

LOJ540游戏

Posted on In
Symbols count in article: 1.9k Reading time ≈ 2 mins.

乱搞构造题

游戏

思路

没啥思路，完全不会三元环，只是随便搞了一下完全图，发现 $n$ 个点的完全图有 $\binom{n}{3}$ 个三元环，再加上有显然的用 $x + 2$ 个点构造 $x$ 个三元环的方法，感觉可得部分分

然后瞪了一眼数据，发现有个特殊数据是立方数，我愣是啥也没想到，幸好有个大样例，一看才发现，三圆环对立方数，也就是说，如果有 $3x$ 个点，我先放 $x$ 个点不连边，再放 $x$ 个点每个点都和最初的 $x$ 个点连边，再放 $x$ 个点每个点都和前面放的 $2x$ 个点连边，那么在找三元环的时候，必须是在这三份每份 $x$ 个点中各选一个，即共 $x^3$ 个点

到这里，我看差不多了，就开始乱搞，对于要求 $n$ 个环，在完全图和立方数两种构造中找到离他最近的，构造出来然后递归构造剩下的，如果剩下的环 $+2$ 小于剩下的点数就用朴素构造法

然后……就过了

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
const int N = 500;
int cnt = 0;
struct Way{ int val, num, typ; };
std::vector<Way> way;
bool e[N + 100][N + 100];
void lk(int x, int y){ e[x][y] = e[y][x] = true; }
void mk_bf(int x)
{
    lk(cnt + 1, cnt + 2);
    lk(cnt + 2, cnt + 3);
    lk(cnt + 3, cnt + 1);
    cnt += 3, --x;
    while (x--)
    {
        ++cnt;
        lk(cnt, cnt - 1), lk(cnt, cnt - 2);
    }
}
void mk_q3(int x)
{
    int y = x / 3;
    for (int i = 1; i <= y; ++i)
        for (int j = 1; j <= y; ++j) lk(cnt + j, cnt + i + y);
    for (int i = y + y + 1; i <= x; ++i)
        for (int j = y + y; j; --j) lk(cnt + j, cnt + i);
    cnt += x;
}
void mk_all(int x)
{
    for (int i = 1; i <= x; ++i)
        for (int j = 1; j < i; ++j) lk(cnt + i, cnt + j);
    cnt += x;
}
Way find(int x)
{
    int l = 0, r = way.size() - 1, mid, res = -1;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (way[mid].val <= x) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return way[res];
}
void calc(int x)
{
    if (!x) return ;
    if (x + 2 < N - cnt) return mk_bf(x);
    Way t = find(x);
    if (t.typ == 1) mk_q3(t.num);
    else mk_all(t.num);
    calc(x - t.val);
}
int main()
{
    for (int i = 2; i * 3 <= N; ++i) way.pb({i * i * i, i * 3, 1});
    for (int i = 4; i <= N; ++i) way.pb({i * (i - 1) * (i - 2) / 6, i, 2});
    std::sort(way.begin(), way.end(), [&](Way x, Way y){ return x.val == y.val ? x.num > y.num : x.val < y.val; });
    int n;
    scanf("%d", &n);
    calc(n);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i)
    {
        for (int j = i + 1; j <= cnt; ++j) printf("%d ", e[i][j]);
        puts("");
    }
    return 0;
}