P8783 [蓝桥杯 2022 省 B] 统计子矩阵

时间:2024-04-06 10:59:30
#include<bits/stdc++.h> using namespace std; long long a[1010][1010]; long long pre[1010][1010]; long long ptr(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() { std::ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,m; long long k; cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j]; } } long long ans=0; //i记录左上角的横坐标 for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++)//j记录右下角的横坐标 { for(int l=1,r=1;l<=m;l++)//l记录左上角的纵坐标,r记录右下角的纵坐标 { while(r<=m&&ptr(i,l,j,r)<=k)//若此时的子矩阵满足条件,右下角的元素继续往右边移动,即纵坐标++ r++; r--;//上面记录的右下角的元素并不满足条件才退出,所以此时回退一格 ans+=r-l+1; } } } cout<<ans; return 0; }