题目链接:0统计子矩阵 - 蓝桥云课 (lanqiao.cn)
代码
#include<iostream>
using namespace std;
const int N = 505;
int num[N][N];
int main() {
int n, m, k;
cin >> n >> m >> k;
int count = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> num[i][j];
num[i][j] += num[i - 1][j] + num[i][j - 1] - num[i - 1][j - 1];
}
}
//打印二维前缀和效果
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << num[i][j] << " ";
// }
// cout << endl;
// }
//for循环超时
// for (int x1 = 1; x1 <= n; x1++) {
// for (int y1 = 1; y1 <= m; y1++) {
// for (int x2 = x1; x2 <= n; x2++) {
// for (int y2 = y1; y2 <= m; y2++) {
// if (num[x2][y2] - num[x2][y1 - 1] - num[x1 - 1][y2] + num[x1 - 1][y1 - 1] <= k) {
// count++;
//// cout << k << " " << z << " " << i << " " << j << "##" << endl;
// }
//// cout << k << " " << z << " " << i << " " << j << endl;
// }
// }
// }
//// }
// cout << count;
for (int l = 1; l <= m; l++) {
for (int r = l; r <= m; r++) {
for (int u = 1, d = 1; d <= n; d++) {
while (u <= d && num[d][r] - num[d][l - 1] - num[u - 1][r] + num[u - 1][l - 1] > k) {
u++;
}
count += d - u + 1;
}
}
}
cout << count;
return 0;
}
标签:count,前缀,int,矩阵,二维,num
From: https://www.cnblogs.com/zuoxiaochen/p/18225290