领地选择

GitHub跳转原题关系图返回列表

构造二维前缀和，O(1) 计算每个 C×C 正方形价值并按行列顺序寻找唯一最优位置。

OJ: luogu

题目 ID: P2004

难度:普及/提高-

标签:二维前缀和枚举python

日期: 2026-07-16 17:48

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

在 N×MN\times M 矩阵中找到价值和最大的 C×CC\times C 正方形，输出左上角坐标。

思路

构造二维前缀和 prefix[i][j]。以 (bottom, right) 为右下角的正方形可用四个前缀值容斥得到。枚举所有右下角，遇到更大值时记录对应左上角。

Python 知识

  • 每读一行就维护 row_sum，无需先保存原矩阵。
  • array("q") 用紧凑 64 位整数保存前缀表，显著小于 Python 整数列表。
  • 多行整数用 map(int, input().split()) 直接迭代，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md。

代码

python
import sys
from itertools import accumulate


input = sys.stdin.buffer.readline
n, m, side = map(int, input().split())
prefix = [[0] * (m + 1)]

for _ in range(n):
    row_prefix = accumulate(map(int, input().split()), initial=0)
    prefix.append([up + left for up, left in zip(prefix[-1], row_prefix)])

answer = float("-inf")
answer_x = answer_y = 1

for x in range(n - side + 1):
    for y in range(m - side + 1):
        total = (prefix[x + side][y + side] - prefix[x][y + side]
                 - prefix[x + side][y] + prefix[x][y])
        if total > answer:
            answer = total
            answer_x, answer_y = x + 1, y + 1

print(answer_x, answer_y)

复杂度

时间复杂度 O(NM)O(NM)，空间复杂度 O(NM)O(NM)。

总结

固定大小子矩形求和时，二维前缀和能让每个候选位置只做常数次运算。