返回题解分享
讨论 / 题解分享/ 帖子详情

统计子矩阵(编程题) - 题解

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
//数据结构在这里定义

const int N =1e3+10;
int a[N][N];//原数据 
ll sum[N][N];//求和要ll 
int n,m,k;

//求和函数和ans不开long long只能过70%
ll pre(int x, int y, int i, int j){
	return sum[i][j] - sum[x-1][j] \
	- sum[i][y-1] + sum[x-1][y-1];
}

void solve(){
	cin >> n >> m >> k;
	for(int i = 1; i <=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> a[i][j];
			sum[i][j] = sum[i-1][j] + sum[i][j-1] \
			- sum[i-1][j-1] + a[i][j];
		}
	}
	
	ll ans = 0; 
	for(int up = 1; up<=n;up++){
		for(int down = up; down <=n;down++){
			//上下确定了此时问题压缩为一维 
			//滑动窗口法
			int left = 1,right=1;
			for(;right<=m;right++){
				//right添加元素
				while(pre(up,left,down,right)>k && left <= right){
					//总和不满足条件,收缩left 
					left++; 
				} 
				if(left<=right){
					//合法区间
					//计算sublen 这里是最长子区间大小 
					ans += right - left + 1;
				} 
			} 
		}
	}
	cout << ans << endl;
	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;//多组数据要cin
	//cin >> t;
	t = 1;
	while(t--){
		solve();
	} 
	return 0;//必须加return 0 
}
0 回复 0 转发 0 喜欢 4 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!