「土」秘法地震
「土」秘法地震
https://ac.nowcoder.com/acm/problem/53676
我吐槽下这题,输入输出的问题,然后时间高了四五倍.........
题意:求解无效轰炸有多少次,解释下什么叫有效轰炸,也就是在 区间内不存在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;
}
查看14道真题和解析