PYTHON LESSON 111
模拟冲刺：七级抢分攻略
掌握时间分配、客观题检查法与编程题抢分策略，在限时小练中检验哈希、BFS、数学库三项基本功。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 先易后难：卡住 5 分钟就跳题
- max(counter, key=counter.get) 找票王
- math.ceil(math.log2(n)) 估算二分次数
01 · 核心概念
限时应试策略与三类小题速练
限时应试策略与三类小题速练：以 90 分钟为例：客观题（选择、判断）控制在 25 分钟，两道编程题各 25 分钟，最后留 15 分钟回头检查。总原则是先易后难——任何一题卡住超过 5 分钟，果断跳过，把能拿的分先装进口袋。
GESP Python 7 级 · 哈希表GESP Python 7 级 · 泛洪 flood fillGESP Python 7 级 · 数学库常用函数复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
先易后难：卡住 5 分钟就跳题先准确读出这条写法的结构与作用。
max(counter, key=counter.get) 找票王换一组最小数据，手工推演一次结果。
math.ceil(math.log2(n)) 估算二分次数再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 模拟冲刺：15 分钟小题速练（哈希 / BFS / 数学库）
import math
from collections import deque
# 小题 1（哈希表）：计票，找得票最多的人
votes = ["小明", "小红", "小明", "小刚", "小红", "小明"]
counter = {}
for name in votes:
counter[name] = counter.get(name, 0) + 1
winner = max(counter, key=counter.get)
print("小题1 计票：", counter)
print("小题1 答案：", winner, counter[winner], "票")
# 小题 2（BFS）：迷宫从 S 到 E 的最少步数
maze = [
list("S..."),
list("##.#"),
list("...#"),
list(".#E."),
]
rows, cols = 4, 4
dist = [[-1] * cols for _ in range(rows)]
dist[0][0] = 0
q = deque([(0, 0)])
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1 and maze[nr][nc] != "#":
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
print("小题2 答案：", dist[3][2], "步")
# 小题 3（数学库）：10 万个有序数据，二分最多比较几次
print("小题3 答案：", math.ceil(math.log2(100000)), "次")小题1 计票： {'小明': 3, '小红': 2, '小刚': 1}
小题1 答案： 小明 3 票
小题2 答案： 5 步
小题3 答案： 17 次三题分别对应哈希计数、网格 BFS、数学库 log2；建议先计时独立做，再运行程序对答案。
04 · 逐步理解
每一步只解决一个问题
- 01
时间分配策略
以 90 分钟为例：客观题（选择、判断）控制在 25 分钟，两道编程题各 25 分钟，最后留 15 分钟回头检查。总原则是先易后难——任何一题卡住超过 5 分钟，果断跳过，把能拿的分先装进口袋。
- 02
客观题检查法
选择题把选项代回题干验证，别凭感觉；判断题对“一定”“所有”“任何”这类绝对词格外警惕，找一个反例就能推翻；复杂度题把 n=10 万分别代入 O(n²) 和 O(n log n) 算一遍再下笔。
- 03
编程题抢分策略
先写朴素解保底（LIS 先写 O(n²)、背包先写二维表），提交拿到部分分后再优化冲满分。读题时把数据范围圈出来，它直接决定算法档次。输出格式一个空格都别多别少，样例必须原样跑通。
- 04
小题 1 讲评：哈希计票
counter.get(name, 0) 一行完成登记与累加。找票王用 max(counter, key=counter.get)：key 参数告诉 max 按“值”而不是按“键”比较。并列时返回先遇到的那个，题目若要求字典序最小需额外处理。
winner = max(counter, key=counter.get) - 05
小题 2 讲评：迷宫最短路
网格里的最少步数就是 BFS 逐层扩展。dist 数组身兼访问标记与答案：-1 是未到达，入队时写成上一格加一。答案是 dist[3][2] = 5，可以自己走一遍验证：右右下下下。
dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc)) - 06
小题 3 讲评：log2 估算
二分每比较一次范围减半，10 万减半 16 次还剩 2 个，所以需要 17 次——math.ceil 向上取整正是干这个的。这类“估算次数”的客观题几乎每次考级都出现。
math.ceil(math.log2(100000)) # 17
05 · 练习与检验
自己写出来，才算真正学会
- 1限时 15 分钟独立做完三道小题
- 2对照程序输出批改自己的答案
- 3统计每题用时，找出最慢的一题
- 4把三条考试策略抄进自己的考前清单
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
完成检查