PYTHON LESSON 110
真题精讲：消息传播与征文查重
用“对象-关系-问题”三要素法拆解两道七级风格类真题，固化 BFS 距离表与 LCS 的解题套路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 三要素读题：对象、关系、问题
- BFS 距离表同时回答最远与不可达
- LCS 两行滚动：相等左上 +1，不等取上左
01 · 核心概念
认出故事外衣下的图遍历与 DP
认出故事外衣下的图遍历与 DP：任何故事题都按三问拆解：对象是谁（顶点/序列）、关系是什么（边/比较规则）、问题求什么（最值/计数）。三问答完，外衣就脱了，剩下的全是本单元学过的裸模型。
GESP Python 7 级 · 图的 BFS 应用GESP Python 7 级 · 最长公共子序列 LCS同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
02 · 语法与规则
先记住这 3 条，再开始写程序
三要素读题：对象、关系、问题先准确读出这条写法的结构与作用。
BFS 距离表同时回答最远与不可达换一组最小数据，手工推演一次结果。
LCS 两行滚动：相等左上 +1，不等取上左再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 真题精讲：两道七级风格类真题
from collections import deque
print("第 1 题：消息传播")
n = 8
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (6, 7)]
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
dist = [-1] * n
dist[0] = 0
q = deque([0])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
reached = [d for d in dist if d != -1]
print("距离表：", dist)
print("传遍需要", max(reached), "分钟")
print("永远收不到的有", dist.count(-1), "人")
print("第 2 题：征文查重（LCS）")
a = "springfestival"
b = "stringfellow"
m = len(b)
prev = [0] * (m + 1)
cur = [0] * (m + 1)
for ca in a:
for j in range(m):
if ca == b[j]:
cur[j + 1] = prev[j] + 1
else:
cur[j + 1] = max(prev[j + 1], cur[j])
prev, cur = cur, prev
print("两篇作文的最长公共子序列长度：", prev[m])第 1 题：消息传播 距离表： [0, 1, 1, 2, 3, 4, -1, -1] 传遍需要 4 分钟 永远收不到的有 2 人 第 2 题：征文查重（LCS） 两篇作文的最长公共子序列长度： 8
两道均为七级风格原创类真题；第 2 题答案 8 对应公共子序列 sringfel（两串中都能按顺序找到）。
04 · 逐步理解
每一步只解决一个问题
- 01
三要素读题法
任何故事题都按三问拆解：对象是谁（顶点/序列）、关系是什么（边/比较规则）、问题求什么（最值/计数）。三问答完，外衣就脱了，剩下的全是本单元学过的裸模型。
- 02
第 1 题：读题
消息每分钟沿好友关系传一层，问传遍要多久、多少人永远收不到。三要素：人是顶点，好友是无向边，问题是最远距离加不可达人数——BFS 距离表的标准面孔。
- 03
第 1 题：破题
一次 BFS 的距离表同时回答两问：max(dist) 是传遍所需分钟数，dist.count(-1) 是收不到的人数。注意 6、7 号自成小圈子，距离表里是两个 -1，这正是“图可能不连通”的考点。
reached = [d for d in dist if d != -1] print(max(reached), dist.count(-1)) - 04
第 2 题：读题
查重系统要找两篇作文“能按顺序对上的最长片段”，允许跳字——这就是 LCS 换了马甲。对象是字符串，关系是“字符相同可配对”，问题是最长公共子序列长度。
- 05
第 2 题：破题
二维 DP：字符相等取左上 +1，不等取上方、左方的较大值。只留 prev、cur 两行滚动更新，空间从 O(nm) 压到 O(m)。springfestival 和 stringfellow 的答案是 8。
if ca == b[j]: cur[j + 1] = prev[j] + 1 else: cur[j + 1] = max(prev[j + 1], cur[j]) - 06
套路总结
七级编程题就两种主流长相：穿故事外衣的图遍历（连通、距离、染色），和穿故事外衣的 DP（两个序列比一比、一堆物品挑一挑、一段区间并一并）。认出马甲、默写模板、验证边界，三步走完就是满分流程。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对两道题的答案
- 2把第 1 题的边 (6, 7) 改成 (5, 6)，先预测再验证
- 3在纸上画出第 1 题逐层传播的过程
- 4给第 2 题换两个单词，先心算 LCS 再运行对照
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查