题目传送门
题目描述
给定一个N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K。
输入格式
第一行包含三个整数 N,M 和 K。
之后 N 行每行包含 M 个整数, 代表矩阵 A。
输出格式
一个整数代表答案。
输入输出样例
输入 #13 4 10
1 2 3 4
5 6 7 8
9 10 11 1219说明/提示
【样例说明】
满足条件的子矩阵一共有 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≤2.5×108.
蓝桥杯 2022 省赛 B 组 F 题。
解答：
常规思路，用二维前缀和的方法，时间复杂度为o(n4),如果n,m为500，显然会超时，但是可以过70%的数据。
代码：
#include<iostream>
#include<algorithm>
//时间复杂度o(n4);
using namespace std;
const int M = 600;
int ma[M][M];
int sum[M][M];//前缀和
long long ans=0;
int m, n,c;
int main()
{
cin >> n>> m >> c;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> ma[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + ma[i][j];//前缀和,没问题
}
}
int a;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (ma[i][j] > c)
break;
for (int k = i; k <= n; k++)
{
if ((sum[k][j] - sum[k][j - 1] - sum[i - 1][j] + sum[i - 1][j - 1]) > c)
break;
for (int b = j; b <= m; b++)
{
a = sum[k][b] - sum[i-1][b] - sum[k][j-1] + sum[i-1][j-1];
if (a > c)
{
break;
}
ans++;
}
}
}
}
cout << ans;
return 0;
}因为矩阵里的每一个数都是大于0的，所以当矩阵里多元素的时候，矩阵是单调递增的，所以可以考虑双指针，利用双指针来解答，二维前缀和为o(n4)，会超时，所以我们可以采用一维前缀和的方法，将每一列进行前缀和，然后固定上下高度，用双指针来判断，将o(n4)降为o(n3)；具体代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int M = 600;
int a[M][M];
int sum[M][M];
long long ans = 0;
int n, m, k;
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
sum[i][j] += sum[i - 1][j] + a[i][j];//一维前缀和统计每一列的；
}
}
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
for (int l = 1, r = 1,h=0; r <= m; r++)//双指针优化
{
h += sum[j][r] - sum[i - 1][r];
while (h>k)
{
h -= sum[j][l] - sum[i - 1][l];
l++;
}
ans +=r-l+1;
}
}
}
cout << ans;
return 0;
}完结！
标签：前缀,int,sum,矩阵,long,蓝桥,include,统计 From： https://www.cnblogs.com/haggard/p/17250226.html