题解 | 寒假2E-01矩阵

题目大意

给定一个正整数 n，需要构造一个 n×n 的 01 矩阵，满足以下条件：

1.矩阵关于主对角线对称

2.对角线元素为 0

3.矩阵中 0 的连通块个数与 1 的连通块个数之和恰好为 n

4.行和构成 0∼n−1 的排列，列和也构成 0∼n−1 的排列

解题思路

1.什么是回子型的左上角？

回子型矩阵是一种层层环绕的矩阵结构，形似汉字“回”。最外层是一种数字，向内一层换成另一种数字，再向内又换回第一种数字，如此交替。例如 n=5 的回子型矩阵：

0 0 0 0 0

0 1 1 1 0

0 1 0 1 0

0 1 1 1 0

0 0 0 0 0

这个矩阵的左上角 3×3 区域是：

0 0 0

0 1 1

0 1 0

2.为什么用回子型的左上角？

完整回子型虽然连通块结构清晰，但存在两个问题：

1.行和、列和分布过于集中，无法形成 0~n-1 的排列

2.总连通块数约为 2×层数，当 n 较大时远小于 n

但如果只取回子型的左上角，并向整个矩阵进行隔行隔列的拉伸，就能同时解决这两个问题。

示列代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod=998244353;

void solve(){
    int n;
    cin>>n;
    vector<vector<int>>a(n+1,vector<int>(n+1));
    for(int i=2;i<=n;i+=2){
        for(int j=i;j<=n;j++){
            a[i][j]=1;
            a[j][i]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j];
        }
        cout<<"\n";
    }
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}