题解 | #【模板】二维差分#

【模板】二维差分

http://www.nowcoder.com/practice/50e1a93989df42efb0b1dec386fb4ccc

思路:创建一个DP数组,把每次操作修改的起始位置,修正的起始位置记录。利用前缀和把要修改位置填上修改值。最后把DP数组和原始列表相叠加。

while True:
    try:
        n, m, q = map(int, input().split())
        l = []
        dp = [[0 for i in range(m + 1)]for j in range(n + 1)]  # dp数组保存操作数值(变动值),不直接作用到原始数据上
        for i in range(n):
            l.append(list(map(int, input().split())))
        for j in range(q):
            x1, y1, x2, y2,k  = map(int, input().split())
            dp[x1][y1] += k  # 起始修改位置
            if x2 < n:
                dp[x2 + 1][y1] -= k  # 对数组修正,使子矩阵外数据不受影响。子矩阵右边修正
            if y2 < m:
                dp[x1][y2 + 1] -= k  # 对数组修正,使子矩阵外数据不受影响。子矩阵下边修正
            if x2 < n and y2 < m:
                dp[x2 + 1][y2 + 1] += k  # 对数组修正,使子矩阵外数据不受影响。子矩阵you下修正(在减右和减下时,右下角方格减掉两次)
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]  # 利用前缀和把dp[i][j]转化成修改值
                l[i - 1][j - 1] += dp[i][j]  # 同时对原数组l[i - 1][j - 1]的值加上dp[i][j]
        for i in l:
            print(' '.join([str(k) for k in i]))
    except:
        break

全部评论
请问为什么是 x2+1 呢?
点赞 回复 分享
发布于 2022-04-27 10:35

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 14:10
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务