题目 2659:蓝桥杯2022年第十三届省赛真题

题目 2659:蓝桥杯2022年第十三届省赛真题

题目描述

给定一个 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 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

---

思路：

一开始我们都会想到二维前缀和、四层循环暴力枚举，但果不其然肯定是超时的

#include<iostream>
#include<cstring>
using namespace std;
//考察二维前缀和
int a[520][520];
int n,m;
long long  res,k;
int main()
{memset(a,0,sizeof a);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]+a[i][j-1]-a[i-1][j-1];}}for(int i=1;i<=n;i++)//确定左上和右下暴力枚举{for(int j=1;j<=m;j++){for(int u=i;u<=n;u++){for(int v=j;v<=m;v++){int p=a[u][v]-a[i-1][v]-a[u][j-1]+a[i-1][j-1];if(p<=k) res++;else break;}}}}cout<<res<<endl;
} 

后来借鉴了其他大佬的解法后， 发现用双指针可以优化，减小时间复杂度
用二维数组去表示了每一列的前缀和，然后通过控制上下边界和左右边界的移动来控制矩阵的大小以及它的遍历

#include<iostream>
#include<cstring>
using namespace std;
//考察二维前缀和
int a[520][520];
int n,m;
long long res,k;
int main()
{memset(a,0,sizeof a);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];//表示第j列前i行的和 }}//类似于一个滑动窗口//i j控制滑动窗口的上下边界 l r控制滑动窗口的左右边界 for(int i=1;i<=n;i++)//起始的行 {for(int j=i;j<=n;j++)//终止的行 {for(int l=1,r=1,sum=0;r<=m;r++)//l表示左边界 r表示右边界 sum表示当前窗口（矩阵）块儿的和 {sum+=a[j][r]-a[i-1][r] ;while(sum>k)//保证着res所计算进去的每个矩阵个数  每个矩阵和都是不大于k的 {sum-=a[j][l]-a[i-1][l];//要是大于了k  就保持着窗口大小不变将窗口右移// 也就伴随着左边界l的移动 l++;}res+=r-l+1;    }}}cout<<res<<endl;
} 

我们可以通过样例来简单模拟一下