蓝桥备赛——矩阵读入

这篇具有很好参考价值的文章主要介绍了蓝桥备赛——矩阵读入。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述 

蓝桥备赛——矩阵读入,数据结构,矩阵,线性代数

蓝桥备赛——矩阵读入,数据结构,矩阵,线性代数

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

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

二维列表推导式

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),因为有三层嵌套循环分别遍历行、列和子矩阵。

 文章来源地址https://www.toymoban.com/news/detail-844668.html

到了这里,关于蓝桥备赛——矩阵读入的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构-矩阵】矩阵的相关公式推导

    设数组元素长度为 L。 1.1 一维数组 数组下标从 0 开始( A[0]–A[n] ,一共 n+1 个),假设当前下标为 A[i] : 第几个 = i + 1 存储地址 = 首地址 + (第几个-1) * L = A[0] 地址 + i * L 数组下标从 1 开始( A[1]–A[n] ,一共 n 个),假设当前下标为 A[i] : 第几个 = i 存储地址 = 首地址 + (第

    2023年04月22日
    浏览(50)
  • 数据结构——稀疏矩阵

    在矩阵中,若数据为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵;与之相反的叫做稠密矩阵。 将棋盘看作一个二维数组,在棋子落盘时,要记录该棋子落下的坐标,其他坐标的值不做记录,默认为0。由于记录很多无意义的数据

    2024年02月03日
    浏览(41)
  • 【数据结构】邻接矩阵法

    顶点用一维数组Vex表示,其中可存放较为复杂的信息(如下标),边表用二维数组Edge表示,存放边的信息(两顶点之间有直接相连的边为1,否则为0)。  如何求顶点的入度 、出度? 对于无向图  第 i 个节点的度: 该结点所在行列的非0元素个数 对于有向图  第i个节点的

    2024年02月12日
    浏览(60)
  • 【开卷数据结构 】稀疏矩阵

    🌺稀疏矩阵 🍁矩阵与稀疏矩阵的定义 🌺稀疏矩阵的转置 🍁详细思路 🍀思路一 🍀思路二 🌺稀疏矩阵的乘法 🍁详细思路 Q:什么是矩阵 A: 数学上,一个 矩阵 由 m 行 n 列的元素组成,是一个 m 行,n 列的表,m 和 n 是矩阵的 维度 。一般地,写作 mxn(读作“m乘n”)来指

    2024年01月19日
    浏览(42)
  • 数据结构--矩阵

    第七话  数据结构之特殊矩阵 文章目录 一、了解什么是数组 二、数组的基本特征 三、上下三角矩阵 1.上三角矩阵 2.下三角矩阵 3.实现运用 四、稀疏矩阵 五、总结 数组和广义表,可看成是线性表的扩展。即线性表中的数据元素既可以是单个元素,也可以是一个线性结构。数

    2024年02月16日
    浏览(36)
  • 数据结构-矩阵

    介绍 数据结构中的矩阵主要涉及以下几种: 对称矩阵:若矩阵A n*n中的元素特点是a[ij]=a[ji],则称之为n阶对称矩阵。对称矩阵的每一对元素占用一个存储单元,那么对于n阶矩阵,可以压缩到n(n+1)/2个元素的存储单元。 对角矩阵:对角矩阵是指矩阵中的非0元素都集中在以主对

    2024年02月01日
    浏览(33)
  • 重学数据结构——矩阵

    【矩阵】   梦回线代(滑稽) 将二维矩阵按行放到一个一维矩阵中,其中下标k和i,j的关系为: K=n*(i-1)+j-1                             例:A85=S7+j-1=n*7+5-1=7n+4 【矩阵-课堂习题】 例、数组A中,每个元素的长度为3字节,行下标i从1到8,列下标j从1到10,从首地址

    2024年02月11日
    浏览(29)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(57)
  • 【数据结构】矩阵的压缩存储

    5.1 普通矩阵的存储 用二维数组存储 分为行优先和列优先: 行优先:优先存放一行的数据。 列优先:优先存放一列的数据。 注意下标是从0还是1开始的! 5.2 对称矩阵的存储 对称矩阵定义 若n阶方阵中任意一个元素 a i , j a_{i,j} a i , j ​ 都有 a i , j = a j , i a_{i,j}=a_{j,i} a i , j

    2024年03月18日
    浏览(57)
  • [数据结构] 数组与特殊矩阵

    偷懒,先写了数组,队列要画图,所以今天就先不写了 数组是由n个相同类型的数据元素构成的有限序列。每个数据元素被称为 一个数组元素 ,每个元素在n个线性关系中的序号称为该元素的 下标 ,下标的取值范围称为数组的 维界 。 数组与线性表的关系:数组是线性表的

    2024年02月19日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包