备战2024年蓝桥杯 -- 每日一题
Python大学A组
试题一：单调栈
试题二：滑动窗口
试题三：子矩阵
试题四：最大子序和
试题一：单调栈
【题目描述】
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1−1。
【输入格式】
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
【输出格式】
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
【数据范围】
1≤N≤105
1≤数列中元素≤109
【输入样例】
5
3 4 2 7 5
【输出样例】
-1 3 -1 2 2【解题思路】
模板题
【Python程序代码】
from collections import *
n = int(input())
a = list(map(int,input().split()))
q,idx = [0]*(n+5),-1
for i in range(n):
if idx>=0:
while idx>=0 and q[idx]>=a[i]:idx-=1
if idx<0:
print(-1,end=' ')
else:
print(q[idx],end=' ')
else:
print(-1,end=' ')
idx += 1
q[idx] = a[i]
试题二：滑动窗口
【题目描述】
给定一个大小为 n≤106 的数组。有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。你只能在窗口中看到 k个数字。每次滑动窗口向右移动一个位置。以下是一个例子：该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
【输入格式】
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n个整数，代表数组的具体数值。
同行数据之间用空格隔开。
【输出格式】
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
【输入样例】
8 3
1 3 -1 -3 5 3 6 7
【输出样例】
-1 -3 -3 -3 3 3
3 3 5 5 6 7【解题思路】
单调队列模板题
【Python程序代码】
from collections import *
n,k = map(int,input().split())
a = [0] + list(map(int,input().split()))
q = deque()
for i in range(1,n+1):
if len(q) and q[0]<i-k+1:q.popleft()
while q and a[i]<a[q[-1]]:q.pop()
q.append(i)
if i>=k-1:print(a[q[0]],end=' ')
print()
q = deque()
for i in range(1,n+1):
if len(q) and q[0]<i-k+1:q.popleft()
while q and a[i]>a[q[-1]]:q.pop()
q.append(i)
if i>=k-1:print(a[q[0]],end=' ')
试题三：子矩阵
【题目描述】
给定一个 n×m（n 行 m列）的矩阵。设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a×b （a 行 b 列）的子矩阵的价值的和。答案可能很大，你只需要输出答案对 998244353 取模后的结果。
【输入格式】
输入的第一行包含四个整数分别表示 n,m,a,b相邻整数之间使用一个空格分隔。
接下来 n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,j。
【输出格式】
输出一行包含一个整数表示答案。
【数据范围】
对于 40%40% 的评测用例，1≤n,m≤100；
对于 70%70% 的评测用例，1≤n,m≤500；
对于所有评测用例，1≤a≤n≤1000，1≤b≤m≤1000，1≤Ai,j≤109。
【输入样例】
2 3 1 2
1 2 3
4 5 6
【输出样例】
58【解题思路】
对行和列分别用单调队列
【Python程序代码】
from collections import *
n,m,a,b = map(int,input().split())
mp,p = [],998244353
for i in range(n):
mp.append(list(map(int,input().split())))
max_arr = [[] for _ in range(n)]
min_arr = [[] for _ in range(n)]
# 对行变换
for i in range(n):
q = deque()
num = mp[i]
for j in range(m):
if q and q[0]<j-b+1:q.popleft()
while q and num[q[-1]]<num[j]:q.pop()
q.append(j)
if j>=b-1:max_arr[i].append(num[q[0]])
q = deque()
num = mp[i]
for j in range(m):
if q and q[0]<j-b+1:q.popleft()
while q and num[q[-1]]>num[j]:q.pop()
q.append(j)
if j>=b-1:min_arr[i].append(num[q[0]])
max_fin,min_fin = [[] for _ in range(n)],[[] for _ in range(n)]
for i in range(len(max_arr[0])):
q = deque()
for j in range(len(max_arr)):
if q and q[0]<j-a+1:q.popleft()
while q and max_arr[q[-1]][i]<max_arr[j][i]: q.pop()
q.append(j)
if j>=a-1:max_fin[j].append(max_arr[q[0]][i])
q = deque()
for j in range(len(max_arr)):
if q and q[0] < j - a + 1: q.popleft()
while q and min_arr[q[-1]][i] > min_arr[j][i]: q.pop()
q.append(j)
if j >= a - 1: min_fin[j].append(min_arr[q[0]][i])
res = 0
for i in range(len(max_fin)):
for j in range(len(min_fin[i])):
res = (res + max_fin[i][j] * min_fin[i][j])%p
print(res)
试题四：最大子序和
【题目描述】
输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
注意： 子序列的长度至少是 11。
【输入格式】
第一行输入两个整数 n,m。
第二行输入 n 个数，代表长度为 n 的整数序列。
同一行数之间用空格隔开。
【输出格式】
输出一个整数，代表该序列的最大子序和。
【数据范围】
1≤n,m≤300000,
保证所有输入和最终结果都在 int 范围内。
【输入样例】
6 4
1 -3 5 1 -2 3
【输出样例】
7【解题思路】
单调队列用一下，首先初始ans应该是数组中最大的一个，其他的情况可以用前缀和+单调队列。
【Python程序代码】
from collections import *
n,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
res = max(a[1:])
for i in range(1,n+1):a[i]+=a[i-1]
q = deque()
q.append(0)
for i in range(1,n):
if q and i-q[0]+1>m:q.popleft()
while q and a[i]<a[q[-1]]:q.pop()
q.append(i)
if i>1:res = max([res,a[i+1]-a[q[0]]])
print(res)
