【题解】统计子矩阵
2022/7/5 23:23:06
本文主要是介绍【题解】统计子矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
试题 F: 统计子矩阵
时间限制: 1.0s 内存限制: 256.0MB 本题总分:15 分
【问题描述】
给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大
N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
【输入格式】
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数,代表矩阵 A.
【输出格式】
一个整数代表答案。
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
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 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.
30分思路
朴素做法:5重循环暴力求解
70分思路:
预处理二维前缀和,枚举对角线
时间复杂度:O(nnmm(m+1)(n+1)/4)~O(nnnmmm/4);
70分代码
#include<cstdio> #include<iostream> using namespace std; int n,m,k,a[510][510],s[510][510]; int ans,f[510][510]; int get(int x1,int y1,int x2,int y2) { return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; s[i][j]+=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int ii=0;ii<=n-i;ii++) { for(int jj=0;jj<=m-j;jj++) { int x1=i,y1=j,x2=i+ii,y2=j+jj; if(get(x1,y1,x2,y2)<=k) f[i][j]++; } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(f[i][j]) ans+=f[i][j]; } } cout<<ans; return 0; }
100分思路
二维前缀和+枚举上下界 双指针左右查找
时间复杂度O(nnm)
100分AC代码:
#include<cstdio> #include<iostream> using namespace std; int n,m,k,a[510][510],s[510][510]; long long ans,f[510][510]; #define ll long long long long get(int x1,int y1,int x2,int y2) { return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; s[i][j]+=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } } for(int l=1;l<=m;l++) { for(int r=l;r<=m;r++) { int j=1; for(int i=1;i<=n;i++) { while(j<=i&&1ll*get(j,l,i,r)>k) j++; ans+=(i-j+1); } } } /*for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(f[i][j]) ans+=f[i][j]; } }*/ cout<<ans; return 0; }
这篇关于【题解】统计子矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了