题解：B4164 [BCSP-X 2024 12 月初中组] 末日塔后传

qhr2023 · 2025-03-13 22:28:45 · 题解

solution

一道构造。

先假设已经有了 n 个点的解，考虑推广到 n+2 个点。

因为 n 个点内部是合法的，令 n+1 和 n+2 到这 n 个点的距离及 n 个点到 n+1 和 n+2 距离都不超过 2 即可。

我们可以从 n+2 到 n 个点都连一条边，n 个点每个点都连一条到 n+1 的边，n+1 再连一条到 n+2 的边，这样就是一种合法的 n+2 的方案了。

如下图，黑点是 n 个点，红色是新加的 2 个点，我们先不管心 n 个点内部怎么连。

所以我们知道，只要 n 个点有解，那 n+2 个点也一定有解。

故只要找到有解的最小奇数和偶数即可，1 个点时显然成立，所以奇数都有解，而最小的偶数通过手算是 6。这样就可以构造所有 1+2k 和 6+2k 的解了，k 是非负整数。

实现方面，对于奇数，从 2 开始执行上述的连边即可；对于偶数，可以把前 6 个点的边连完，从 7 开始执行上述连边即可。下图是 n=6 的解。

code

#include <bits/stdc++.h>
using namespace std;
int n, a[505][505];
int main () {
    cin >> n;
    if (n==2||n==4) {
        puts("NO");
        return 0;
    }
    puts("YES");
    if (n%2==0) 
        a[1][2]=a[1][3]=a[1][4]=1,
        a[2][3]=a[2][5]=a[2][6]=1,
        a[3][4]=a[3][5]=a[3][6]=1,
        a[4][5]=a[4][2]=a[5][6]=a[5][1]=a[6][1]=a[6][4]=1;
    for (int i=(n%2?2:7); i<=n; a[i][i+1]=1, i+=2)
            for (int j=1; j<i; ++j)
                a[j][i]=a[i+1][j]=1;
    for (int i=1; i<=n; ++i, cout << '\n')
        for (int j=1; j<=n; ++j)
            cout << a[i][j] << ' ';
    return 0;
}