蓝桥杯-统计子矩阵

统计子矩阵

题目链接

思路：

1. 使用前缀和+滑动窗口 ，可以先计算出纵向或横向的前缀和，matrix[i][j]表示前i行第j列之和

2. 然后遍历上边界top和下边界buttom，再这个上下边界内使用滑动窗口，由于前面维护了纵向前缀和，所以转化成类似一维的滑动窗口。

3. 滑动窗口[l,r]：遍历右端点，根据区间和调整左端点，如果区间和大了，左端点右移。注意区间和也要移除左端点，直到找到满足的区间，区间大小r-l+1就是以r为右端点的满足条件子矩阵个数，累加即可

#include <iostream>
using namespace std;
const int MAXN=502;
int matrix[MAXN][MAXN];
int n,m,k,ans=0;int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&matrix[i][j]);matrix[i][j]+=matrix[i-1][j]; //前缀和：第i行j列为第1行到第i行j列的和}}//枚举上下边界for(int top=1;top<=n;top++){for(int buttom=top;buttom<=n;buttom++){int l=1,r=1; //滑动窗口的左右端点int sum=0; //滑动窗口的和for(r=1;r<=m;r++){ //枚举右端点sum+=matrix[buttom][r]-matrix[top-1][r]; //更新区间和：加上右端那一列的值while(sum>k){sum-=matrix[buttom][l]-matrix[top-1][l]; //当前矩阵的sum大于k，缩减左端l++;}ans+=r-l+1; //方法数就是区间大小}}}cout<<ans<<endl;return 0;
}