第十三届蓝桥杯 B组题目 统计子矩阵

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

输入格式

第一行包含三个整数 N,M 和 K。

之后 N 行每行包含 M 个整数，代表矩阵 A。

输出格式

一个整数代表答案。

数据范围

对于 30% 的数据，N,M≤20，
对于 70% 的数据，N,M≤100，
对于 100% 的数据，1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000。

输入样例：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例：

19

样例解释

满足条件的子矩阵一共有 19，包含：

• 大小为 1×1 的有 10 个。
• 大小为 1×2 的有 3 个。
• 大小为 1×3 的有 2 个。
• 大小为 1×4 的有 1 个。
• 大小为 2×1 的有 3 个。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long int cnt=0;
int a[505][505];
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 j=i;j<=n;j++)//限制下边界 
			for(int l=1,r=1,sum=0;r<=m;r++)//限制左右边界 
			{
				sum+=a[j][r]-a[i-1][r];//依次加上右边一列的前缀和
				while(sum>k)
				{
					sum-=a[j][l]-a[i-1][l];//减去最左边的前缀和
					l++;//左边界右移 
				} 
				cnt+=r-l+1; 
			}
			
	cout<<cnt<<endl;
	return 0;
 }