蓝桥杯笔记-2023年第十四届省赛真题-子矩阵

滑动窗口+队列

文章共2,523字 · 阅读需要大约9分钟

一键AI生成摘要，助你高效阅读

问答

m0_64126000

2816人浏览 · 2023-11-10 20:25:56

m0_64126000 · 2023-11-10 20:25:56 发布

题目描述

给定一个 n × m （n 行 m 列）的矩阵。

设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a × b （a 行 b 列）的子矩阵的价值的和。

答案可能很大，你只需要输出答案对 998244353 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 n, m, a, b ，相邻整数之间使用一个空格分隔。

接下来 n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai, j 。

输出格式

输出一行包含一个整数表示答案。

样例输入

复制

2 3 1 2
1 2 3
4 5 6

样例输出

复制

提示

1×2+2×3+4×5+5×6 = 58 。

对于 40% 的评测用例，1 ≤ n, m ≤ 100 ；

对于 70% 的评测用例，1 ≤ n, m ≤ 500 ；

对于所有评测用例，1 ≤ a ≤ n ≤ 1000 1 ≤ b ≤ m ≤ 1000 1 ≤ Ai, j ≤ 109 。

问题重述

在一个n*m的矩阵中，将所有a*b大小的子矩阵的最大值和最小值相乘，它们的结果之和为问题输出。

问题分析

刚开始做看样例还以为是子序列乘积之和，看完解答后才发现题看错了。

1. 暴力法

首先是暴力法，定义i，j遍历该矩阵，通过i，j的移动来找出矩阵所有的子矩阵，每找到一个子矩阵最大值，最小值并将他们相乘，将结果保存，以此类推，将所有子矩阵的结果相加保存并取余得到最终结果。

该算法时间复杂度为O(n*m*a*b)，分别是遍历矩阵O(n*m)下遍历其子矩阵O(a*b)，该时间复杂度不知道能不能完成40%的样例通过。

2.滑动窗口

暴力算法可不可以进行优化呢？我们可以看到，在寻找子矩阵的极值的时候有很多重复查找过程，我们可以不可以将这些重复的过程进行优化呢？这就可以用到我们的滑动窗口的一个算法，在整个列表l，将一确定范围n的子序列结合在一起为一个窗口，怎么让该窗口滑动起来呢，我们可以像队列那样，在通过 i 的遍历过程中，将末端的值l[i-b]进行剔除，在将前端的值l[i]加进来，这样，我们就可以看到该窗口在进行滑动，该算法可以大大减少我们的重复查找。

对于一维列表如此，那么二位列表呢，如果一个a*b的子矩阵整个整个的进行移动改变窗口的值，我们将a个一维的窗口进行滑动，每出去一段，存入一段，我们就检查这两段是否改变的极值，是则更改极值，该极值为该子矩阵的极值。但是，感觉跟暴力法没什么区别，都将子矩阵进行了遍历，只不过是从一块一块的查找极值，一段一段的查找。

为解决这个问题，我们可以通过类似压缩的方式来减少查找量。我们可以先对每一行b列的子矩阵求极大极小值，将极大极小值分别存储为两个二维列表，例如将下面5*5矩阵：

3	5	1	6	1
1	2	4	7	6
9	4	8	4	6
1	3	7	1	3
4	5	8	9	2

要求其3*3的所有子矩阵的极值乘积和，先求一行b列（1*3）的子矩阵极值乘积和，求出两个列表：

最大值maxL
5	6	6
4	7	7
9	8	8
7	7	7
8	9	9

最小值minL
1	1	1
1	2	4
4	4	4
1	1	1
4	5	2

求出来后，我们要求a*b的子矩阵的极值，就相当于求maxL(minL)每一列乘以a行，但是这种求法太麻烦了，我们可以将maxL(minL)旋转过去，得到旋转后的表：

5	4	9	7	8
5	7	8	7	9
6	7	8	7	9

1	1	4	1	4
1	2	4	1	5
1	4	4	1	2

可以直接通过两个循环嵌套以a列*1行直接求出a*b的子矩阵（要绕似了，不会说话了）。得到子极值极值表：

子矩阵最大值表
9	9	9
8	8	9
8	8	9

子矩阵最小值表
1	1	1
1	1	1
1	1	1

最后，将两表一一相乘并求和，得到子矩阵的价值的和。

代码实现

1. 求出单行子矩阵极值

假设我们有一个数组 nums = [3, 9, 7, 4, 5, 8]，并且我们希望找到大小为3的滑动窗口中的最大值。现在让我们来分步执行find_max_number函数：

初始时，空队列my_deque和空列表my_want。

当 i = 0 时：

my_deque: [0] (num[0]=3放入队列中)
my_want: [] (当前窗口未达到大小，无最大值)
当 i = 1 时：

my_deque: [1] (num[1]=9放入队列中，因为9比3大，所以3被移出队列)
my_want: [] (当前窗口未达到大小，无最大值)
当 i = 2 时：

my_deque: [1, 2] (num[2]=7放入队列中，因为7比9小，尾插进去)
my_want: [9] (当前窗口达到大小，最大值为9，加入my_want列表)
当 i = 3 时：

my_deque: [1, 2, 3] (num[3]=4放入队列中，因为4比7小，尾插进去)
my_want: [9, 9] (当前窗口达到大小，最大值为9，加入my_want列表)
当 i = 4 时：

my_deque: [4] (nums[1]=9踢出窗口（i-1>=3)，num[4]=5放入队列中，因为5比4大，4被移出队列)
my_want: [9, 9, 7] (当前窗口达到大小，最大值为7，加入my_want列表)
当 i = 5 时：

my_deque: [5] (num[5]=8放入队列中，因为8比4,5大，4,5被移出队列)
my_want: [9, 9, 7, 8] (当前窗口达到大小，最大值为8，加入my_want列表)
最终，my_want的输出为 [9, 9, 7, 8]。

参考代码

根据蓝桥杯2023年第十四届省赛真题-子矩阵-二维滑动窗口+单调队列-Dotcpp编程社区

from collections import deque


def find_max_number(array,size):
    my_deque = deque()
    my_want = []
    for i in range(len(array)):
        #保证队列第一个为当前滑块最大值
        while my_deque and array[my_deque[-1]] < array[i]:
            my_deque.pop()
        my_deque.append(i)
        #目前滑块把之前的最大值划出去了。
        if my_deque[0] <= i - size:
            my_deque.popleft()
        #i从0到n，如果n或m为3，n为10，那么i在0，1的时候不能构成我们需要的子序列【0】，【0，1】
        #不能成为我们需要的n或m的长度的子序列，必须大于3-1=2的下标时我们的最大值才有意义【0，1，2】。
        #后面依次为【1，2，3】，【2，3，4】。。。【7，8，9】，总计8个。
        if i >= size - 1:
            my_want.append(array[my_deque[0]])
    return my_want


def find_min_number(array,size):
    my_deque = deque()
    my_want = []
    for i in range(len(array)):
        while my_deque and array[my_deque[-1]] > array[i]:
            my_deque.pop()
        my_deque.append(i)
        # 目前滑块把之前的最值划出去了
        if my_deque[0] <= i - size:
            my_deque.popleft()

        if i >= size - 1:
            my_want.append(array[my_deque[0]])
    return my_want
mo = 998244353
ans = 0
n,m,a,b = map(int,input().split())
lis = []
for i in range(n):
    lis.append(list(map(int,input().split())))


max_number = []
min_number = []
for i in range(len(lis)):
    max_number.append(find_max_number(lis[i],b))
    min_number.append(find_min_number(lis[i],b))

#翻转列表，方便对列找极值
trans_max = []
trans_min = []
for i in range(len(max_number[0])):
    trans = []
    for j in range(len(max_number)):
        trans.append(max_number[j][i])
    trans_max.append(trans)
for i in range(len(min_number[0])):
    trans = []
    for j in range(len(min_number)):
        trans.append(min_number[j][i])
    trans_min.append(trans)


maxlie = []
minlie = []
# 按列求二维窗口最大值、最小值
for i in range(len(trans_max)):
    x = find_max_number(trans_max[i],a)
    y = find_min_number(trans_min[i],a)
    maxlie.append(x)
    minlie.append(y)
ans = 0
for i in range(len(maxlie)):
    for j in range(len(maxlie[0])):
        ans += (maxlie[i][j] * minlie[i][j]) % mo
        ans %= mo
print(ans)