蓝桥杯每日一题：统计子矩阵

题目来源：第十三届蓝桥杯软件赛省赛 B组

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

输入 : 第一行包括三个整数$N, M$ 和$K$

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

输出 : 一个整数代表答案

Input Sample :

3 4 10

1 2 3 4

5 6 7 8

9 10 11 12

Output Sample :

19

思路: 前缀和 + 滑动窗口

我最开始考虑的方法是 二维前缀和, 因为这是一个二维矩阵, 但后续发现用二维前缀和会tle. 看了题解思路才知道其实可以变成一位前缀和, 只统计纵向的前缀和, 然后用滑动窗口找到合适的区间

下面给出题解代码, 请注重思考, 不要无脑cv

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
int a[maxn][maxn];
ll ans = 0;

void io() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

int main() {
	io();
	int n, m, k;
	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++) {
			int l = 1, sum = 0;
			for (int r = 1; r <= m; r++) {
				sum += a[j][r] - a[i - 1][r];
				while (sum > k) {
					sum -= a[j][l] - a[i - 1][l];
					l++;
				}
				ans += r - l + 1;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}