M04133: 垃圾炸弹

matrices, http://cs101.openjudge.cn/pctbook/M04133/

2018年俄罗斯世界杯（2018 FIFA World Cup）开踢啦！为了方便球迷观看比赛，莫斯科街道上很多路口都放置了的直播大屏幕，但是人群散去后总会在这些路口留下一堆垃圾。为此俄罗斯政府决定动用一种最新发明——“垃圾炸弹”。这种“炸弹”利用最先进的量子物理技术，爆炸后产生的冲击波可以完全清除波及范围内的所有垃圾，并且不会产生任何其他不良影响。炸弹爆炸后冲击波是以正方形方式扩散的，炸弹威力（扩散距离）以d给出，表示可以传播d条街道。

例如下图是一个d=1的“垃圾炸弹”爆炸后的波及范围。

假设莫斯科的布局为严格的1025*1025的网格状，由于财政问题市政府只买得起一枚“垃圾炸弹”，希望你帮他们找到合适的投放地点，使得一次清除的垃圾总量最多（假设垃圾数量可以用一个非负整数表示，并且除设置大屏幕的路口以外的地点没有垃圾）。

输入

第一行给出“炸弹”威力d(1 <= d <= 50)。第二行给出一个数组n(1 <= n <= 20)表示设置了大屏幕(有垃圾)的路口数目。接下来n行每行给出三个数字x, y, i, 分别代表路口的坐标(x, y)以及垃圾数量i. 点坐标(x, y)保证是有效的（区间在0到1024之间），同一坐标只会给出一次。

输出

输出能清理垃圾最多的投放点数目，以及能够清除的垃圾总量。

样例输入

样例输出

1 30

将每个垃圾周围区域加上垃圾数量，表示该点炸弹清理数，再遍历矩阵统计最大清理数及其出现次数。

python

'''
遍历方式计算出在每个点投掷炸弹能清理的垃圾数量，并用max_point存储垃圾数量的最大值，
res存储清理垃圾数量最大时的点的数量。最后输出结果。
'''
d = int(input())
n = int(input())
square = [[0]*1025 for _ in range(1025)]
for _ in range(n):
    x, y, k = map(int, input().split())
    #for i in range(x-d if x-d >= 0 else 0, x+d+1 if x+d <= 1024 else 1025):
      #for j in range(y-d if y-d >= 0 else 0, y+d+1 if y+d <= 1024 else 1025):
    for i in range(max(x-d, 0), min(x+d+1, 1025)):
        for j in range(max(y-d, 0), min(y+d+1, 1025)):
          square[i][j] += k

res = max_point = 0
for i in range(0, 1025):
  for j in range(0, 1025):
    if square[i][j] > max_point:
      max_point = square[i][j]
      res = 1
    elif square[i][j] == max_point:
      res += 1
print(res, max_point)

python

d = int(input())
n = int(input())
board = [[0] * 1025 for _ in range(1025)]
for _ in range(n):
    x, y, k = map(int, input().split())
    for i in range(max(0, x - d), min(1025, x + d + 1)):
        for j in range(max(0, y - d), min(1025, y + d + 1)):
            board[i][j] += k
maxk = max(max(l) for l in board)
num = sum(l.count(maxk) for l in board)
print(num, maxk)

python

d = int(input())
n = int(input())
c = {}
for i in range(n):
    x, y, z = map(int,input().split())
    for p in range(max(0, x - d), min(1024, x + d) + 1):
        for q in range(max(0, y - d), min(1024, y + d) + 1):
            c[(p, q)] = c.setdefault((p, q), 0) + z
a = list(c.values())
s = max(a)
print(a.count(s), s)

【夏子涵元培学院】思路：用二维前缀和数组避免多次暴力循环

这是一个典型的“用前缀和优化区域统计”问题，适合练习二维前缀和的应用。

python

def main():
    d = int(input().strip())
    n = int(input().strip())

    # 使用字典存储垃圾点，节省空间（稀疏数据时特别有效）
    moskow = {}
    max_coord = 1024
    min_coord = 0

    for _ in range(n):
        x, y, weight = map(int, input().strip().split())
        if (x, y) not in moskow:
            moskow[(x, y)] = 0
        moskow[(x, y)] += weight

    # 构建二维前缀和数组（只构建 [0..1024] 范围）
    size = max_coord + 1
    prefix = [[0] * (size + 1) for _ in range(size + 1)]  # prefix[0..1024+1][0..1024+1]

    for i in range(1, size + 1):
        for j in range(1, size + 1):
            # 注意：prefix[i][j] 对应坐标 (i-1, j-1)
            val = moskow.get((i - 1, j - 1), 0)
            prefix[i][j] = val + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]

    max_total = 0
    count = 0

    # 遍历所有可能的爆炸中心 (i, j)，范围 [0, 1024]
    for i in range(min_coord, max_coord + 1):
        for j in range(min_coord, max_coord + 1):
            # 计算爆炸影响区域 [x1, x2] × [y1, y2]
            x1 = max(min_coord, i - d)
            y1 = max(min_coord, j - d)
            x2 = min(max_coord, i + d)
            y2 = min(max_coord, j + d)

            # 查询前缀和：注意 prefix 是 1-indexed
            total = prefix[x2 + 1][y2 + 1] \
                    - prefix[x1][y2 + 1] \
                    - prefix[x2 + 1][y1] \
                    + prefix[x1][y1]

            if total > max_total:
                max_total = total
                count = 1
            elif total == max_total:
                count += 1

    print(count, max_total)


if __name__ == '__main__':
    main()

M04133: 垃圾炸弹 ​

M04133: 垃圾炸弹