第十四届蓝桥杯第三期模拟赛 【python】（一）：https://developer.aliyun.com/article/1410161
小蓝有一个 n * m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。
现在，这个水域长满了水草，小蓝要清理水草。
每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。
经过一段时间清理后，请问还有多少地方没有被清理过。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
第二行包含一个整数 t ，表示清理的次数。
接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。
输出格式
输出一行包含一个整数，表示没有被清理过的面积。
样例输入
2 3 2 1 1 1 3 1 2 2 2
样例输出
2
样例输入
30 20 2 5 5 10 15 6 7 15 9
样例输出
519
评测用例规模与约定
对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。
🧠思路
感觉这道题也是一样的，和前面的信号覆盖也是类似的，并且数据也不是很大，所以首先就用模拟的穷举也可以很快的写出来，只要把清理过的标为0，其他均为1，之后进行求和即可
所以以下简单的思路还是用一个flag数组表示是否清理过，然后计数所有清理过的草坪，最后总数-清理过的草坪就可以得到未清理过的草坪了。
🖥︎参考代码
w,h = map(int,input().split()) t = int(input()) flag = [[0]*(h+1) for _ in range(w+1)] # flag[i][j]代表是否清理过 cnt = 0 for _ in range(t): r1, c1, r2, c2 = map(int,input().split()) for i in range(r1,r2+1): for j in range(c1,c2+1): if flag[i][j] == 0: flag[i][j] = 1 cnt += 1 # 清理过的草坪+1 print(w*h-cnt) # 剩余未清理的草坪
✨最长滑行（DFS搜索）
❓️问题描述
小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。
如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。
如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。
小蓝不能滑出矩阵所表示的场地。
小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。
输入格式
输入第一行包含两个整数 n, m，用一个空格分隔。
接下来 n 行，每行包含 m 个整数，相邻整数之间用一个空格分隔，依次表示每个位置的高度。
输出格式
输出一行包含一个整数，表示答案。
样例输入
4 5 1 4 6 3 1 11 8 7 3 1 9 4 5 2 1 1 3 2 2 1
样例输出
7
样例说明
滑行的位置一次为 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。
评测用例规模与约定
对于 30 % 评测用例，1 < = n < = 20 , 1 < = m < = 20 1 < = n < = 20, 1 < = m < = 201<=n<=20,1<=m<=20 ，0 < = 高度 < = 100 0 < = 高度 < = 1000<=高度<=100 。
对于所有评测用例，1 < = n < = 100 ， 1 < = m < = 100 ， 0 < = 高度 < = 10000 1 < = n < = 100 ，1 < = m < = 100 ，0 < = 高度 < = 100001<=n<=100，1<=m<=100，0<=高度<=10000 。
🧠思路
这道题实际上就是一道搜索问题，本质上我们还是使用DFS进行求解，我们可以从任意一个点开始搜索，然后最后取最大值就是我们最后的结果。这里我们使用DFS求解，为了加快速度，我们还是使用了记忆化搜索，如果发现已经搜索过了，就直接返回结果即可。
首先简单讲一讲DFS的思路吧，我们会从当前x,y进行不断搜索，然后发现下一个点符合条件，在范围内且严格小于当前点的高度，我们就继续搜索，因为我们要取最长，所以我们要取max，不断取最优的结果，最后都记录到我们的dp数组中
这样在下一次搜索的时候，如果发现当前的dp数组的值已经被记录过了，那我们就直接返回值即可，就不需要那么多花里胡哨的操作，其实这道题可能也叫树形的DFS，有时候还是会出现的，不过思路还是OK的，就是类似于树形一样不断迭代dfs而已，最后就是还要加上这个递归深度的代码，这样保证自己不会出错！！！
🖥︎参考代码
import sys sys.setrecursionlimit(1<<31-1) # 设置最大的递归深度 n,m = map(int,input().split()) a = [] for _ in range(n): a.append(list(map(int,input().split()))) dp = [[-1]*m for _ in range(n)] # 记忆化搜索 f = [(-1,0),(1,0),(0,-1),(0,1)] # 返回从x,y开始的最长距离 def dfs(x,y): if dp[x][y] != -1: return dp[x][y] # 如果说明不为-1，说明已经记录过了，直接返回即可 res = 1 for fx,fy in f: nx,ny = x+fx,y+fy if 0<=nx<n and 0<=ny<m and a[x][y] > a[nx][ny]: # dfs(nx,ny)代表从ny,ny的最长距离 res = max(res,dfs(nx,ny) + 1) # 不断取最优的 dp[x][y] = res # 记录当前值 return dp[x][y] ans = 0 for i in range(n): for j in range(m): ans = max(ans, dfs(i,j)) print(ans)
✨区间最小值（ST表模板题）
❓️问题描述
小蓝有一个序列 a [ 1 ] , a [ 2 ] , … , a [ n ] a[1], a[2], …, a[n]a[1],a[2],…,a[n]。
给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a [ i − k ] , a [ i − k + 1 ] , … , a [ i + k ] a[i-k], a[i-k+1], …, a[i+k]a[i−k],a[i−k+1],…,a[i+k] 这 2k+1 个数中的最小值是多少？
当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数 n。
第二行包含 n 个整数，分别表示 a[1], a[2], …, a[n]。
第三行包含一个整数 k 。
输出格式
输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。
样例输入
5 5 2 7 4 3 1
样例输出
2 2 2 3 3
评测用例规模与约定
对于 30%的评测用例，1 < n < = 1000 , 1 < = a [ i ] < = 1000 1 < n <= 1000,1 <= a[i]
对于60%的评测用例，1 < = n < = 10000 , 1 < = a [ i ] < = 50000 1 <= n <= 10000,1 <= a
对于所有评测用例，1 < = n < = 100000 , 1 < = a [ i ] < = 1000000 1 <= n <= 100000
🧠思路
这道题属于一个模板题，就是需要知道这个ST表的模板，接下来我来介绍一下
RMQ问题
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于一个长度N的数组，在多次询问中，每次都以O(1)的时间得到区间[a, b]的最大值或最小值。
ST ( Sparse Table ) 算法
ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O ( 1 ) O(1)O(1)时间内回答每个查询。其思想就是保存以i为起点的某段数据的最小值。
预处理，用动态规划（DP）解决。思想接近于二路归并排序过程的分治思想。
既然是DP思想，首先要记录每步的状态。
设A [ i ] A[i]A[i]是要求区间最值的数列，F [ i , j ] F[i, j]F[i,j]表示从第i ii个数起连续2 j
个数中的最大值。 这里的F [ i , j ] F[i, j]F[i,j]就是每步的状态。
例如：
A数列为：3 2 4 5 6 8 1 2 9 7
F[1，0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。
同理 : F[1,1] = max(3,2) = 3, F[1，2]=max(3,2,4,5) = 5，F[1，3] = max(3,2,4,5,6,8,1,2) = 8;
状态转移方程
既然有每步的状态了，开始找状态转移方程。
怎么理解呢？
我们可以在看一个图
代码如下：
def RMQ(): t=int(math.log2(length)) # 注意边界，取log2 dp=[[0]*(t+1) for _ in range(length+1)] for i in range(1,length+1): dp[i][0]=data[i] # 初始化 for j in range(1,t+1): for i in range(length-(1<<i)+1): # i + 1<<j - 1 <= n 进行转化 dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]) # 状态转移方程
查询区间
那么查询怎么做呢？毕竟我们存放的都是2次幂个数的最小值。假如查询的区间是奇数个，或不是2次幂个数怎么弄？
其实很简单，就是把头尾分开！
假如我们需要查询的区间为(i,j)，那么我们需要找到小于这个闭区间(左边界取i，右边界取j)的最大幂（可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789)
- 区间的长度为
j - i + 1 - 可以取
t=log2( j - i + 1)区间是1->3 就取log2( 3 - 1 + 1) = 1小于等于区间的最大幂 RMQ(A, i, j)=max{F[i , t], F[ j - 2 ^ t + 1, t]}
所以总结下来，先计算出一个满足2 t < r − l + 1 < 2 t + 1 2^t<r−l+1<2^{t+1}2 <r−l+1<2 的t值，即小于区间长度的2的最高次幂。
显然，区间[ l , l + 2 t − 1 ] [l,l+2^{t-1}][l,l+2
]和[ r − 2 t + 1 , r ] [r-2^{t}+1,r][r−2 +1,r]一定覆盖了区间[l,r]，如下图：
所以知道了所有的方法，直接套用st模板即可
其实还有更简单的，但是可能不能全过，但是我们肯定能拿分，就是直接穷举呗，本身python也有min函数
🖥︎参考代码
ST模板
import math # ST模板 class ST: def __init__(self,data): length = len(data) data = [0] + data # 变成 1-indexing t = int(math.log2(length)) # 取log2 dp=[[float('inf')]*(t+1) for _ in range(length+1)] # 定义DP数组 for i in range(1,length+1): dp[i][0] = data[i] # 初始化 for j in range(1,t+1): for i in range(length-(1<<j)+1 + 1): # i + 1<<j - 1 <= n 进行转化 dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]) # 状态转移方程 self.dp=dp def query(self,L,R): t = int(math.log2(R-L+1)) dp= self.dp return min(dp[L][t],dp[R-(1<<t)+1][t]) n = int(input()) a = list(map(int,input().split())) # 0-indexing k = int(input()) st = ST(a) # 构建st表 for i in range(1,n+1): l = max(1,i-k) r = min(n,i+k) print(st.query(l,r),end=' ')
穷举
我感觉穷举可以拿60%的分
n = int(input()) a = list(map(int,input().split())) k = int(input()) for i in range(n): l = max(0,i-k) r = min(i+k,n-1) print(min(a[l:r+1]),end=' ')
