1.小美的平衡矩阵

一开始暴力搜索，超时了

因此必须优化，时间主要浪费在了“计数一个范围内的0和1的个数”

所以用一个二维前缀和，psum[row][col] 表示 grid[row][0:col] 中1的个数，也就是预计算

这样在执行“计数一个范围内的0和1的个数”，只需要遍历每一行的前缀和，从二维降到了一维

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> grid;
vector<vector<int>> psum; // 记录grid[row][0:col]中1的个数
bool count(int scale, int row, int col) {
    int cnt1 = 0;
    for(int i = row; i < row + scale; i++) {
        if(col) cnt1 += psum[i][col+scale-1] - psum[i][col-1];
        else cnt1 += psum[i][scale-1];
    }
    return cnt1 * 2 == scale * scale;
}
int search(int scale) {
    int cnt = 0;
    for(int i = 0; i <= n - scale; i++) {
        for(int j = 0; j <= n - scale; j++) {
            if(count(scale, i, j)) {
                cnt++; 
                // if(scale == 2) {
                //     cout << "start:" << i << " " << j << endl;
                // }
            }
        }
    }
    return cnt;
}
int main() {
    cin >> n;
    grid.resize(n, vector<int>(n, 0));
    psum.resize(n, vector<int>(n, 0)); 
    vector<string> str(n);
    for(int i = 0; i < n; i++) {
        cin >> str[i];
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            grid[i][j] = str[i][j] - '0';
        }
    }

    for(int i = 0; i < n; i++) {
        if(grid[i][0]) psum[i][0] = 1;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 1; j < n; j++) {
            psum[i][j] = psum[i][j-1] + grid[i][j];
        }
    }

    for(int i = 1; i <= n; i++) {
        cout << search(i) << endl;
    }
    
    return  0;
}
// 64 位输出请用 printf("%lld")