自己怎么制作公众号_最新军事新闻头条重大_免费的个人网站怎么做_seo排名啥意思

统计子矩阵

2024-12-5 蓝桥杯每日一题 统计子矩阵 前缀和 双指针

题目大意

给定一个 $N\times M$的矩阵 A, 请你统计有多少个子矩阵 (最小$ 1×1$, 最大 $N\times M$) 满足子矩阵中所有数的和不超过给定的整数 K ?

解题思路

1. 乍一看这个题与矩阵有关，而且又让求子矩阵的总和，那么很自然的就会想到二维前缀和，然后通过四重循环的枚举找出所有符合条件的子矩阵。
2. 再一看数据范围，四重循环包爆的，那么想怎么缩小这个循环次数呢？
   既然枚举子矩阵的两个顶点行不通，那么枚举子矩阵的两条边行不行？
3. **先看宽怎么枚举？**可以想到通过求出每一列的前缀和，然后通过双重循环枚举即可，这个枚举的长度就是宽，又由于是前缀和可以通过O(1) 来求出这之间的总和；
4. **然后再看长度怎么枚举？**首先确定这个长度的枚举是在宽度已经确定的条件下枚举的，也就是说在枚举的时候，长和宽只有一个值在变；那么可以通过双指针的方式枚举长度范围，右指针每次向前加1，然后左指针根据矩阵的大小来改变；那么数量的计算就是左右指针之间的差值。

对于蓝桥杯来说暴力拿分还是挺重要的

70分

// 二维前缀和#include <iostream>
using namespace std;const int N = 510;
typedef long long ll;
int n,m,kk,a[N][N],b[N][N];int main()
{cin>>n>>m>>kk;for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin>>a[i][j];for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];} }   int res = 0;for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {for(int k = i;k <= n;k++) {for(int h = j;h <= m;h ++) {if(b[k][h] - b[k][j-1] - b[i-1][h] + b[i-1][j-1] <= kk) {res ++;} else {break;}}}}}cout<<res<<endl;return 0;
}

Accepted

// 列前缀和 ＋ 双指针#include <iostream>
using namespace std;const int N = 510;
typedef long long ll;
int n,m,kk,a[N][N],b[N][N];int main()
{cin>>n>>m>>kk;for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) {cin>>a[i][j];b[i][j] = b[i-1][j] + a[i][j];  // 处理 列 前缀和}ll res = 0; // 要开long longfor(int i = 1;i <= n;i++) {for(int j = i;j <= n;j++) { // 前两层循环 枚举矩阵的宽for(int l = 1,r = 1,sum = 0;r <= m;r++) {   // 通过双指针枚举矩阵的长sum += b[j][r] - b[i-1][r];     // 先斩后奏  先加里面后面再判断while(sum > kk) {sum -= b[j][l] - b[i-1][l];    // 从前面缩短矩阵的长l++;}res += r-l+1;           // 因为这时候矩阵的宽是确定的，那么只需要判断有多少种长度是满足的即可}}}cout<<res<<endl;return 0;
}

备注

想要一起备赛的小伙伴可以私信加我的联系方式！