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

题目描述

给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K。

输入格式

第一行包含三个整数 N, M和 K。

之后 N 行每行包含 M 个整数, 代表矩阵 A。

输出格式

一个整数代表答案。

输入输出样例

输入 #1

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出 #1

19

说明/提示

【样例说明】

满足条件的子矩阵一共有 19，包含:

大小为 1×1 的有 10个。

大小为1×2 的有 3 个。 大小为1×3 的有 2 个。

大小为 1×4 的有 1 个。

大小为 2×1 的有 3 个。

【评测用例规模与约定】

对于30% 的数据, N,M≤20.

对于 70% 的数据, N,M≤100.

对于 100% 的数据, 1≤N,M≤500,0≤Aij​≤1000,1≤K≤2.5×10^8.

蓝桥杯 2022 省赛 B 组 F 题。

80代码 O(n^4)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int qsm(int x,int n)
{int res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cin>>n>>m>>k;fp(i,1,n){fp(j,1,m){cin>>a[i][j];sum[i][j]=sum[i][j-1]+sum[i-1][j]+a[i][j]-sum[i-1][j-1];}}int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int t=i;t<=n;t++){for(int f=j;f<=m;f++){int x=sum[t][f]-sum[i-1][f]-sum[t][j-1]+sum[i-1][j-1];if(x<=k)cnt++;}}}}cout<<cnt<<"\n";return 0;
} 

 100代码O(n^3)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int qsm(int x,int n)
{int res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cin>>n>>m>>k;fp(i,1,n){fp(j,1,m){cin>>a[i][j];sum[i][j]=sum[i-1][j]+a[i][j];}}int cnt=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int s=0;for(int l=1,r=1;r<=m;r++){s+=sum[j][r]-sum[i-1][r];while(s>k){s-=sum[j][l]-sum[i-1][l];l++;}cnt+=r-l+1;}}}cout<<cnt<<"\n";return 0;
}