蓝桥杯倒计时 | 倒计时19天
作者🕵️♂️：让机器理解语言か
专栏🎇：蓝桥杯倒计时冲刺
描述🎨：蓝桥杯冲刺阶段，一定要沉住气，一步一个脚印，胜利就在前方！
寄语💓：🐾没有白走的路，每一步都算数！🐾
目录
题目一：附近最小
思路
代码
题目二：清理水域
思路
代码
题目三：最大连通
思路
代码（官方题解）
代码（优化）
题目一：附近最小
省赛模拟题
问题描述
小蓝有一个序列 a[1],a[2],...,a[n]。给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，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。
对于 50% 的评测用例，1<=n<=10000，1<=a[i]<=10000。
对于所有评测用例，1<=n<=1000000，1<=a[i]<=1000000。
思路：
1、怎么控制修改后的数列不超过[0,n-1]?
答：确定好数列的上下限
修改后的数列下标下限是i-k，且不低于0： start = max(0,i-k)
修改后的数列下标下限是i-k，且不高于n-1：end = min(i+k,n-1)
2、怎么取出数列的最小值？
答：用min()函数，x.append(min(a[start:end+1]))，注意是end+1,因为切片范围是左闭右开区间，用列表x来存每个序号i的最小值。
3、怎么对数列进行时间上的优化，保证代码不超时？
答：因为每次遍历一个数，修改后的数列整体向右移一位，所以当遍历到序号i时，他的数列区间是a[i−k],a[i−k+1],...,a[i+k] ，他的下标下限是a[i-k]，那么a[i-k-1]就在序号i-1的区间下限，序号i和i-1的重叠区间就是a[start:end]，区间i-1比区间i多a[i-k-1]，区间i比区间i-1多a[end]。
①如果a[i-k-1]是序号i-1的区间内的最小值，那我们需要重新计算最小值：x.append(min(a[start:end+1]))
②如果a[i-k-1]不是序号i-1的区间内的最小值，那么区间i-1的最小值就在重叠区间内，所以我们只需要求出重叠区间和a[end]的最小值：x.append(min(x[-1],a[end]))，就可以得到序号i的区间最小值。
注意：我们需要考虑到前一个数的情况，所以我们从序号1开始遍历，列表x的初始化为序号0的区间最小值结果。
代码：
n = int(input())
a = list(map(int,input().split()))
k = int(input())
x = [min(a[0:min(0+k+1,n)])] # 初始化第一个点的最小值
# 遍历n-1个数（从1开始），每次找到一个数的最小值
for i in range(1,n):
start = max(0,i-k) # i-k：修改后的数列下标下限，保证下限不低于0
end = min(i+k,n-1) # i+k：修改后的数列下标上限，保证上限不低于n-1
start2 = max(0,i-k-1) # 起始位置
if a[start2] == x[-1]: # a[i]区间的前一个数就是a[i-1]的最小值
x.append(min(a[start:end+1])) # 取出序列a[i]修改后的最小值
else:
x.append(min(x[-1],a[end])) # 取a[i-1]的最小值和a的最后一个数的最小值
for i in x:
print(i,end=" ")题目二：清理水域
清理水域 -省赛模拟题
问题描述
小蓝有一个 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。
思路：
设置一个列表a来记录清理过的区域，初始化为0，表示没有清理过，然后每次遍历清理区域，将将清理过的区域在a中标记为1，最后统计a中有多少个0，就是未清理过的面积。
小技巧：用二维列表来存清理区间 clear = [list(map(int,input().split())) for _ in range(t)]，注意外面用[ ],里面用list()转为列表
代码：
n,m = map(int,input().split())
t = int(input())
clear = [list(map(int,input().split())) for _ in range(t)] # 二维列表存清理区间
a = [[0 for _ in range(m)] for _ in range(n)] # 初始化为0，表示没有清理过
for i in clear:
# 遍历该清理区域内的每一点
for j in range(i[0]-1,i[2]):
for k in range(i[1]-1,i[3]):
a[j][k] = 1 # 清理过的标记为1
# 求没有清理的面积
sum = 0
for i in range(n):
sum+=a[i].count(0) # 将每一行没有清理的面积累加
print(sum)
题目三：最大连通
最大连通 -省赛模拟题
问题描述
小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。
110010000011111110101001001001101010111011011011101001111110 010000000001010001101100000010010110001111100010101100011110 001011101000100011111111111010000010010101010111001000010100 101100001101011101101011011001000110111111010000000110110000 010101100100010000111000100111100110001110111101010011001011 010011011010011110111101111001001001010111110001101000100011 101001011000110100001101011000000110110110100100110111101011 101111000000101000111001100010110000100110001001000101011001 001110111010001011110000001111100001010101001110011010101110 001010101000110001011111001010111111100110000011011111101010 011111100011001110100101001011110011000101011000100111001011 011010001101011110011011111010111110010100101000110111010110 001110000111100100101110001011101010001100010111110111011011 111100001000001100010110101100111001001111100100110000001101 001110010000000111011110000011000010101000111000000110101101 100100011101011111001101001010011111110010111101000010000111 110010100110101100001101111101010011000110101100000110001010 110101101100001110000100010001001010100010110100100001000011 100100000100001101010101001101000101101000000101111110001010 101101011010101000111110110000110100000010011111111100110010 101111000100000100011000010001011111001010010001010110001010 001010001110101010000100010011101001010101101101010111100101 001111110000101100010111111100000100101010000001011101100001 101011110010000010010110000100001010011111100011011000110010 011110010100011101100101111101000001011100001011010001110011 000101000101000010010010110111000010101111001101100110011100 100011100110011111000110011001111100001110110111001001000111 111011000110001000110111011001011110010010010110101000011111 011110011110110110011011001011010000100100101010110000010011 010011110011100101010101111010001001001111101111101110011101如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。
请问矩阵中最大的连通分块有多大？
思路：
求最大连通块可以用DFS来解决。
遍历地图所有点，对值为1的点做DFS搜索。
DFS：对于值为0的点直接返回（终止条件），对于值为1的点，搜索过后就将该点置为0，表示不能再通过，并将res 设置为1，表示搜索的点加1。接着搜索该点的四个邻居点，继续DFS搜索。每到一点，将四个邻居点可以到达的点累加起来，就是该点的最大连通点。最后在每一点可以到达的最远距离选出最大值，就是最大连通块数。
代码（官方题解）：
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = 30
m = 60
def dfs(x, y):
if g[x][y] == '0': # 该点走不通（终止条件）
return 0
g[x][y] = '0' # 走过了就置为0
res = 1
for i in range(4): # 遍历该点的四个方向
tx = x + dx[i]
ty = y + dy[i]
if tx < 0 or ty < 0 or tx >= n or ty >= m: # 越界（终止条件）
continue
res += dfs(tx, ty) # 不越界则继续搜索，将结果累加起来
return res
g = [list(map(str,input())) for _ in range(n)] # 二维列表存地图(数字连在一起输入，只能转为字符串）
res = 0
for i in range(n):
for j in range(m):
if g[i][j] == '1':
res = max(res, dfs(i, j)) # 在每一点可以到达的最远距离选出最大值
print(res)代码（优化）：
记忆化搜索：将当前位置（x, y ）的最大连通数记录起来，下次再次遇到该点（x, y ）直接返回 jiyi[x][y]。
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = 30
m = 60
jiyi = [[-1] * m for _ in range(n)] # 记忆化搜索：当前位置的最大连通块
def dfs(x, y):
if g[x][y] == '0': # 该点走不通（终止条件）
return 0
if jiyi[x][y] != -1: # 如果被记录过了
return jiyi[x][y] # 直接返回当前位置所能达到的最远距离
g[x][y] = '0' # 走过了就置为0
res = 1
for i in range(4): # 遍历该点的四个方向
tx = x + dx[i]
ty = y + dy[i]
if tx < 0 or ty < 0 or tx >= n or ty >= m: # 越界（终止条件）
continue
res += dfs(tx, ty) # 不越界则继续搜索，将结果累加起来
jiyi[x][y] = res # 记录下当前位置的最大连通块
return res
g = [list(map(str,input())) for _ in range(n)] # 二维列表存地图(数字连在一起输入，只能转为字符串）
res = 0
for i in range(n):
for j in range(m):
if g[i][j] == '1':
res = max(res, dfs(i, j)) # 在每一点可以到达的最远距离选出最大值
print(res)