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

· · 题解

题目传送门

题目大意

有 n 座塔，第 i 座塔产生的第 j 种能量必须送到第 j 座塔，路上最多经过 2 条管道。要输出一个 n\times n 的 01 矩阵 d，满足 d_{i,i}=0 且 \forall i\ne j,\ d_{i,j}\ \text{xor}\ d_{j,i}=1（恰好是一个竞赛图），使任意 i 到任意 j 都有长度不超过 2 的路径。无解输出 NO。

思路

这题只给一个 n，答案本身就是一张图，先把能想到的路子都过一遍：

首先，因为我是蒟蒻，所以第一时间想到了暴力：枚举所有竞赛图找直径 2 的，但是当n=6 就有 2^{15} 种，n 再大直接爆炸，直接 TLE。作为蒟蒻，我们肯定是不想错题的，所以否决。

于是我又考虑到随机化：随机定向的竞赛图在 n 较大时大概率直径就是 2 ，交上去也许能过，但 n=6 都有不小的翻车概率，不保险，所以作为蒟蒻，我们肯定也是不想用这种很大概率错题的方式的。

于是最终因为我想到了一个绝妙的方法（我看到了题目标签），就是构造：手推一个通用方案，n\le 500 居然看起来可以过，所以就是它了。

所以用构造。不妨把塔看成点、管道看成有向边，题目就是要构造一个直径不超过 2 的竞赛图。 先写一些小数据测试一下：

当 n=2 时：一对点之间只有一条边，反方向那个点永远过不去，NO。

当 n=3 时：注意到可以构造一个三元环，每个点到其他两点分别 1、2 步，YES。

当 n=4 时：题面直接告诉我们 NO 了（也可以自己枚举 2^6 个竞赛图验证）。

于是继续推，发现剩下的 n 全都有解，构造如下。

当 n 为奇数时，可以取循环竞赛图，点 i 向 i+1,i+2,\dots,i+\frac{n-1}{2} 连边（下标对 n 取模）。每个点出度都是 \frac{n-1}{2}，一步能覆盖后面连续 \frac{n-1}{2} 个点，两步能覆盖剩下的，所以任意两点距离不超过 2。

当 n 为偶数时：先对前 n-1 个点（奇数个）做上面的循环竞赛图，第 n 个点这样接：n 向所有奇数编号的点连边，所有偶数编号的点向 n 连边。因为我认为不可能这么简单，所以来让我们检查一下：

所有情况下复杂度 O(n^2)，不会 TLE ，这正是我们想要的。

参考代码

:::success[AC CODE]

#include<bits/stdc++.h>
using namespace std;
int n;
int a[505][505];                        // 邻接矩阵
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    if(n==2||n==4){
        cout<<"NO";
        return 0;
    }
    cout<<"YES"<<endl;
    if(n%2==1){
        for(int i=1;i<=n;i++){
            for(int k=1;k<=n/2;k++){    // 循环竞赛图: i 向 i+1..i+(n-1)/2
                a[i][(i-1+k)%n+1]=1;
            }
        }
    }
    else{
        int m=n-1;
        for(int i=1;i<=m;i++){          // 前 n-1 个点建循环竞赛图
            for(int k=1;k<=m/2;k++){
                a[i][(i-1+k)%m+1]=1;
            }
        }
        for(int i=1;i<=m;i++){       // 第 n 个点: 奇数点 <- n, 偶数点 -> n
            if(i%2==1){
                a[n][i]=1;
            }
            else{
                a[i][n]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;                     //换行是个好习惯
    }
    return 0;
}

:::

:::info[AI 使用说明] 本文使用 DeepSeek 进行了润色。 :::