题目描述
给定一个 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 ≤ Aij ≤ 1000；1 ≤ K ≤ 250000000。
解题思路
这道题的核心在于如何高效地枚举子矩阵并计算其和。暴力枚举四个边界的时间复杂度是 O(N²M²)，在 N, M = 500 时显然会超时。我们需要利用二维前缀和来优化求和操作，将单次查询降为 O(1)。
1. 二维前缀和预处理
首先构建二维前缀和数组 s[i][j]，表示从 (1,1) 到 (i,j) 的矩形区域和。这样任意子矩阵 (x1, y1) 到 (x2, y2) 的和可以通过公式快速计算：
sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
2. 固定上下边界，双指针扫描左右边界
我们可以枚举子矩阵的行范围 [x1, x2]。一旦上下边界确定，问题就转化为了在一维数组中寻找满足和不超过 K 的子段数量。
由于矩阵元素非负，当右边界 r 向右移动时，子矩阵和单调递增；当左边界 l 向右移动时，子矩阵和单调递减。这符合双指针（滑动窗口）的应用场景。
对于每一对固定的行 [x1, x2]：
- 初始化左指针
l = 1。 - 遍历右指针
r从 1 到 M。 - 如果当前子矩阵和超过 K，则不断右移
l直到和小于等于 K。 - 此时，以
r为右边界的所有合法左边界都在[l, r]范围内，数量为r - l + 1。
3. 复杂度分析
- 预处理前缀和：O(NM)。
- 枚举行对：O(N²)。
- 双指针扫描列：每个
r和l最多移动 M 次，整体 O(M)。 - 总时间复杂度：O(N²M)，在 500 的规模下完全可以接受。
代码实现
下面给出 Java 语言的完整实现。注意处理数据读取时的性能问题，使用 BufferedReader 比 Scanner 更快。
java.io.*;
{
;
n, m, k;
[][] a = [N][N];
[][] s = [N][N];
( (System.in));
IOException {
String[] ts = br.readLine().split();
n = Integer.parseInt(ts[]);
m = Integer.parseInt(ts[]);
k = Integer.parseInt(ts[]);
( ; i <= n; i++) {
ts = br.readLine().split();
( ; j <= m; j++) {
a[i][j] = Integer.parseInt(ts[j - ]);
s[i][j] = s[i - ][j] + s[i][j - ] - s[i - ][j - ] + a[i][j];
}
}
;
( ; x1 <= n; x1++) {
( x1; x2 <= n; x2++) {
;
( ; r <= m; r++) {
(l <= r && getSum(x1, l, x2, r) > k) {
l++;
}
res += () (r - l + );
}
}
}
System.out.println(res);
}
{
s[x2][y2] - s[x1 - ][y2] - s[x2][y1 - ] + s[x1 - ][y1 - ] <= k;
}
{
s[x2][y2] - s[x1 - ][y2] - s[x2][y1 - ] + s[x1 - ][y1 - ];
}
}
