题目链接
A. Maximal Binary Matrix（Codeforces 803A）
思路
本题的入手点是，先满足“字典序最小”的要求，再满足对称性（就比较容易了）。
由于题目要求解的“字典序”最小，所以可以先按照行从上到下，再按照列从左到右的顺序为矩形填上 1 （也就是在作文纸上写字的顺序）。然后就只需要满足对称性了。假设当前我们已经填到
- 当 i=j 时，由于当前填的位置位于对角线上，填上后肯定不会影响对称性，所以能填就填。什么是不能填的情况呢？如果填 1 的次数没有剩余了的话就不能填了。
- 当
i!=j 时，由于当前填的位置不位于对角线上，所以如果要在 (i,j) 网格内填数的话就得在 (j,i) 网格内填数。有如下情况就不能填：剩余的填 1 次数为1 ， (i,j) 网格内已经填过 1 了。
代码
#include <bits/stdc++.h>
using namespace std;const int maxn = 110;
int n, k, a[maxn][maxn];// 输出矩阵
void output() {for(int i = 1; i <= n ;i++) {for(int j = 1; j <= n; j++) {cout << a[i][j] << ' ';}cout << endl;}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;// k比格子还要多的时候if(k > n * n) {cout << -1 << endl;return 0;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(k == 0) {output();return 0;}if(a[i][j] == 1) {continue;}// 填对角线位置if(i == j) {a[i][j] = 1;k--;}// 填非对角线位置else if(k >= 2) {a[i][j] = a[j][i] = 1;k -= 2;}}}if(k > 0) {cout << -1 << endl;}else {output();}return 0;
}B. Distances to Zero（Codeforces 803B）
思路
本题的入手点在于将问题“找离某位置最近的
我们只考虑“找在数组中的位置的 i 左侧最近
代码
#include <bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 10, INF = 3e5;
int n, last, a[maxn], b[maxn], c[maxn];int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;for(int i = 0; i < n; i++) {cin >> a[i];}// 从左到右扫描数组，寻找离位置i最近的左侧的0last = -1;for(int i = 0; i < n; i++) {if(a[i] == 0) {b[i] = 0;last = i;}else if(last >= 0) {b[i] = i - last;}else {b[i] = INF;}}// 从右到左扫描数组，寻找离位置i最近的右侧的0last = -1;for(int i = n - 1; i >= 0; i--) {if(a[i] == 0) {c[i] = 0;last = i;}else if(last >= 0) {c[i] = last - i;}else {c[i] = INF;}}// 输出答案for(int i = 0; i < n; i++) {cout << min(b[i], c[i]) << ' ';}return 0;
}C. Maximal GCD（Codefoeces 803C）
思路
本题的入手点为考虑到数列的