当前位置: 首页 > article >正文

【2024.3.19练习】统计子矩阵

题目描述


题目分析

这道题一开始没有思路,使用蛮力枚举的方法时间复杂度为O(N^3M^3),显然超时。

参考题解后学会了化二维问题为一维问题,先使用O(N^2)的复杂度限制子矩阵的高度,再考虑列,这样就将子矩阵的和问题转变为了连续子序列的和问题,显然可以用双指针法减低复杂度。因此总时间复杂度减低为了O(N^2M),看似非常大,但是由于循环体内语句已经十分简短,运行时间可以控制在百毫秒级,不会导致超时。

注意,需要提前使用动态规划的思路算出每列的数字和,不要在循环体内临时计算,否则仍会运行超时。


我的代码

这道题的坑在于虽然K限制在int范围内,但ans的值最大为500^4/2,会超出int范围!因此使用long long存储数据。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll; 
int n;
int m;
int k;
const int max_n = 502;
int A[max_n][max_n];
int sum[max_n][max_n];
int main() {
	//初始化 
	int i = 0;
	int j = 0;
	cin >> n >> m >> k;
	for(i = 0;i <= n + 1;i++){
		for(j = 0;j <= m + 1;j++){
			A[i][j] = 0;
			sum[i][j] = 0;
		}
	}
	for(i = 1;i <= n;i++){
		for(j = 1;j <= m;j++){
			cin>>A[i][j];
			sum[i][j] = sum[i-1][j]+A[i][j];
		}
	}
	//降维操作
	ll ans = 0;
	for(i = 1;i <= n;i++){
		for(j = 1;j <= i;j++){
			//尺取法
			int s = 1;
			int t = 1;
			int flag = 0;
			int sum2 = sum[i][1] - sum[j-1][1];
			for( ;flag == 0; ){
				if(sum2 <= k){
					ans = ans + t - s + 1;
					//cout<<s<<"-"<<t<<":"<<sum2<<endl;
					t++;
					sum2 = sum2 + (sum[i][t] - sum[j-1][t]);
				}
				else{
					if(s == t){
						//cout<<s<<"-"<<t<<":"<<sum2<<endl;
						t++;
						sum2 = sum2 + (sum[i][t] - sum[j-1][t]);
					}else{
						//cout<<s<<"-"<<t<<":"<<sum2<<endl;
						sum2 = sum2 - (sum[i][s] - sum[j-1][s]);
						s++;
					}
				}
				if(t == m + 1){
					flag = 1;
				}	
			}
			//cout<<"ans:"<<ans<<endl;
		}
	}
	//获取答案
	cout<<ans; 
	return 0;
}

http://www.kler.cn/a/274544.html

相关文章:

  • 深度学习试题及答案解析(二)
  • Java模拟多个Mqtt客户端连接Mqtt Broker
  • TCL发布万象分区,再造Mini LED技术天花板
  • Connecting to Oracle 11g Database in Python
  • Loki 微服务模式组件介绍
  • 【开源项目】数字孪生轨道~经典开源项目数字孪生智慧轨道——开源工程及源码
  • FFmpeg-- c++实现:音频流aac和视频流h264封装
  • 机器人离散化阻抗控制
  • 【源码&教程】基于GAN的动漫头像生成系统
  • Word为图表设置图注并在图表清单中自动生成
  • 解决由于历史原因解析tflite失败的问题
  • 一款非常流行的数字音乐工作站软件FL Studio for Mac 21.2.3.3586中文版新功能特色
  • uniapp rich-text组件在苹果手机上最多显示两行样式失效
  • 课时69:流程控制_for循环_for (())案例
  • 10 Internet基本服务(3)
  • VMware的安装和Ubuntu的配置安装
  • 奥特曼剧透GPT-5,将在高级推理功能上实现重大进步
  • Java-Java基础学习(2)-网络编程-TCP-UDP
  • Spring Boot 自动化单元测试类的编写过程
  • LeetCode 热题100 图论专题解析
  • C#,图论与图算法,有向图(Graph)之环(Cycle)判断的颜色算法与源代码
  • WiFi是可以连接网络,但是在Pixel 手机上就连接提示受阻,无法上网-解决方法
  • 大数据面试题 —— HBase
  • [LLM] 大模型基础|预训练|有监督微调SFT | 推理
  • node.js 的常用命令
  • SLAM 求解IPC算法