AcWing 4405. 统计子矩阵(不是很熟,明天在打一遍)
原题链接
中等
作者:
YMYS
,
2024-04-11 20:33:11
,
所有人可见
,
阅读 16
//2024.4.11
//https://www.lanqiao.cn/problems/2109/learning/
//统计子矩阵
/*
思路:
1、我们思考,这道题肯定使用前缀和,但是如果使用二维的前缀和,会使得的最后遍历整个数组的时候。
左上(i,j)二重循环,右下(k,l)也需要二重循环,那我们一共嵌套起来就是四层循环。这样会TLE
2、所以我们采用“化二维为一维的前缀和”使用算法,使得整个遍历降到三维
3、刚开始我在想为什么最外层循环的i必须是上指针。为社么不能把i指针变为下指针。
答:因为最外层循环i在慢慢往下走,j每次也是1开始慢慢往下走。
如果说找到了一个大矩阵刚好满足该矩阵的和小于等于K,那么i不变j往下的矩阵一定也是小于K的,我们这样就没办法把四维的变二维的去遍历了
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510;
int n,m,k;
int a[N][N];//a[i][j]表示a[i][0]一直加到a[i][j]的这一列的和
int b[N];//一维的中间数组
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
cin>>n>>m>>k;
for(int i=1;i<=n;i++){//i行j列
for(int j=1;j<=m;j++){
cin>>a[i][j];
a[i][j] += a[i-1][j];
//cout<<a[i][j]<<' ';
}
//cout<<endl;
}
int res = 0;
for(int i=1;i<=n;i++){//上指针
for(int j=i;j<=n;j++){//下指针
for(int r=1, l=1, sum = 0;r<=m;r++){//每次到该层循环,都重新把sum置为0
sum += a[j][r] - a[i-1][r];
while (sum>k)
{
sum-=a[j][l] - a[i-1][l];
l++;
}
res += r-l+1;
}
}
}
cout<<res<<endl;
return 0;
}