蓝桥杯-子矩阵

"""
题目来源
https://www.lanqiao.cn/problems/3521/learning/?page=1&first_category_id=1&name=%E5%AD%90%E7%9F%A9%E9%98%B5
"""
import os
import sys
from collections import deque# 请在此输入您的代码
n, m, a, b = map(int, input().split())
datas = []
for i in range(n):datas.append(list(map(int, input().split())))# 记录所有子矩阵区间最大值
def max_value_queue(x):# 记录每一行所有区间长度为b的区间最大值ws = []for i in range(n):nums = datas[i]# w记录当前行所有区间长度为b的区间最大值w = []# 单调队列q = deque()for i, v in enumerate(nums):# 1.入队列while q and v >= nums[q[-1]]:q.pop()q.append(i)# 2.出队列# 单调队列的长度限制为b, 当队列元素个数大于b就需要将队首元素出队if i - q[0] + 1 >= b + 1:q.popleft()# 3.开始记录答案if i >= b - 1:# 单调队列降序, 队首元素为区间最大值w.append(nums[q[0]])ws.append(w)# 记录所有二维区间长度为a宽度为b的区间最大值ans = []# 将ws中的每一列作为一行tmps = [[ws[j][i] for j in range(n)] for i in range(len(ws[0]))]for i in range(len(ws[0])):nums = tmps[i]# w记录当前行所有区间长度为a的区间最大值w = []# 单调队列q = deque()for i, v in enumerate(nums):# 1.入队列while q and v >= nums[q[-1]]:q.pop()q.append(i)# 2.出队列# 单调队列的长度限制为a, 当队列元素个数大于a就需要将队首元素出队if i - q[0] + 1 >= a + 1:q.popleft()# 3.开始记录答案if i >= a - 1:# 单调队列降序, 队首元素为区间最大值w.append(nums[q[0]])ans.append(w)return ans# 记录所有矩阵最小值
def min_value_queue(x):# 记录每一行所有区间长度为b的区间最小值ws = []for i in range(n):nums = datas[i]# w记录当前行所有区间长度为b的区间最小值w = []# 单调队列q = deque()for i, v in enumerate(nums):# 1.入队列while q and v <= nums[q[-1]]:q.pop()q.append(i)# 2.出队列# 单调队列的长度限制为b, 当队列元素个数大于b就需要将队首元素出队if i - q[0] + 1 >= b + 1:q.popleft()# 3.开始记录答案if i >= b - 1:# 单调队列降序, 队首元素为区间最小值w.append(nums[q[0]])ws.append(w)# 记录所有二维区间长度为a宽度为b的区间最小值ans = []# 将ws中的每一列作为一行tmps = [[ws[j][i] for j in range(n)] for i in range(len(ws[0]))]for i in range(len(ws[0])):nums = tmps[i]# w记录当前行所有区间长度为a的区间最小值w = []# 单调队列q = deque()for i, v in enumerate(nums):# 1.入队列while q and v <= nums[q[-1]]:q.pop()q.append(i)# 2.出队列# 单调队列的长度限制为a, 当队列元素个数大于a就需要将队首元素出队if i - q[0] + 1 >= a + 1:q.popleft()# 3.开始记录答案if i >= a - 1:# 单调队列降序, 队首元素为区间最小值w.append(nums[q[0]])ans.append(w)return ans
maxs = max_value_queue(datas)
mins = min_value_queue(datas)answer = 0
for i in range(len(maxs)):for j in range(len(maxs[0])):answer = (answer + maxs[i][j] * mins[i][j]) % 998244353
print(answer)

解题思路:

这个就是二维单调队列的使用, 一维单调队列求区间最值比较简单, 可以去做一下滑动窗口最大值:

https://leetcode.cn/problems/sliding-window-maximum/, 那么二维区间最值怎么求呢？

首先从横向来看，可以用单调队列将每一行的区间最值求出来, 用数组w记录当前行的所有区间最值, 用ws将每一行的w都存储一起。接下来再来纵看，取已经求得的ws二维数组其中一列，求纵向的区间最值, 用t记录当前列的区间最值, 用ts记录每一列的t。最后ts就存储了所有的子矩阵的区间最值。

将区间最大值和区间最小值相乘求和求模就是最终答案, 代码看起来很长, 其实功能比较相似, 两个函数都是求区间最值, 一个是最大一个是最小。