蓝桥杯B组统计子矩阵

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

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

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

一个整数代表答案。

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 个。

【评测用例规模与约定】

对于 30% 的数据, N,M≤20.

对于 70%的数据, N,M≤100.

对于 100% 的数据, 1≤N,M≤500,0≤A_ij​≤1000,1≤K≤2.5×10⁸.

蓝桥杯 2022 省赛 B 组 F 题。

解答：

常规思路，用二维前缀和的方法，时间复杂度为o(n⁴),如果n,m为500，显然会超时，但是可以过70%的数据。

代码：

#include<iostream>
#include<algorithm>
//时间复杂度o(n4);
using namespace std;
const int M = 600;
int ma[M][M];
int sum[M][M];//前缀和
long long ans=0;
int m, n,c;
int main()
{
	cin >> n>> m >> c;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> ma[i][j];
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ma[i][j];//前缀和,没问题
		}
	}
	int a;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (ma[i][j] > c)
				break;
			for (int k = i; k <= n; k++)
			{
				if ((sum[k][j] - sum[k][j - 1] - sum[i - 1][j] + sum[i - 1][j - 1]) > c)
					break;
				for (int b = j; b <= m; b++)
				{
					a = sum[k][b] - sum[i-1][b] - sum[k][j-1] + sum[i-1][j-1];
					if (a > c)
					{
						break;
					}	
						ans++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

因为矩阵里的每一个数都是大于0的，所以当矩阵里多元素的时候，矩阵是单调递增的，所以可以考虑双指针，利用双指针来解答，二维前缀和为o(n⁴)，会超时，所以我们可以采用一维前缀和的方法，将每一列进行前缀和，然后固定上下高度，用双指针来判断，将o(n⁴)降为o(n³)；具体代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 600;
int a[M][M];
int sum[M][M];
long long ans = 0;
int n, m, k;
int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			sum[i][j] += sum[i - 1][j] + a[i][j];//一维前缀和统计每一列的；
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{
			for (int l = 1, r = 1,h=0; r <= m; r++)//双指针优化
			{
				h += sum[j][r] - sum[i - 1][r];
				while (h>k)
				{
					h -= sum[j][l] - sum[i - 1][l];
					l++;
				}
				ans +=r-l+1;
			}
		}
	}
	cout << ans;
	return 0;
}

完结！