预计3月5日 Wednesday 前完成
【2025年3月1日，记】题目太简单了，3月3日前完成
蓝桥杯速成刷题清单（上）
https://www.lanqiao.cn/problems/1216/learning/?problem_list_id=30&page=1
替换题号1216
目录
- 进度
- 题解和碎碎念
- 1. 排序
- 题面
- 小结
- ac代码
- 2. 走迷宫
- 题面
- 小结
- ac代码
- 3. 小明的背包1
- 题面
- 小结
- ac代码
- 4. 蓝桥公园
- 题面
- 小结
- ac代码
- 5. 回文判定
- 题面
- 小结
- ac代码
- 题
- 题面
- 小结
- ac代码
- 题
- 题面
- 小结
- ac代码
- 题
- 题面
- 小结
- ac代码
- 题
- 题面
- 小结
- ac代码
进度
题解和碎碎念
1. 排序
题面
太容易，快排内置的 sorted()
小结
ac代码
import os
import sys
# 请在此输入您的代码
N = int(input())
line = sys.stdin.readline().strip()
ls = list(map(int, line.split()))
sorted1 = sorted(ls)
sorted2 = sorted(ls, key= lambda x:-x)
print(" ".join(map(str, sorted1)))
print(" ".join(map(str, sorted2)))
2. 走迷宫
题面
太 ez，就一个 DFS，用内置的 queue
小结
python 内置 queue 用法简介
import queue
q = queue.Queue()
q.put((x, y, cnt)) # 放入
(x, y, cnt) = q.get() # 取出
if q.empty(): # 判断是否为空
pass
python 内置集合 set() 用法
visited = set()
visited.add((x, y))
if (x, y) in visited:
pass
visited.discard((x, y)) # 从集合中删除元素，若不存在，不报错
removed = visited.pop() # 随机删一个，并返回，为空时报错
visited.clear() # 清空整个集合
if len(visited) == 0:
print("Visited is empty")
ac代码
import os
import sys
import queue
# 请在此输入您的代码
line = sys.stdin.readline().strip()
N, M = map(int, line.split())
matrix = []
for _ in range(N):
line = sys.stdin.readline().strip()
ls = list(map(int, line.split()))
matrix.append(ls)
line = sys.stdin.readline().strip()
xin, yin, xout, yout = map(int, line.split())
xin -= 1
yin -= 1
xout -= 1
yout -= 1
moves = [[-1, 0], [0, -1], [1, 0], [0, 1]]
q = queue.Queue()
q.put((xin, yin, 0))
visited = set()
success = False
while not q.empty() and not success:
# print(queue.popleft())
(x, y, cnt) = q.get()
# print(f'x= {x}, y= {y}, cnt= {cnt}')
for move in moves:
x1 = x + move[0]
y1 = y + move[1]
if x1 < 0 or x1 >= N or y1 < 0 or y1 >= M or matrix[x1][y1] != 1 or (x1, y1) in visited:
pass
else:
if x1 == xout and y1 == yout:
print(cnt + 1)
success = True
break
else:
q.put((x1, y1, cnt + 1))
visited.add((x1, y1))
if not success:
print("-1")
3. 小明的背包1
题面
太 ez，最最最基础的 01 背包（当然，我不会啦~
小结
这篇讲的好好（虽然我只学了最基础的 01 背包，难的以后我遇到再学，一定会学的
背包问题详解（01背包，完全背包，多重背包，分组背包）
用二维 dp 记录，核心代码如下
# dp[m][n] 考虑m件物品，在空间不超过n时最大收益
dp = [[0 for _ in range(V + 1)] for _ in range(N + 1)]
for j in range(1, V + 1):
for i in range(1, N + 1):
dp[i][j] = dp[i - 1][j]
if item[i - 1][0] <= j:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i - 1][0]] + item[i - 1][1])
有两个易错点：
- 那个 dp 初始化，我最开始不是用的两个 range，后一个是直接 * 。结果就遇到了 python 的 生成多个对同一行列表的引用，而不是独立的列表，这会导致修改其中任何一行时，其他行也会受到影响 debug 好一会…
- 忘记了 if 前面那个初始化，wa 了一半测试点…
ac代码
import sys
line = sys.stdin.readline().strip()
N, V = map(int, line.split())
item = []
for _ in range(N):
line = sys.stdin.readline().strip()
w, v = map(int, line.split())
item.append([w, v])
# dp[m][n] 考虑m件物品，在空间不超过n时最大收益
dp = [[0 for _ in range(V + 1)] for _ in range(N + 1)]
for j in range(1, V + 1):
for i in range(1, N + 1):
dp[i][j] = dp[i - 1][j]
if item[i - 1][0] <= j:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i - 1][0]] + item[i - 1][1])
print(dp[N][V])
4. 蓝桥公园
题面
ez，Floyd 模板题，骂骂咧咧，什么破题，故意卡 python 是吧
小结
多源最短通路 Floyd 算法——3个循环，通过中心点更新
# i：中间点，j k：起点 终点
# idx2content：记录路径
for i in range(1, N + 1):
for j in range(1, N + 1):
for k in range(1, N + 1):
if dist[j][k] > dist[j][i] + dist[i][k]:
dist[j][k] = dist[j][i] + dist[i][k]
dist[k][j] = dist[j][k]
idx2content[j][k] = i
idx2content[k][j] = i
补充 单源最短路径 Dijkstra算法
讲的很好
补充 最小生成树
# 这个代码不对哈
# 最小不是从 dist_new，应该是 visited 里有的点到外界的最小
idx2content = [float('inf') for _ in range(N + 1)]
while len(visited) != N:
dist_new = copy.deepcopy(dist[new])
while True:
min_value = min(dist_new)
min_idx = dist_new.index(min_value)
if min_idx not in visited:
idx2content[new] = min_idx
new = min_idx
visited.add(min_idx)
dist_new[min_idx] = float('inf')
ps. 笑死了，最开始把最小生成树当成 Floyd 交了，还过了一些数据点
ac代码
略
5. 回文判定
题面
秒了
小结
ac代码
import sys
line = sys.stdin.readline().strip()
if line == line[::-1]:
print("Y")
else:
print("N")
