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

题目:P8783 [蓝桥杯 2022 省 B] 统计子矩阵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

代码：（部分解析在代码中）

#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;}