题解：CF1917E Construct Matrix

_endl_ · 2026-11-11 18:34:13 · 题解

随便想想就能发现 2\nmid k 无解。

当 n>2 时，k=2 和 k=n^2-2 无解。k=2 穷举一下状态也能看出来，k=n^2-2 就是 k=2 全局反转一下。

然后开始分讨。

• k \bmod 4 = 0

  直接瞎放那种 2\times 2 正方形就行。这个显然是最优的没有浪费的。

• k \bmod 4 = 2

  考虑通过一个消耗 6 个 1 的最小结构，比如：

  011
  101
  110

  我们希望构造一个每行、每列都有偶数个 1，且 1 的数量模 4 余 2 的局部结构。由于两个 1 无法同时满足行列异或均为 0，因此最小需要 6 个 1。

  然后把他丢到左上角，因为 n 是偶数所以再空一行一列，剩下的开始放 2\times 2小正方形。

  注意此时需要特判 n=2 手动构造。

  还要特判 k=n^2-6，因为你填完左上角之后，剩下还能填 \frac{n^2-16}4 个方块，所以这么构造最多放 n^2-10 个 1。还有一个 k=n^2-6 没考虑，此时只需要全填成 1，把左上角原来的 1 改成 0 即可。

Code.

#include<bits/stdc++.h>
using namespace std;
#define main(x) MiAn();int mIaN();main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;if(strlen(#x))cin>>t;while(t--)mIaN();cerr<<"Time: "<<1.0*clock()/CLOCKS_PER_SEC<<"s\n";}int mIaN()
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define mem(a,b) memset((a),(b),sizeof(a))
#define all(x) (x).begin(),(x).end()
#define abs_(x) ((x)<0?-(x):(x))
#define sz(x) ((int)(x).size())
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
int n,k;
bool ans[2005][2005];
int main(111){
    cin>>n>>k;
    if(!k){
        cout<<"Yes\n";
        rep(i,1,n){
            rep(j,1,n){
                cout<<"0 ";
            }
            cout<<"\n";
        }
        return 0;
    }
    rep(i,1,n){rep(j,1,n){ans[i][j]=0;}}
    if((k&1)||(n>2&&(k==2||k==n*n-2))){cout<<"No\n";return 0;}
    if(!(k%4)){
        cout<<"Yes\n";
        int cnt=0;
        for(int x=1;x<=n&&cnt<(k>>2);x+=2){
            for(int y=1;y<=n&&cnt<(k>>2);y+=2){
                ans[x][y]=ans[x+1][y]=ans[x][y+1]=ans[x+1][y+1]=1;
                cnt++;
            }
        }
        rep(i,1,n){
            rep(j,1,n){
                cout<<ans[i][j]<<' ';
            }
            cout<<"\n";
        }
    }
    else{
        if((k==2||k==n*n-2)&&n>2){
            cout<<"No\n";
            return 0;
        }
        if(n==2) ans[1][1]=ans[2][2]=1;
        else if(k==n*n-6){
            rep(i,1,n) rep(j,1,n) ans[i][j]=1;
            ans[1][1]=ans[1][2]=ans[2][1]=0;
            ans[2][3]=ans[3][2]=ans[3][3]=0;
        }
        else{
            ans[1][1]=ans[1][2]=ans[2][1]=1;
            ans[2][3]=ans[3][2]=ans[3][3]=1;
            k-=6;
            for(int x=1;x<=n&&k;x+=2){
                for(int y=1;y<=n&&k;y+=2){
                    if(x<=4&&y<=4) continue;
                    ans[x][y]=ans[x+1][y]=1;
                    ans[x][y+1]=ans[x+1][y+1]=1;
                    k-=4;
                }
            }
        }
        cout<<"Yes\n";
        rep(i,1,n){
            rep(j,1,n) cout<<ans[i][j]<<' ';
            cout<<"\n";
        }
    }
    return 0;
}