AcWing 4405. 统计子矩阵
原题链接
中等
作者:
双水
,
2024-03-25 21:18:50
,
所有人可见
,
阅读 2
二维前缀和
二维前缀和原理
/*S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k;
long long ans;
int a[N][N];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
a[i][j]=a[i][j-1]+a[i-1][j]+a[i][j]-a[i-1][j-1];
}
}
//二维前缀和
for(int i=1;i<=m;i++)//i表示左侧
{
for(int j=i;j<=m;j++)//j表示右侧
{
//如果s-t之间有符合的,我就记录下来,然后逐渐下降
for(int s=1,t=1;t<=n;t++)//t表示下侧,s表示上侧。
{
while(s <= t && a[t][j] - a[s - 1][j] - a[t][i - 1] + a[s - 1][i - 1] > k) s ++ ;
if(s <= t) ans += t - s + 1;//表示中间矩阵的数量
}
}
}
cout<<ans;
}