牛客每日一题—— 「土」秘法地震

题意:问有多少个大小为k*k的矩阵的元素之和至少为1

思路:

​ 因为矩阵的大小已经固定,我们可以直接枚举一下左上角的区间端点,这样就可以根据端点和矩阵大小得到右下角的端点。

​ 这时候如果再遍历区间的话,复杂度就是O(n^4),所以我们要想办法优化一下。

​ 枚举是必不可少的,这时候就可以把查询变成O(1)查询。

​ 这时候就要用到二维前缀和了!

​ 前缀和是可以通过预处理的方式使得最后的查询为O(1)查询,一维的前缀和就是维护一个一维数组然后逐项累加,其中s[i]表示从1到i的数组元素的和,查询的时候只需要输出s[r]-s[l-1]即可。

二维前缀和则是维护一个二维数组,s[i] [j]表示左上角端点为(1,1),右下角端点为(i,j)的矩形的元素之和

    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

所以(x1,y1),(x2,y2)的子矩阵之和就是

s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

可以画图理解一下~

综上所述:本题可以先预处理出二维前缀和表示子矩阵的和,再通过枚举左上角端点的情况来得到大小为k*k的子矩阵的和,如果这个和大于1的话,答案就+1。

另外,对于矩阵的输入有两种方法,一是通过字符串或字符数组输入,二是可以通过

 scanf("%1d",&g[i][j]);

输入,表示逐位输入。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
int s[maxn][maxn];
int a[maxn][maxn];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    int res=0;
    for(int i=1;i+k-1<=n;i++)
        for(int j=1;j+k-1<=m;j++)
                if(s[i+k-1][j+k-1]-s[i-1][j+k-1]-s[i+k-1][j-1]+s[i-1][j-1]>0) res++;
    cout<<res<<endl;
    return 0;
}