lqb官方题单-速成刷题清单(上)-python版

预计3月5日 Wednesday 前完成 【2025年3月1日，记】题目太简单了，3月3日前完成

蓝桥杯速成刷题清单（上） .lanqiao /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") 题 题面 小结 ac代码 题 题面 小结 ac代码 题 题面 小结 ac代码 题 题面 小结 ac代码