「土」秘法地震

我吐槽下这题,输入输出的问题,然后时间高了四五倍.........
题意:求解无效轰炸有多少次,解释下什么叫有效轰炸,也就是在 区间内不存在1,就是有效轰炸
题解:二维前缀和模板题(算是dp吧)
如果对于每一位枚举,时间复杂度:(看题解他们有人说能过去,额,不知道咋说)
现在我们优化这个
参考链接:https://www.cnblogs.com/hulean/p/10824752.html
先计算(1,1)到(i,j)这个大的矩形之内存在的1的数量
套用下大佬的图

计算方法, 因为对于(i-1,j)和(i,j-1)都有(i-1,j-1)这部分的面积,所以可以这两部分相加减去(i-1,j-1)
然后下来求答案
那还是按照这个图来看把(i-1,j-1)(i-1,j)(i,j-1)其中的1换成k,就能得到(i-k,j-k)到(i,j)其中的1的个数
简单说下为啥这样做:我们相当于枚举每个矩形的右下坐标,然后来判断这个矩形是否成立,因为这两个条件完全可以确定一个矩阵
时间复杂度:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1001][1001],s[1001][1001],ans;
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%1d",&a[j][i]);
            s[j][i]=s[j-1][i]+s[j][i-1]-s[j-1][i-1]+a[j][i];
        }
    }
    for(int i=k;i<=n;i++)    for(int j=k;j<=m;j++){
        if(s[j][i]-s[j-k][i]-s[j][i-k]+s[j-k][i-k]>0)    ans++;
    }
    cout<<ans<<endl;
    return 0;
}