蓝桥备赛——矩阵读入

题目描述 

如上图所示,是一道有关二维前缀和的问题,因为涉及到二维,肯定就是以矩阵的形式进行读入的。

为此,针对矩阵的读入形式进行总结,可以大致总结出两种类型如下:

二维列表推导式

n, m, k = map(int, input().split())
mat = []
for i in range(n):
    mat.append(list(map(int, input().split())))
pre = [[0 for _ in range(m)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(m):
        pre[i][j] = pre[i - 1][j] + mat[i - 1][j]

 可以看到上面代码的

pre = [[0 for _ in range(m)] for _ in range(n + 1)]

表示的是对于第一个[ ]中的元素是生成一个行向量,对于外面的第二个[ ]表示的是生成多少行的列表。

经过上面的代码,可以获得一个列表为

即获得了一个所有元素都为0的列表。后面再不停地读入元素进行原内容覆盖。

自创的方法

n,m,k=map(int,input().split())
mas=[]
for i in range(n):
    matrix = []
    matrix.extend(map(int,input().split()))
    mas.append(matrix)
print(mas)

 同样是先读入数据,不过需要额外创建一个列表作为中转,将数据读入后,再将其作为整体append到一个新的列表,即可达到上面二维列表推导式的效果。

与上面方法不同的地方是,不需要再重新将元素全部覆盖,所录入列表的即为最终数据。

AC Code

n, m, k = map(int, input().split())
mat = []
for i in range(n):
    mat.append(list(map(int, input().split())))
pre = [[0 for _ in range(m)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(m):
        pre[i][j] = pre[i - 1][j] + mat[i - 1][j]
ans = 0
for i in range(n):
    for j in range(i, n):
        l, r, sum = 0, 0, 0
        while r < m:
            sum += pre[j + 1][r] - pre[i][r]
            while sum > k:
                sum -= pre[j + 1][l] - pre[i][l]
                l += 1
            ans += r - l + 1
            r += 1
print(ans)

现在来解释一下上面的代码

n, m, k = map(int, input().split())
mat = []
for i in range(n):
    mat.append(list(map(int, input().split())))
pre = [[0 for _ in range(m)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(m):
        pre[i][j] = pre[i - 1][j] + mat[i - 1][j]

这块代码的作用就是读入相关数据

ans = 0
for i in range(n):
    for j in range(i, n):
        l, r, sum = 0, 0, 0
        while r < m:
            sum += pre[j + 1][r] - pre[i][r]
            while sum > k:
                sum -= pre[j + 1][l] - pre[i][l]
                l += 1
            ans += r - l + 1
            r += 1
print(ans)

上面代码的作用就是对应:

for i in range(1, n + 1): for j in range(m): pre[i][j] = pre[i - 1][j] + mat[i - 1][j]:计算前缀和矩阵pre。对于pre[i][j],表示原始矩阵中第i-1行(因为前缀和矩阵行数比原始矩阵多了1)以及前j列的元素之和。

ans = 0:初始化变量ans,用于记录满足条件的子矩阵数量。

for i in range(n): for j in range(i, n)::遍历所有可能的子矩阵的上边界i和下边界j

l, r, sum = 0, 0, 0:初始化左边界l、右边界r以及子矩阵元素之和sum

while r < m: sum += pre[j + 1][r] - pre[i][r]:在子矩阵的右边界r小于列数m时,计算子矩阵在当前列的元素之和。

while sum > k: sum -= pre[j + 1][l] - pre[i][l] l += 1:如果子矩阵的元素之和超过了限定值k,则移动左边界l,直到子矩阵的元素之和不再超过k

ans += r - l + 1:更新满足条件的子矩阵数量。

r += 1:向右移动子矩阵的右边界r

print(ans):输出满足条件的子矩阵数量。

该算法的时间复杂度为O(n^3 * m),因为有三层嵌套循环分别遍历行、列和子矩阵。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505529.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一百以内累加(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS #include <stdio.h>int main() {//初始化变量值&#xff1b;int a 2;int result 1;//循环运算&#xff1b;while (a < 100){//加&#xff1b;result a result;//改变变量值&a…

杨伟民:提高中国消费的七张长效王牌

“新冠疫情冲击以来&#xff0c;需求不足&#xff0c;特别是居民消费不足的问题再一次凸显&#xff0c;我觉得一方面是疫情冲击的短期影响&#xff0c;另一方面也是长期的深层次结构性问题并没有得到解决。”3月25日&#xff0c;在中国发展高层论坛2024年年会“全球经济增长趋势…

C++——C++11线程库

目录 一&#xff0c;线程库简介 二&#xff0c;线程库简单使用 2.1 传函数指针 ​编辑 2.2 传lamdba表达式 2.3 简单综合运用 2.4 线程函数参数 三&#xff0c;线程安全问题 3.1 为什么会有这个问题&#xff1f; 3.2 锁 3.2.1 互斥锁 3.2.2 递归锁 3.3 原子操作 3…

基于springboot实现房屋租赁系统项目【项目源码+论文说明】

基于springboot实现房屋租赁系统演示 摘要 社会的发展和科学技术的进步&#xff0c;互联网技术越来越受欢迎。网络计算机的生活方式逐渐受到广大人民群众的喜爱&#xff0c;也逐渐进入了每个用户的使用。互联网具有便利性&#xff0c;速度快&#xff0c;效率高&#xff0c;成本…

网络类型整理

1、点到点 &#xff1a;在一个网段内只能存在&#xff0c;两个物理节点 MA-多路访问 -- 在一个网段内物理节点的数量不限制 MA--- BMA NBMA 2、BMA -- 广播型多路访问 3、NBMA--非广播型多路访问 注&#xff1a;不同网络类型实际为不同的数据链路层技术&#xff1b;由于二…

AI渣土车监测报警摄像机

随着城市建设的不断发展和交通运输的快速增长&#xff0c;渣土车作为建筑行业中不可或缺的运输工具&#xff0c;承担着大量的渣土运输任务。然而&#xff0c;由于渣土车在运输过程中存在超速、违规变道、碾压行人等交通安全问题&#xff0c;给道路交通和行人安全带来了严重的隐…

OrangePi AIpro(香橙派)远程连接,在windows上显示图形化桌面

OrangePi AIpro&#xff08;香橙派&#xff09;远程连接&#xff0c;在windows上显示图形化桌面 一、连接调试串口1、硬件连接&#xff08;1&#xff09;首先需要准备一根 Micro USB接口&#xff08;老安卓线&#xff09;的数据线&#xff08;2&#xff09;将 Micro USB 接口一…

Docker之ruoyi-vue项目部署

文章目录 创建自定义网络安装redis安装mysql发布若依项目--后端使用Dockerfile自定义镜像运行容器 nginx 创建自定义网络 #搭建net-ry局域网&#xff0c;用于部署若依项目 docker network create net-ry --subnet172.68.0.0/16 --gateway172.68.0.1 注意1&#xff1a;关闭宿主…

【uC/OS-III篇】uC/OS-III 创建第一个任务(For STM32)

uC/OS-III 创建第一个任务&#xff08;For STM32&#xff09; 日期&#xff1a;2024-3-30 23:55&#xff0c;结尾总结了今天学习的一些小收获 本博客对应的项目源码工程 源码项目工程 1. 首先定义错误码变量 // 用于使用uC/OS函数时返回错误码 OS_ERR err; 2. 定义任务控制…

非NVIDIA平台下的CUDA的替代方案OpenCL,第一步如何获取PlatformInfo、DeviceInfo

非NVIDIA平台下的CUDA的替代方案OpenCL&#xff0c;第一步如何获取PlatformInfo、DeviceInfo 介绍 当谈到高性能计算&#xff0c;NVIDIA的CUDA框架无疑是一个强大的工具。OpenC&#xff08;Open Computing Language&#xff09;是一个更为通用的解决方案&#xff0c;或者你使用…

MySQL面试必备一之索引

本文首发于公众号&#xff1a;Hunter后端 原文链接&#xff1a;MySQL面试必备一之索引 在面试过程中&#xff0c;会有一些关于 MySQL 索引相关的问题&#xff0c;以下总结了一些&#xff1a; MySQL 的数据存储使用的是什么索引结构B 树的结构是什么样子什么是复合索引、聚簇索…

SVFormer: Semi-supervised Video Transformer for Action Recognition

标题&#xff1a;SVFormer&#xff1a;用于动作识别的半监督视频Transformer 原文链接&#xff1a;https://doi.org/10.48550/arXiv.2211.13222 源码链接&#xff1a;GitHub - ChenHsing/SVFormer 发表&#xff1a;CVPR 摘要 半监督动作识别是一项具有挑战性但至关重要的任…

2024年道路运输企业安全生产管理人员证模拟考试题库及道路运输企业安全生产管理人员理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年道路运输企业安全生产管理人员证模拟考试题库及道路运输企业安全生产管理人员理论考试试题是由安全生产模拟考试一点通提供&#xff0c;道路运输企业安全生产管理人员证模拟考试题库是根据道路运输企业安全生产…

day58 动态规划part15

392. 判断子序列 简单 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"ace"是"abcde&q…

通天星CMSV6 车载定位监控平台 任意文件上传漏洞复现(XVE-2023-23454)

0x01 产品简介 通天星CMSV6车载定位监控平台拥有以位置服务、无线3G/4G视频传输、云存储服务为核心的研发团队,专注于为定位、无线视频终端产品提供平台服务,通天星CMSV6产品覆盖车载录像机、单兵录像机、网络监控摄像机、行驶记录仪等产品的视频综合平台。 0x02 漏洞概述 …

汇编语言第四版-王爽第2章 寄存器

二进制左移四位&#xff0c;相当于四进制左移一位。 debug命令实操&#xff0c;win11不能启动&#xff0c;需要配置文件 Windows64位系统进入debug模式_window10系统64位怎么使用debugger-CSDN博客

DeepL Pro3.1 下载地址及安装教程

DeepL Pro是DeepL公司推出的专业翻译服务。DeepL是一家专注于机器翻译和自然语言处理技术的公司&#xff0c;其翻译引擎被认为在质量和准确性方面表现优秀.DeepL Pro提供了一系列高级功能和服务&#xff0c;以满足专业用户的翻译需求。其中包括&#xff1a; 高质量翻译&#xf…

vue3 视频播放功能整体复盘梳理

回顾工作中对视频的处理&#xff0c;让工作中处理的问题的经验固化成成果&#xff0c;不仅仅是完成任务&#xff0c;还能解答任务的知识点。 遇到的问题 1、如何隐藏下载按钮&#xff1f; video 标签中的controlslist属性是可以用来控制播放器上空间的显示&#xff0c;在原来默…

MySQL数据库高阶语句②

目录 一.子查询与多表查询 1.子查询 2.update子查询 3.多表查询 4.delete子查询 5.exists关键字也用于子查询 6.结果集 二.MySQL视图 1.定义 2.作用场景 3.视图与表的区别与联系 &#xff08;1&#xff09;区别 ①视图是已经编译好的sql语句。而表不是 ②视图没有…

unity 打包安卓错误汇集

Failed to find target with hash string "android-34’ in: D:Pr 他说找不到sdk34level的我用as打开后卸载又重装&#xff0c;最后解决了 我放到Plugins/Android/下面的Java代码没有被编译 这个不知道为什么。我故意把代码写的有问题&#xff0c;会报错那种&#xff…