蓝桥杯真题 2109.统计子矩阵

原题地址:1.统计子矩阵 - 蓝桥云课

问题描述

给定一个 N×MN×M 的矩阵 AA, 请你统计有多少个子矩阵 (最小 1×11×1, 最大 N×M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK ?

输入格式

第一行包含三个整数 N,MN,M 和 KK.

之后 NN 行每行包含 MM 个整数, 代表矩阵 AA.

输出格式

一个整数代表答案。

具体代码和思路如下:

#include <iostream>
using namespace std;int n,m,k;
int a[501][501];
long long ans = 0;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 - 1][j];}}for (int i = 1;i <= n;++i){//滑动窗口的上边界for (int ii = i;ii <= n;++ii){//滑动窗口的下边界int l = 1,r = 1;//l为滑动窗口的左边界，r为滑动窗口的右边界int sum = 0;//sum为当前滑动窗口内所有元素的和,即小区间[l,r]的和for (r = 1;r <= m;++r){//更新右边界sum += a[ii][r] - a[i - 1][r];//加入新扩大的窗口的边界值while (sum > k){//当sum大于k时，就停止更新右边界r，开始让左边界l向右移，直到区间[l,r]内的值小于等于ksum -= a[ii][l] - a[i - 1][l];//由于左边界l要向右移，所以要减去原来左边界上的值l++;}//当区间[l,r]内的所有元素和小于等于k时，就说明该区间内的所有子区间的区间和都要小于等于kans += r - l + 1;}}}cout<<ans;return 0;
}