题目来源:第十三届蓝桥杯软件赛省赛 B组
给定一个 N × M N \times M N×M 的矩阵 A A A , 请统计有多少个子矩阵 (最小 1 × 1 1\times 1 1×1, 最大 N × M N \times M N×M) 满足子矩阵中所有数的和不超过给定的整数 K K K ?
输入 : 第一行包括三个整数 N , M N, M N,M 和 K K K
之后 N N N 行包含 M M M 个整数, 代表矩阵 A A 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;
}