蓝桥杯22年第十三届省赛-统计子矩阵|一维前缀和加双指针
题目链接：
1.统计子矩阵 - 蓝桥云课 (lanqiao.cn)
蓝桥杯2022年第十三届省赛真题-统计子矩阵 - C语言网 (dotcpp.com)
说明：
涉及到子矩阵的时候，一般就跟前缀和相关，可以降维。
先回顾一下最大子矩阵，回忆一下一维前缀和的模板，枚举列（行也可以，计算前缀和时就算列上的前缀和）的起点和终点，求每行上的元素之和的时候时间优化为O(1)：
最大子段和和最大子矩阵|动态规划-CSDN博客
如果列的起点和终点确定，那么求小于k的子矩阵个数其实就是求第1行到第m行有多少个和小于k的连续子序列。
用l，r表示这个子序列的左右端点，
如果
因为矩阵元素都为正数
1.sum（l，r）<k，那么sum(i,r)<k ; l<=i<=r，合法的新子序列个数就是r-l+1；
2.sum(l,r)>k,那么sum(l,j)>k;r<=j<=m, 当前区间已经大于k了，没必要再继续向下挪动r了，那就移动l
再注意一下自己的错误：
//错误代码，不能加这个判断 ，因为，当t和b都指向一个元素时，这个元素还大于k//s减为0，t移动到b+1位置，并且接下来仍有可能出现小于k的矩阵 //if(t>b) break;/*错误代码，因为此时小于k的矩阵不止一个，而是 b-t+1个即i+1列到j列上，t行到b行的矩阵和小于k，那么，固定t， t到b-1行也小于kt到b-2行也小于k,t到X（t<=X<=b）行都小于k，应该加上t到b的数字个数反过来也一样，b移动到下个位置小于k，将b固定，b行到t行 也是 b-t+1个if(s<=k) {ans++;}*/总结一下：
- 子矩阵问题可能会用前缀和降维
- 求小于某个值的连续子序列的数量时，使用双指针。l和r都起始点开始，移动r指针，序列和小于k时，新答案有r-l+1个；大于k时，移动l指针直到小于k。
代码：
只用前缀和的版本，两层循环控制列的起点和终点，两层循环控制行的起点和终点。会超时。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N =500+10;
int ans = 0;
int k;int mx[N][N]={0};
signed main() {ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);int m,n;cin>>m>>n;cin>>k;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>mx[i][j];mx[i][j]+=mx[i][j-1];}}for(int i=0;i<=n-1;i++){for(int j=i+1;j<=n;j++){for(int t=1;t<=m;t++){int s=0;for(int b=t;b<=m;b++){s+=mx[b][j]-mx[b][i];if(s<=k) ans++;else break;}}}}cout<<ans;return 0;
}加双指针：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N =500+10;
int ans = 0;
int k;int mx[N][N]={0};
signed main() {ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);int m,n;cin>>m>>n;cin>>k;//计算每行上的前缀和 for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>mx[i][j];mx[i][j]+=mx[i][j-1];}}// for(int i=0;i<=n-1;i++){
// for(int j=i+1;j<=n;j++){
//
// 此处 要控制起始行和终点行
// for(int t=1;t<=m;t++){
// int s=0;
// for(int b=t;b<=m;b++){
// s+=mx[b][j]-mx[b][i];
// if(s<=k)
// ans++;
// else break;
// }
// }
//
// }
// }for(int i=0;i<=n-1;i++){for(int j=i+1;j<=n;j++){//t头指针，b尾指针//当和大于k，头指针向右挪动//尾指针最后都要移动for(int t=1,b=1,s=0;t<=m&&b<=m;b++){//int s=0; 应该放在上面初始化为0 s+=mx[b][j]-mx[b][i];while(s>k){s-=mx[t][j]-mx[t][i];t++;} //错误代码，不能加这个判断 ，因为，当t和b都指向一个元素时，这个元素还大于k//s减为0，t移动到b+1位置，并且接下来仍有可能出现小于k的矩阵 //if(t>b) break;/*错误代码，因为此时小于k的矩阵不止一个，而是 b-t+1个即i+1列到j列上，t行到b行的矩阵和小于k，那么，固定t， t到b-1行也小于kt到b-2行也小于k,t到X（t<=X<=b）行都小于k，应该加上t到b的数字个数反过来也一样，b移动到下个位置小于k，将b固定，b行到t行 也是 b-t+1个if(s<=k) {ans++;}*/ans+=b-t+1;}}}cout<<ans;return 0;
}