「土」秘法地震 题解

本来打算只写一种解法的，不过感觉太水了，就多写点吧

解法一.暴力

按照题目说的模拟去做，复杂度,期望得分：70-100(数据有点弱啊qwq)

解法二.带优化的暴力

我们设a[i][j]表示i,j点的正下面中，包含i,j的k格格子中是否至少存在一个1。

这个直接暴力统计就好了，当然，你要把存在改成有几个的话，就可以直接计算了

然后，我们枚举每个k*k矩形的左上角，设为(x,y)，那么，我们只要中有一个1，那么这个k*k的矩形中就会有一个1。直接暴力统计或者跟上面的方法一样计算也行。

复杂度：,期望得分:100

解法三.二维前缀和

我们直接预处理出二维前缀和（每个点到1,1所构成的矩阵中，元素之和）

那么， 我们还是枚举一个左上角，然后直接根据二维前缀和的公式，就可以O(1)算出以(x,y)为左上角的一个k*k的矩形的所有元素之和，如果和大于0，则说明其中必然有至少一个1，那么答案加1即可

复杂度：,期望得分:100

代码：

[可过版甚至比我正解还快]

```#include<bits/stdc++.h>
using namespace std;
const int N=1001;
bool s[N][N],q[N][N];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%1d",&s[i][j]);//输入小技巧，即只输入一个数字
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(s[i][j]){
                for(int t=max(1,i-k+1);t<=i;++t){
                    for(int p=max(1,j-k+1);p<=j;++p){
                        q[t][p]=1;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n-k+1;++i){
        for(int j=1;j<=m-k+1;++j){
            ans+=q[i][j];
        }
    }
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
bool s[N][N];
bool a[N][N],q[N][N];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%1d",&s[i][j]);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(s[i][j]){
                for(int t=i;t>=max(1,i-k+1);--t){
                    a[t][j]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int t=j;t<=min(m,j+k-1);++t){
                q[i][j]|=a[i][t];
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n-k+1;++i){
        for(int j=1;j<=m-k+1;++j){
            ans+=q[i][j];
        }
    }
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
bool s[N][N];int a[N][N],b[N][N];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%1d",&s[i][j]);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=k;++j){
            a[i][1]+=s[i][j];
        }
        for(int j=2;j<=m-k+1;++j){
            a[i][j]=a[i][j-1]-s[i][j-1]+s[i][j+k-1];
        }
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=k;++j){
            b[1][i]+=a[j][i];
        }
        for(int j=2;j<=n-k+1;++j){
            b[j][i]=b[j-1][i]-a[j-1][i]+a[j+k-1][i];
        }
    }
    int ans=0;
    for(int i=1;i<=n-k+1;++i){
        for(int j=0;j<=m-k+1;++j){
            ans+=(b[i][j]>0);
        }
    }
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int s[N][N];
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%1d",&s[i][j]);
        }
    }
    for(int i=2;i<=n;++i){
        s[i][1]+=s[i-1][1];
    }
    for(int i=2;i<=m;++i){
        s[1][i]+=s[1][i-1];
    }
    for(int i=2;i<=n;++i){
        for(int j=2;j<=m;++j){
            s[i][j]+=(s[i-1][j]+s[i][j-1]-s[i-1][j-1]);
        }
    }
    int ans=0;
    for(int i=1;i<=n-k+1;++i){
        for(int j=1;j<=m-k+1;++j){
            int a=i,b=j,c=i+k-1,d=j+k-1;
            ans+=((s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1])>0);
        }
    }
    printf("%d",ans);
    return 0;
}