蓝桥杯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++;}*/

总结一下：

1. 子矩阵问题可能会用前缀和降维
2. 求小于某个值的连续子序列的数量时，使用双指针。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;
}