P8783统计子矩阵

P8783统计子矩阵

题目

传送门

分析

双指针:二维滑动窗口
与上篇P638逛画展右相同之处，逛画展为一维滑动窗口，本题为二维滑动窗口：左右、上下。可以选择固定左右或者上下边界，以固定左右边界为例：（代码里也列出了以上下为边界的部分）

固定住左右边界：
移动上下边界：下边界向下移动，直到矩阵之和>k时，上边界向下追，
直到重新<=k时，再重复以上操作。始终保持矩阵内之和<=k，将结果累加

如何求出区域内之和？

黄色矩阵 = 左上角到黄色区域 - 左上角到绿色区域 - 左上角到橙色区域 + 左上角到灰色区域（因为在减绿、橙区域时灰色区域被减了两次，需要加回来）使用getSum()计算。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int n,m,k,a[N][N],pre[N][N];
long long ans=0;

int getSum(int x1,int y1,int x2,int y2){
	return pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
}

int main(){
	cin>>n>>m>>k;
	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++){
			pre[i][j] = pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+a[i][j];
		}
	}
	
	//固定左右边界
	for(int L = 1;L<=m;L++){
		for(int R = L;R<=m;R++){
			
			//上下边界
			int U = 1,D = 1;
			
			while(1){
				//终止条件：下边界到底了，终止本次循环。此时进入左右边界的下一循环
				if(D>n)break;
				
				while(U<=D && getSum(U,L,D,R)>k){//如果区域之和>k，上边界追一下
					U++;
				}
				//如果还满足<=k，则答案+1，且下边界继续走，
				if(U<=D)ans+=D-U+1;
				D++;
				
			}
			
		}
	}
	
//	//固定上下边界：
//	//当区域之和>k时：L++，左边界追一下
//	//<=k时：代表当前区域满足条件，累加结果。D++，D继续往下走
//	for(int U = 1;U <= n;U++){
//		for(int D = U;D <= n;D++){
//			int L = 1,R = 1;
//			
//			while(1){
//				//循环终止条件
//				if(R>m)break;
//				while(L<=R && getSum(U,L,D,R)>k){//区域和>k时
//					L++;//追一下
//				}
//				
//				//R继续前进
//				if(L<=R)ans+=R-L+1;
//				R++;
//				
//			}
//			
//		}
//	}
	cout<<ans;
	return 0;
}