Codeforces1917E - Construct Matrix
首先考虑因为 \(n\) 为偶数，所以 \(k\) 为奇数时不可能满足条件。
其次，如果 \(4|k\)，那么实际上在矩阵中一直放 \(2\times 2\) 的全为 \(1\) 的矩阵就可以了。
随后，如果 \(k \equiv 2 \mod 4\)，那么可以证明如果 \(k \ne 2 \land k \ne n^2-2\) ，那么必然有解。
我们在右下角预留一个 \(4\times 4\) 的矩阵填，先填其他位置。
然后会发现这个 \(4\times 4\) 的矩阵中，除了 \(k' = 2\) 和 \(k' = 14\) 的情况没法填，其他都有解。
又因为 \(k \ne 2 \land k \ne n^2-2\)，所以对于 \(k'=2\) 在外面少填某个 \(2\times 2\) 的矩阵即可；对于 \(k'=14\) 在外面多填某个 \(2\times 2\) 的矩阵即可。
另外 \(k=2\) 或 \(k=n^2-2\) 的情况，有解当且仅当 \(n=2\)。
代码写得很丑因为是边想边写的。
#include <bits/stdc++.h>
using namespace std;
int n, k;
int mp[1005][1005], ans[20][5][5];
int tgr[5], tgc[5];
int main (){
int T;
scanf ("%d", &T);
for (int i = 0;i < (1 << 16);++ i){
int cnt = 0;
for (int j = 0;j < 4;++ j)
tgr[j] = tgc[j] = 0;
for (int j = 0;j < 16;++ j)
if (i >> j & 1){
++ cnt;
tgr[j / 4] ^= 1;
tgc[j % 4] ^= 1;
}
bool tag = true;
for (int j = 0;j < 4;++ j)
tag = tag && tgr[j] == 0 && tgc[j] == 0;
if (tag){
for (int x = 0;x < 4;++ x)
for (int y = 0;y < 4;++ y)
ans[cnt][x][y] = i >> ((x << 2) + y) & 1;
}
}
while (T --){
scanf ("%d%d", &n, &k);
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= n;++ j)
mp[i][j] = 0;
if (k == 2 || k == n * n - 2){
if (n == 2)
puts ("Yes\n1 0\n0 1");
else
puts ("No");
} else {
if (k & 1)
puts ("No");
else {
if (k % 4 == 0){
puts ("Yes");
for (int i = 1;i <= n && k > 0;i += 2)
for (int j = 1;j <= n && k > 0;j += 2){
k -= 4;
mp[i][j] = mp[i + 1][j] = mp[i][j + 1] = mp[i + 1][j + 1] = 1;
}
for (int i = 1;i <= n;++ i, puts (""))
for (int j = 1;j <= n;++ j)
printf ("%d ", mp[i][j]);
} else {
if (k % 16 != 2 && k % 16 != 14){
int t = (k - 1) % 16 + 1;
k -= t;
for (int i = 1;i <= n && k > 0;i += 2)
for (int j = 1;j <= n && k > 0;j += 2)
if (i <= n - 4 || j <= n - 4){
k -= 4;
mp[i][j] = mp[i + 1][j] = mp[i][j + 1] = mp[i + 1][j + 1] = 1;
}
for (int i = 0;i < 4;++ i)
for (int j = 0;j < 4;++ j)
mp[i + n - 3][j + n - 3] = ans[t][i][j];
puts ("Yes");
for (int i = 1;i <= n;++ i, puts (""))
for (int j = 1;j <= n;++ j)
printf ("%d ", mp[i][j]);
} else
if (k % 16 == 2){
int t = 6;
k -= t;
for (int i = 1;i <= n && k > 0;i += 2)
for (int j = 1;j <= n && k > 0;j += 2)
if (i <= n - 4 || j <= n - 4){
k -= 4;
mp[i][j] = mp[i + 1][j] = mp[i][j + 1] = mp[i + 1][j + 1] = 1;
}
for (int i = 0;i < 4;++ i)
for (int j = 0;j < 4;++ j)
mp[i + n - 3][j + n - 3] = ans[t][i][j];
puts ("Yes");
for (int i = 1;i <= n;++ i, puts (""))
for (int j = 1;j <= n;++ j)
printf ("%d ", mp[i][j]);
} else
if (k % 16 == 14){
int t = 10;
k -= t;
for (int i = 1;i <= n && k > 0;i += 2)
for (int j = 1;j <= n && k > 0;j += 2)
if (i <= n - 4 || j <= n - 4){
k -= 4;
mp[i][j] = mp[i + 1][j] = mp[i][j + 1] = mp[i + 1][j + 1] = 1;
}
for (int i = 0;i < 4;++ i)
for (int j = 0;j < 4;++ j)
mp[i + n - 3][j + n - 3] = ans[t][i][j];
puts ("Yes");
for (int i = 1;i <= n;++ i, puts (""))
for (int j = 1;j <= n;++ j)
printf ("%d ", mp[i][j]);
}
}
}
}
}
return 0;
}