「土」秘法地震（二维前缀和）

题目：

给一个nm的01矩阵。问有多少个kk的含1矩阵。（n最大1000）

做法：

二维前缀和。跟板子没啥区别。。
利用二维前缀和可以快速得到某矩形区域中数字的和。那么枚举所有k*k矩阵的右下角位置，利用二维前缀和得到矩阵中1的数量，大于零则ans++即可。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1010;
char s[N];
int prefix[N][N];
int main(void){ 
    IOS;
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i){
        cin >> (s+1);
        for (int j = 1; j <= m; ++j){
            if (s[j] == '1'){
                prefix[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            prefix[i][j] += prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];
        }
    }
    int ans = 0;
    for (int i = k; i <= n; ++i){
        for (int j = k; j <= m; ++j){
            int cnt = prefix[i][j]-prefix[i][j-k]-prefix[i-k][j]+prefix[i-k][j-k];
            if (cnt) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}