1.统计子矩阵 - 蓝桥云课
统计子矩阵
问题描述
给定一个 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。
思路：
暴力枚举四个循环
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 505;
ll a[MAX][MAX], pre[MAX][MAX];int main() {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];pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];}}ll ans = 0;for (int i = 1; i <= N; ++i) {for (int j = 1; j <= M; ++j) {int max_n = N - i + 1; // 行方向最大延展数int max_m = M - j + 1; // 修正此处：列方向最大延展数for (int n = 1; n <= max_n; ++n) { // 遍历行数for (int m = 1; m <= max_m; ++m) { // 遍历列数int x2 = i + n - 1;int y2 = j + m - 1;ll sum = pre[x2][y2] - pre[i-1][y2] - pre[x2][j-1] + pre[i-1][j-1];if (sum <= K) ans++;}}}}cout << ans << endl;return 0;
}
思路：
双指针优化
代码: