蓝桥2022c++B组 F 统计子矩阵
最暴力的做法：
#include<iostream>
using namespace std;
int a[505][505]={0};
long long q[505][505]={0};
int main()
{
int n,m,k;
cin>>n>>m>>k;
int i,j,b,c,ans=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
q[i][j]=q[i][j-1]+q[i-1][j]-q[i-1][j-1]+a[i][j];//构建前缀和数组
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)//左上角
{
for(b=i;b<=n;b++)
{
for(c=j;c<=m;c++)//右下角
{
if(q[b][c]-q[i-1][c]-q[b][j-1]+q[i-1][j-1]<=k)
ans++;
}
}
}
}
cout<<ans<<endl;
return 0;
}看了大佬之后的做法：
#include<iostream>
using namespace std;
int a[505][505]={0};
long long q[505][505]={0};
int main()
{
int n,m,k;
cin>>n>>m>>k;
int i,j,b,c,ans=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
q[i][j]=q[i][j-1]+q[i-1][j]-q[i-1][j-1]+a[i][j];//构建前缀和数组
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)//左上角
{
for(b=i;b<=n;b++)
{
c=m;
while(q[b][c]-q[i-1][c]-q[b][j-1]+q[i-1][j-1]>k) c--;
if(c<j) break;
ans+=c-j+1;
}
}
}
cout<<ans<<endl;
return 0;
}