吉安网站推广徽hyhyk1,公司网站模板设计,百度 wordpress react,东莞企业网站制作推广运营题目描述 给定一个 NM 的矩阵 A#xff0c;请你统计有多少个子矩阵 (最小 11, 最大 NM) 满足子矩阵中所有数的和不超过给定的整数 K。 输入格式 第一行包含三个整数 N, M和 K。 之后 N 行每行包含 M 个整数, 代表矩阵 A。 输出格式 一个整数代表答案。 输入输出样例 输入 #1 3… 题目描述 给定一个 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)
#includebits/stdc.h
using namespace std;
#define int long long
#define fp(i,a,b) for(int ia;ib;i)
#define PII pairint,int
const int N1e510;
const int mod1e97;
const double eps1e-5;
typedef double db;
int qsm(int x,int n)
{int res1;while(n){if(n1)resres*x%mod;xx*x%mod;n1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cinnmk;fp(i,1,n){fp(j,1,m){cina[i][j];sum[i][j]sum[i][j-1]sum[i-1][j]a[i][j]-sum[i-1][j-1];}}int cnt0;for(int i1;in;i){for(int j1;jm;j){for(int ti;tn;t){for(int fj;fm;f){int xsum[t][f]-sum[i-1][f]-sum[t][j-1]sum[i-1][j-1];if(xk)cnt;}}}}coutcnt\n;return 0;
} 100代码O(n^3)
#includebits/stdc.h
using namespace std;
#define int long long
#define fp(i,a,b) for(int ia;ib;i)
#define PII pairint,int
const int N1e510;
const int mod1e97;
const double eps1e-5;
typedef double db;
int qsm(int x,int n)
{int res1;while(n){if(n1)resres*x%mod;xx*x%mod;n1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cinnmk;fp(i,1,n){fp(j,1,m){cina[i][j];sum[i][j]sum[i-1][j]a[i][j];}}int cnt0;for(int i1;in;i){for(int ji;jn;j){int s0;for(int l1,r1;rm;r){ssum[j][r]-sum[i-1][r];while(sk){s-sum[j][l]-sum[i-1][l];l;}cntr-l1;}}}coutcnt\n;return 0;
}
