专栏文章

P13889 [蓝桥杯 2023 省 Python A] 子矩阵 题解

iimnotcfz
P13889题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1s5cz
此快照首次捕获于
2025/12/02 11:57
3 个月前
此快照最后确认于
2025/12/02 11:57
3 个月前
查看原文
题目 P13889 难度 普及+/提高 所属比赛 蓝桥杯 2023 作者 imnotcfz

0x00 省流

二维版滑动窗口，感觉能拿来当例题。

0x01 45pts 做法

暴力枚举子矩阵的左上角，然后求子矩阵的价值，时间复杂度 O(nmab)O(nmab)。

0x02 100pts 做法

说到区间最值问题（RMQ），我们可以跑 nn 遍单调队列，求出原矩阵每一行的滑动窗口答案。
Python 代码PYTHON
from collections import deque

q_max = deque()
q_min = deque()
row_max = [[] for _ in range(n)]
row_min = [[] for _ in range(n)]

for i in range(n):
    q_max.clear()
    q_min.clear()
    for j in range(m):
        while len(q_max) and q_max[0] + b <= j:
            q_max.popleft()
        while len(q_max) and A[i][q_max[-1]] <= A[i][j]:
            q_max.pop()

        while len(q_min) and q_min[0] + b <= j:
            q_min.popleft()
        while len(q_min) and A[i][q_min[-1]] >= A[i][j]:
            q_min.pop()

        q_max.append(j)
        q_min.append(j)

        if j >= b - 1:
            row_max[i].append(A[i][q_max[0]])
            row_min[i].append(A[i][q_min[0]])
但是题目要求的是二维的窗口，于是我们同样枚举子矩阵的左上角，然后再用一个循环，求出子矩阵每一行的最值。
Python 代码PYTHON
for i in range(m - b + 1):
    for j in range(n - a + 1):
        matrix_max = 0
        matrix_min = 1145141919810
        for k in range(a):
            matrix_max = max(matrix_max, row_max[j + k][i])
            matrix_min = min(matrix_min, row_min[j + k][i])
        ans += matrix_max * matrix_min
        ans %= 998244353
时间复杂度 O(nm2)O(nm^2)，使用 PyPy3 已经足以通过本题。

0x03 更好的 100pts 做法

说到区间最值问题（RMQ），我们可以枚举子矩阵的左端点 jj，然后跑一遍单调队列，求出左端点为 jj 的每个子矩阵的最值。
时间复杂度不变，因为瓶颈主要在于求出每一行的滑动窗口答案，但效率提高了接近一倍。
PYTHON
from collections import deque

n, m, a, b = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]

ans = 0
# 双端队列
q_max = deque()
q_min = deque()
# 行最值
row_max = [[] for _ in range(n)]
row_min = [[] for _ in range(n)]

for i in range(n):
    # 多测不清空，小心见祖宗
    q_max.clear()
    q_min.clear()
    for j in range(m):
        # 弹出队首过时的元素
        while len(q_max) and q_max[0] + b <= j:
            q_max.popleft()
        # 弹出队尾值不比新元素大的元素
        # 如果一个选手比你小还比你强，那么你可以退役了
        while len(q_max) and A[i][q_max[-1]] <= A[i][j]:
            q_max.pop()
        # 由于原理相通且代码重复，接下来的单调队列不作解释
        while len(q_min) and q_min[0] + b <= j:
            q_min.popleft()
        while len(q_min) and A[i][q_min[-1]] >= A[i][j]:
            q_min.pop()

        q_max.append(j)
        q_min.append(j)
        if j >= b - 1:
            row_max[i].append(A[i][q_max[0]])
            row_min[i].append(A[i][q_min[0]])

for j in range(m - b + 1):
    q_max.clear()
    q_min.clear()
    for i in range(n):
        while len(q_max) and q_max[0] + a <= i:
            q_max.popleft()
        while len(q_max) and row_max[q_max[-1]][j] <= row_max[i][j]:
            q_max.pop()

        while len(q_min) and q_min[0] + a <= i:
            q_min.popleft()
        while len(q_min) and row_min[q_min[-1]][j] >= row_min[i][j]:
            q_min.pop()

        q_max.append(i)
        q_min.append(i)
        if i >= a - 1:
            matrix_max = row_max[q_max[0]][j]
            matrix_min = row_min[q_min[0]][j]
            ans += matrix_max * matrix_min
            ans %= 998244353

print(ans)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...