Python 竞赛语法与算法模板

从零基础到基础算法独立解题

知识讲解 · 手算过程 · 完整例题 · 分层练习 · 模板速查

面向：几乎没有 Python 基础，准备开始算法竞赛或在线刷题的读者。

使用范围：Python 3 的通用语法与标准库。代码采用基础、兼容性较好的写法，不依赖第三方包，不依赖某一届比赛的特殊环境。

编写日期：2026 年 10 月 8 日

阅读说明：先学会，再压缩成模板

这不是一份把 Java 代码逐行换成 Python 的对照表。参考材料《Java 蓝桥杯算法与模板笔记》采用“知识分类讲解＋统一模板区”的组织方式，原文明确不包含基础语法。本书保留它的基础算法、搜索、动态规划和图论主线，按零基础读者的依赖关系重新排序，补入 Python 比赛语法、数据结构操作、例题推演和配套练习。

来源边界。 原笔记提供主题范围和组织参考；Python 的语言说明、所有 Python 代码、教学例子、学习顺序和习题搭配均为本次重新编写或扩展，不能视为原 PDF 的逐字内容。平台习题只给题号、名称、训练目标与提示，不复制完整题面；具体要求以链接中的官方题面为准。Python 接口的核对资料列在附录。原材料页码：第 1–2 页为目录，第 3–29 页为知识梳理，第 29–53 页为模板。

你需要怎样使用这本书

第一次阅读请按顺序进行。每章开头写明先修内容；“选学”表示可以暂时跳过，不影响随后标为基础的主线。看到代码，先预测输出，再运行，再改变一个输入。能解释每个变量是什么，才算看懂模板。

本书把三类内容分开：语法演示用于理解某个写法；自编例题包含明确任务与可核对的答案；平台练习用于自己提交。自编例题不冒充平台原题，书中样例也不冒充官方样例。

“入门、巩固、提高”是本书的教学分层，不是平台官方难度。提高题只组合本章及前面学过的知识；少数格式特殊的题会额外提示。力扣题在第 10 章介绍提交方式后才正式安排。第 1–4 章尚未讲一行多个数，因此主要使用单值输入和自编练习，不提前偷用 map 或 split。

每个算法先回答四个问题：解决什么问题？为什么这个办法成立？变量分别表示什么？什么时候不能用？ 然后再看模板、复杂度与练习。不要把“代码短”误认为“适合入门”。

两条重要约定

默认列表下标从 0 开始。[l, r) 表示包含 l、不包含 r；[l, r] 表示两端都包含。遇到题目使用第 1 个、第 2 个的位置编号，我们会在读入时统一减 1，或明确声明模板采用 1-based。不能把两套编号混用。

本书给的是算法与代码的适用条件，不承诺同一段代码在所有平台、所有数据规模下都能通过。提交前仍需核对题目的时间、内存、Python 解释器、输入格式及空集规则。链接核对仅指题目身份与页面入口，不代表实际登录账号提交或已获得 AC。

学习主线

第 01–10 章：写得出来。认识变量、条件、循环、容器、函数，独立处理输入输出。

第 11–20 章：把题目变成步骤。枚举、排序、哈希、前缀和、差分、双指针、窗口、二分与贪心。

第 21–29 章：组织状态与搜索。栈、队列、堆、数学、递归、回溯、图与网格、并查集。

第 30–35 章：理解动态规划。先写清状态，再写转移，最后考虑空间优化。

第 36–39 章：基础图论及选学结构。Dijkstra、拓扑排序、最小生成树、单调栈与单调队列。

第 40 章与附录：考前检查、练习路线、模板索引、完整程序与资料来源。

第01章 第一个程序、变量与输出

先修：无。 本章目标是看懂一行代码，知道代码、输入、输出分别是什么。

1.1 程序究竟在做什么

程序是一组按规则执行的指令。算法题通常给程序一些输入，让它计算，再输出答案。程序默认从上到下执行；以后学习条件和循环，才能改变执行路线。

编辑器用来写代码；Python 解释器用来执行代码；在线评测系统常简称 OJ，用测试数据检查结果。初学时只需能在一个支持 Python 3 的环境中运行代码。代码文件可保存为 main.py，不要保存为 main.py.txt。在已有 Python 环境的终端中运行 python main.py；具体安装方式以 Python 官方安装说明为准，比赛则优先使用其提供的环境。

下面的程序不需要输入：

print("Hello, Python!")
print(2026)

输出为两行：

Hello, Python!
2026

print 是 Python 提供的功能，作用是输出。圆括号中放要输出的内容。“调用”就是让这个功能执行一次。暂时只需要会使用，自己编写功能要到第 8 章。

引号表示文字；引号本身不会出现在输出中。字符串里的大小写、标点和空格都属于内容。代码中的括号、逗号、引号应使用英文半角符号，不能把 print 写成 Print。

1.2 变量：给一个值起名字

apples = 6
price = 3
cost = apples * price
print(cost)

执行顺序是：把整数 6 交给名字 apples；把 3 交给 price；计算右侧乘法，再把结果 18 交给 cost；输出 18。

= 表示赋值，不是数学中的“永远相等”。程序执行某一行时，先算右边，再更新左边。

x = 5
x = x + 2
print(x)

第二行右边使用旧值 5，计算出 7 后再更新 x，因此输出 7。不是让程序求解方程 x = x + 2。

变量名可以含字母、数字和下划线，但不能以数字开头。优先使用 total、count、left 这样的名字。不要把变量命名为 print、input、list、sum，否则会遮住后面需要使用的内置功能。

1.3 常用的值：整数、小数、文字、真假

12 和 "12" 不同。前者能直接进行数值运算；后者是两个字符。判断条件在第 3 章讲。

print(12 + 3)
print("12" + "3")

输出依次是 15 和 123。字符串的 + 表示连接；数字的 + 表示加法。不要把字符串与整数直接相加。

1.4 输出多个内容、控制空格和换行

x = 3
y = 8
print(x, y)
print(x, y, sep=",")
print(x, end=" ")
print(y)

输出：

3 8
3,8
3 8

逗号分开要输出的多个值；默认中间插入一个空格，最后换行。sep="," 指定值之间用逗号隔开；end=" " 把本次输出末尾的换行改为一个空格。这里 sep 和 end 是 print 已经约定的参数名称，不能任意拼写。

print() 什么都不填，会输出一个空行。"\n" 表示换行符；反斜杠和字母 n 合在一起表示一个换行，而不是普通的两个字符。

print("A\nB")
print("*")
print("***")

# 开始的注释是给人看的说明，不参与计算；但引号里的 # 是普通字符。

# 计算三个盒子一共装多少个球
boxes = 3
balls = 4
print(boxes * balls)  # 这里输出 12

1.5 自编例题与答案

例 1：交换两个数。 已知 a=3、b=8，交换它们后输出。新手先借一个临时变量，不使用尚未讲过的多重赋值。

 a = 3

上面故意展示了一个危险细节：顶层代码前面不应随便多一个空格。真正的完整程序如下：

# 临时变量先保存旧 a
# 不能先写 a = b 再写 b = a，那样两个值都会变成 8
a = 3
b = 8
temp = a
a = b
b = temp
print(a, b)

输出 8 3。执行到 a=b 时，旧的 3 已经存在 temp 中，因此没有丢失。

例 2：输出固定图案。 输出三行星号，数量分别为 1、2、3。本章直接写三次 print，不要求会循环。

print("*")
print("**")
print("***")

自己做。 ① 把上例改成倒三角；② 已知长方形长 7、宽 4，输出面积；③ 预测 x=2; y=x; x=9 依次执行后 y 是多少。第三题答案是 2，因为给整数名字重新赋值不会让另一个名字自动跟着变。

1.6 平台练习

入门｜洛谷 P1000｜超级玛丽游戏
训练重点与提示：练习严格输出固定文本。可以一行一行 print，不需要循环；不要额外输出说明文字。未开始

过关标准： 不看示例，能写出一个包含变量、计算、注释和两行输出的程序。

第02章 数字运算、单值输入与类型转换

先修：第 1 章。 本章仍然只读取“一行一个数”，一行多个数在第 5 章讲。

2.1 把输入变成可计算的数字

text = input()
number = int(text)
print(number + 1)

输入 7，输出 8。input() 读取一整行，返回字符串，不包含末尾的换行。int(text) 将合法的整数字符串转换成整数。两步可以合并为 number = int(input())，因为先执行最里面的 input()，再进行外面的 int()。

n = int(input())
print(n * n)

输入 12，输出 144。在自己的终端运行时，程序停在 input() 等待输入是正常现象，不是卡死。输入数据后按回车。

需要小数时用 float(input())。需要保留文字时用 input()，不要强行转整数。例如学号 "0012" 转为整数后是 12，前面的零会丢失。

str(x) 将值转换成字符串，例如 str(12) 得到 "12"。int("3.5") 会出错，因为它不是整数字符串。int(3.9) 得到 3，int(-3.9) 得到 -3，这是向零截断，和下面的向下取整除法不同。

2.2 七个常用运算符

/ 的结果是浮点数，即使 6 / 3 也得到 2.0。数量、下标和二分中点通常需要 //，不能误用 /。

注意负数：-7 // 3 是 -3，-7 % 3 是 2，因为必须满足 a = (a // b) * b + a % b。当除数为正数时，余数位于 0 到除数减 1 之间。Java 的负数除法和余数习惯不能照搬到这里。

乘方用 **，不是 ^；^ 在第 23 章会作为按位异或介绍。先乘除后加减，不确定就加括号。-3 ** 2 得到 -9，而 (-3) ** 2 得到 9。

x += 1 对数值来说相当于 x = x + 1；还有 -=、*=、//=、%=。Python 不用 x++ 表示加一。

2.3 自编例题 1：把秒数拆成时、分、秒

输入一个非负整数，表示总秒数。输出小时数、剩余分钟数和剩余秒数；小时数可以大于 23，不做日期换算。

seconds = int(input())
hours = seconds // 3600
remaining = seconds % 3600
minutes = remaining // 60
seconds_left = remaining % 60
print(hours, minutes, seconds_left)

输入 3665，输出 1 1 5。先拿走整小时，再把剩余 65 秒分为 1 分和 5 秒。输入 0 时输出 0 0 0。

例 2：拆出一个三位正整数的各位。 百位是 n // 100，十位是 n // 10 % 10，个位是 n % 10。

n = int(input())
hundreds = n // 100
tens = n // 10 % 10
ones = n % 10
print(hundreds + tens + ones)

本例前提是 100 <= n <= 999。输入 507，三个位是 5、0、7，输出 12。不满足“三位正整数”条件时，不应直接拿这个特化写法套用。

2.4 自编例题 3：至少需要多少个盒子

有 n 个物品，每个盒子最多装 k 个。这里输入分为两行，第一行 n，第二行 k，要求 n>=0、k>0。

n = int(input())
k = int(input())
boxes = (n + k - 1) // k
print(boxes)

输入分别为 10 和 3，输出 4；输入 9 和 3，输出 3；输入 0 和 3，输出 0。这是非负整数除法向上取整的常用写法，避免把很大的整数先变成浮点数。

为什么成立？每凑满 k 个需要一盒，不满一盒的尾部也需要占一盒。加上 k-1 后再向下整除，恰好补上这一盒，整除时又不会多算。

2.5 整数很大和小数不精确是两回事

Python 的整数没有 Java int、long 那样固定的位数上限，会随数值增长使用更多内存。但并不意味着大整数运算没有时间和内存代价，也不意味着十进制字符串的转换永远不受限制。

浮点数用有限位表示近似值。不要通过 int(n / k) 计算大整数的商；即使最后转回整数，中间的 / 也可能先丢精度。整数问题尽量全程使用整数。小数输出位数在第 6 章统一讲。

自练： ① 输入四位正整数，求各位和；② 输入非负分钟数，转成小时和分钟；③ 两行输入单价与数量，输出总价。可用输入 1005、125、以及 6/8 检验，答案依次是 6、2 5、48。

过关标准： 能说明 /、//、% 的不同，知道输入为什么需要 int，能手算正整数的拆位。

第03章 条件判断、布尔值与逻辑

先修：第 1–2 章。 本章学习“在不同情况下执行不同的代码”。

3.1 if 和缩进

score = int(input())
if score >= 60:
    print("Pass")
else:
    print("Fail")

if 后面放条件，末尾必须有英文冒号。条件为真就执行其后缩进的代码块；否则执行 else 的代码块。每层通常缩进 4 个空格，同一块缩进必须一致；不要混用空格与制表符。

输入 80 只输出 Pass，输入 59 只输出 Fail。else 不是必须的；只有需要“其他情况”时才写。

3.2 比较与逻辑

== 表示相等，!= 表示不相等，<、<=、>、>= 分别表示小于、小于等于、大于、大于等于。= 是赋值，不能代替 ==。

and 表示两个条件都成立；or 表示至少一个成立；not 表示取反。不要写成 Java/C++ 中的 &&、||、!。

x = int(input())
is_even = x % 2 == 0
in_range = x >= 4 and x <= 12
print(is_even)
print(in_range)
print(is_even and in_range)

输入 6，三行都是 True。如果题目要输出 1 或 0，可以用 int(is_even)；int(True) 为 1，int(False) 为 0。

4 <= x <= 12 是合法的链式比较，等价于上述两个比较用 and 连接。初学不确定优先级时，用括号分开子条件。

and 和 or 会短路：左边已经决定结果时，不再计算右边。下面只有 b 不为 0 才做除法，因此不会除零。

a = int(input())
b = int(input())
if b != 0 and a % b == 0:
    print("divisible")
else:
    print("not divisible or zero divisor")

3.3 多分支与多个独立 if

score = int(input())
if score >= 90:
    print("A")
elif score >= 60:
    print("B")
else:
    print("C")

elif 是“否则再判断”。一个 if/elif/else 链只执行第一个满足条件的分支。因此先检查 90，再检查 60；如果反过来，95 分会提前进入 >=60 分支。

多个独立的 if 则都会各自检查。例如一个数既能被 2 整除又能被 3 整除时，两条独立判断都可能输出。

3.4 自编例题 1：求绝对值

x = int(input())
if x < 0:
    answer = -x
else:
    answer = x
print(answer)

输入 -8，输出 8；输入 0，输出 0。这里每个分支都给 answer 赋值，因此后面能安全使用。若某个分支漏掉赋值，运行到对应输入时就可能报错。

Python 已经有 abs(x)，作用就是取绝对值。先理解上面的分支过程，再可以把核心部分简化为 print(abs(x))。

3.5 自编例题 2：判断能否组成三角形

输入三行正整数边长。三条边能组成非退化三角形，当且仅当任意两边之和都大于第三边。

a = int(input())
b = int(input())
c = int(input())
if a + b > c and a + c > b and b + c > a:
    print("Yes")
else:
    print("No")

输入 3、4、5，输出 Yes；输入 1、2、3，输出 No，因为等于时只能摊成一条线。这里的数学判定条件已在题意中给出，不要求你预先记住。

例 3：四种喜好。 已知两个布尔值 p、q：都成立用 p and q；至少一个成立用 p or q；恰好一个成立用 p != q；都不成立用 not (p or q)。先分别算出两个布尔值，再组合，通常比把所有比较揉成一长行更清楚。

3.6 平台练习

入门｜洛谷 P5712｜【深基3.例4】Apples
训练重点与提示：练习 if/else 和按题意输出单复数。只读一个整数，字符串可以通过 print 的多个参数与 sep 控制格式。未开始

巩固｜洛谷 P5711｜【深基3.例3】闰年判断
训练重点与提示：题面给出了闰年规则。把“整除 4 且不整除 100，或者整除 400”写成逻辑表达式；测试 1900 和 2000。未开始

巩固｜洛谷 P5710｜【深基3.例2】数的性质
训练重点与提示：先保存两个性质的 True/False，再组合四种条件。题目中的范围是“大于 4 且不大于 12”，注意和本章演示中的闭区间不同。未开始

过关标准： 能分清 = 与 ==、独立 if 与 elif；遇到边界等号会主动测试。

第04章 for、while、循环与累积

先修：第 1–3 章。 “重复”是算法最重要的基本动作之一。

4.1 for 和 range：重复确定次数

for i in range(5):
    print(i)

输出 0、1、2、3、4，各占一行。range(5) 按顺序给出从 0 到 4 的整数，不包含 5。每轮循环将当前整数交给 i，再执行缩进的代码。

三个参数依次是起点、终点、步长。终点始终不取；步长不能为 0。需要遍历 1 到 n，要写 range(1, n + 1)。

4.2 自编例题 1：求 1 到 n 的和

n = int(input())
total = 0
for i in range(1, n + 1):
    total += i
print(total)

输入 4，变化过程如下：

total=0 必须放在循环外。如果放在循环里，每轮都会清零，最后只剩 n。输出也在循环外，因此只输出最终答案。

例 2：统计 1 到 n 有多少个偶数。 求和变量保存“总和”，计数变量保存“符合条件的个数”，二者不能混淆。

n = int(input())
count = 0
for i in range(1, n + 1):
    if i % 2 == 0:
        count += 1
print(count)

输入 7，输出 3。现在缩进有两层：先进入循环，再进入条件。

4.3 while：一直重复到条件不成立

x = int(input())
steps = 0
while x > 1:
    x //= 2
    steps += 1
print(steps)

输入 10，x 依次从 10 变 5、2、1，输出 3。和平台题“第几天”不同，本自编例题问的是“做了几次除法”；第一天未操作时不计为一次。

while 在每轮开始前检查条件。一定要确认循环体能改变条件所依赖的状态；忘记更新 x 可能造成无限循环。

4.4 自编例题 3：任意非负整数的各位和

n = int(input())
x = n
total = 0
while x > 0:
    total += x % 10
    x //= 10
print(total)

输入 5072：先取 2，再取 7，再取 0，再取 5，总和 14。x//=10 每次去掉个位。用 x 处理而不是直接改 n，可保留原数。

输入 0 时循环不执行，结果仍是 0，这与“数位和”含义吻合。但如果问“0 有几位”，答案应是 1，不能照搬这里的零次循环计数。算法要看状态的具体含义。

4.5 break、continue 与循环中的顺序

break 立即退出所在的这一层循环；continue 跳过这一轮剩余语句，直接进入下一轮。

# 输出 1 到 10 的奇数
for i in range(1, 11):
    if i % 2 == 0:
        continue
    print(i)

# 查找 1 到 n 中第一个能被 7 整除的数
n = int(input())
answer = -1
for i in range(1, n + 1):
    if i % 7 == 0:
        answer = i
        break
print(answer)

-1 在这个问题中表示“没有找到”，因为合法答案是正整数。哨兵值必须不会与合法答案冲突。循环执行完时，判断答案是否还等于 -1，就能区分是否找到。

在 while 中使用 continue 尤其小心：如果它跳过了更新计数器的语句，可能导致死循环。

4.6 嵌套循环与阶乘

# 输出一个 3 行、4 列的星号矩形
for row in range(3):
    for col in range(4):
        print("*", end="")
    print()

外层每执行一轮，内层完整执行 4 轮，再输出换行。一共输出 12 个星号。

# n! = 1 * 2 * ... * n，约定 0! = 1
n = int(input())
product = 1
for i in range(1, n + 1):
    product *= i
print(product)

累加通常从 0 开始，累乘通常从 1 开始。用 0 初始化乘积会一直得到 0。

4.7 平台练习

入门｜洛谷 P5722｜【深基4.例11】数列求和
训练重点与提示：用累加变量与 range 求数列和。本题明确要求不用求和公式提交；公式 n*(n+1)//2 只用于本地核对循环结果。未开始

巩固｜洛谷 P5720｜【深基4.例4】一尺之棰
训练重点与提示：while 每轮把木棍长度整除 2。注意题目问“第几天”，第一天已经存在，不能直接输出操作次数。未开始

巩固｜洛谷 P1423｜小玉在游泳
训练重点与提示：同时维护累计距离、下一步距离和步数。达到目标就停止；目标为 0 时不需要游泳。未开始

自练： 打印 1 到 n 的平方；输出九九乘法表的数字三角形；求 n! 中“实际计算出的结果”而非取模结果。前两题只需要本章知识，输出排版可以先简单用空格隔开。

第05章 列表、下标、多值输入与二维表

先修：第 1–4 章。 本章是后面所有数组算法的基础，请不要只记一行快读写法。

5.1 列表保存一组数

a = [10, 20, 30]
print(a[0])
print(a[2])
a[1] = 99
print(a)

输出分别是 10、30、[10, 99, 30]。方括号中的逗号分开各个元素。a[0] 表示第一个元素，a[2] 表示第三个元素。列表长度为 3，有效非负下标为 0、1、2，访问 a[3] 会越界。

len(a) 返回元素个数。a[-1] 表示最后一个元素，a[-2] 表示倒数第二个。负下标很方便，但也会掩盖错误：本来想访问前一项却在 i=0 时读到 a[-1]，程序不会报错，却可能算错。

空列表写作 []。a=[0]*5 创建 5 个零；这对整数列表是常用初始化方式。二维列表不能简单照搬，见本章末尾。

5.2 两种遍历与常用方法

a = [6, 2, 9]
for x in a:
    print(x)
for i in range(len(a)):
    print(i, a[i])

第一种只取值；第二种取下标后再访问值。需要改某个位置时用下标。

a = [6, 2, 9]
for i in range(len(a)):
    a[i] += 1
print(a)

输出 [7, 3, 10]。而 for x in a: x += 1 只是改变本轮名字 x 绑定的整数，不会把结果写回列表。

a.append([1,2]) 加入的是一个列表元素，a.extend([1,2]) 加入的是两个整数。方法前面的点表示“对这个对象做该操作”。

5.3 一行多个整数：先拆解，再简写

题目输入一行 3 8。input() 仍然得到字符串 "3 8"，不能直接 int("3 8")。

text = input()
parts = text.split()
a = int(parts[0])
b = int(parts[1])
print(a + b)

split() 按空白把字符串拆成若干段，返回字符串列表。这里得到 ["3", "8"]。连续空格会被统一当作分隔，前后空白也不会产生多余的空项。

要读入一整行整数列表，先写完整过程：

parts = input().split()
a = []
for text in parts:
    value = int(text)
    a.append(value)
print(a)

至此你已经能解很多入门题，不需要先记 map。第 9 章会在完全相同的过程上介绍简写。

读 n 个数。 如果题目说明第一行 n、第二行 n 个数，就先读 n，再读整行。若题目允许它们跨行，应采用第 10 章的跨行读取方式，不能假设一行刚好读完。

5.4 自编例题 1：最大值、最小值、总和

输入第一行 n，第二行 n 个整数，保证 n≥1，所有数在第二行。

n = int(input())
parts = input().split()
a = []
for text in parts:
    a.append(int(text))

largest = a[0]
smallest = a[0]
total = 0
for x in a:
    if x > largest:
        largest = x
    if x < smallest:
        smallest = x
    total += x
print(largest, smallest, total)

输入：

4
-3 -8 -1 -6

输出 -1 -8 -18。最大值不能初始化成 0，因为数组可能全部为负。Python 内置 max(a)、min(a)、sum(a) 分别求最大、最小、总和；现在理解扫描过程后可以使用它们。max([]) 与 min([]) 没有默认答案，会报错；sum([]) 为 0。

5.5 自编例题 2：找第一个目标的下标

a = [7, 4, 9, 4]
target = 4
answer = -1
for i in range(len(a)):
    if a[i] == target:
        answer = i
        break
print(answer)

输出 1。若问“第几个”，才在找到后加 1；没有找到时不能把 -1 加成 0 后混成正常位置。

5.6 复制不是赋值，删除不要边遍历边移动

a = [1, 2, 3]
b = a
b[0] = 99
print(a)

输出 [99, 2, 3]，因为 a 和 b 指向同一个列表。要复制一维整数列表，可以用 b=a.copy()。随后改 b[0] 不再改 a[0]。

过滤数据时优先新建答案列表，不要在遍历原列表时连续 remove，因为下标移动可能跳过元素。

a = [0, 3, 0, 5]
kept = []
for x in a:
    if x != 0:
        kept.append(x)
print(kept)

5.7 二维列表：一张表

grid[r][c] 先取第 r 行，再取这一行第 c 列。行列均从 0 开始。

rows = 2
cols = 3
grid = []
for r in range(rows):
    row = [0] * cols
    grid.append(row)
grid[0][1] = 7
print(grid)

输出 [[0, 7, 0], [0, 0, 0]]。每轮都创建一个新行，互不影响。

不要写 grid=[[0]*cols]*rows。 这会让多个位置引用同一个行列表，修改一行时其他行也跟着变化。第 9 章将给出正确的列表推导式写法。

读取 2 行、每行 3 个数，可以在外层循环中重复“拆分、转整数、追加整行”的过程。遍历表时先写行循环再写列循环，清楚 r 管行、c 管列。

5.8 平台练习

入门｜洛谷 P1001｜A+B Problem
训练重点与提示：按本章拆分步骤读取同一行两个整数，输出和。不要添加“请输入”或“答案是”。未开始

入门｜洛谷 P5703｜【深基2.例5】苹果采购
训练重点与提示：与 A+B 相同的输入处理，改成乘法。未开始

巩固｜洛谷 P5724｜【深基4.习5】求极差
训练重点与提示：先用手写扫描求最大最小值，再用 max/min 重写；比较两种版本的输出。未开始

巩固｜洛谷 P1046｜【NOIP 2005 普及组】陶陶摘苹果
训练重点与提示：读取高度列表，再读可达到高度。逐一判断苹果高度是否不超过“手能到达的高度＋30”。未开始

巩固｜洛谷 P1427｜小鱼的数字游戏
训练重点与提示：末尾的 0 是结束标志，不属于答案。可先弹出最后的 0，再用倒序 range 输出；控制好最后换行。未开始

第06章 字符串、切片、字符处理与格式化

先修：第 1–5 章。 字符串可以看作按顺序排列的字符，但它不能像列表一样原地改某个位置。

6.1 下标和切片：先统一区间语言

s = "python"
print(s[0])
print(s[-1])
print(s[1:4])
print(s[:3])
print(s[3:])
print(s[::-1])

依次输出 p、n、yth、pyt、hon、nohtyp。s[l:r] 取下标从 l 到 r-1 的字符，是左闭右开区间 [l,r)。

完整写法 s[start:stop:step] 与 range 很像。省略左右端点可以表示从头或到尾；s[::-1] 使用步长 -1，得到反序的新字符串。列表也支持同样的切片规则，例如 a[:]=... 会修改原列表，但 b=a[:] 是得到新的浅拷贝。

下标越界会报错，切片超出尾部通常只取到实际结尾。切片会创建新序列，不应在大循环里把长度很长的切片当作没有代价的动作。

s = "cat"
letters = list(s)
letters[0] = "b"
answer = "".join(letters)
print(answer)

输出 bat。list(s) 把字符拆成列表；"".join(letters) 用空字符串作分隔，把字符连回字符串。不能写 s[0]="b"，因为字符串不可变。

6.2 常见字符串方法

"ab" in s 判断子串是否出现。s.find(...) 得到 0 时表示“在开头”，不是没找到，不能把它直接当作是否找到的布尔值。

strip() 在题目要求保留行首、行尾空格时会损坏输入。input() 本身已去掉行末换行，不必习惯性再加 strip()。

6.3 自编例题 1：判断回文

回文就是从左到右与从右到左相同。例如 level 是，hello 不是。本例把所有字符都当作有效字符，区分大小写。

s = input()
if s == s[::-1]:
    print("Yes")
else:
    print("No")

不使用反转切片也能写：

s = input()
ok = True
for i in range(len(s) // 2):
    if s[i] != s[len(s) - 1 - i]:
        ok = False
        break
if ok:
    print("Yes")
else:
    print("No")

长度为 5 时只需比较位置 0/4、1/3，中间位置 2 不用比较。第二种写法预示了第 16 章的相向双指针，但目前只需要循环和下标就能理解。

6.4 自编例题 2：统计单词与连接数字

line = input()
words = line.split()
print(len(words))

输入 one two three，即使中间有连续空格，也得到 3。空行拆分得到空列表，单词数为 0。

大量输出先收集字符串，再一次连接，避免一边循环一边不断增长长字符串。

a = [12, 3, 45]
texts = []
for x in a:
    texts.append(str(x))
print(" ".join(texts))

输出 12 3 45，而不是 [12, 3, 45]。join 的成员必须是字符串，直接 " ".join(a) 会出错。

6.5 字符与编号：ord 和 chr

ord("a") 得到字符的整数编码，chr(97) 得到对应字符 "a"。小写英文字母从 a 到 z 连续排列，因此 ord(ch)-ord("a") 可以映射成 0–25。这里明确限定小写英文字母；不能把这套 26 个位置的公式用于所有语言的文字。

例 3：循环移动字母。 输入一行非负整数 k、下一行小写英文字母串，将每个字母向后移动 k 个位置，超过 z 回到 a。

k = int(input())
s = input()
answer = []
for ch in s:
    index = ord(ch) - ord("a")
    new_index = (index + k) % 26
    answer.append(chr(ord("a") + new_index))
print("".join(answer))

输入 2 与 xyz，输出 zab。字符编号从 23、24、25 变成 25、0、1，取余完成了循环。

6.6 f-string：小数位数、补零和宽度

字符串前加 f，花括号中可以放变量或表达式。

name = "Ada"
score = 95
print(f"{name}: {score}")
x = 10 / 3
print(f"{x:.2f}")
print(f"{7:03d}")
print(f"{7:5d}")

依次输出 Ada: 95、3.33、007、前面四个空格加 7。.2f 表示以小数形式保留两位；03d 表示整数至少占三位、不足补零；5d 表示至少占五位、默认左侧补空格。

格式化只是控制输出形式，不会提高浮点数计算的精确度。要求固定小数位时用格式化，不要误以为 round(x,2) 一定会打印出两位零。round 的舍入规则也不能简单概括成所有十进制数都“四舍五入”。

6.7 平台练习

入门｜洛谷 P5733｜【深基6.例1】自动修正
训练重点与提示：练习 upper；它返回新字符串，直接输出返回值或赋给变量。未开始

巩固｜洛谷 P1307｜【NOIP 2011 普及组】数字反转
训练重点与提示：分离负号，对绝对值的十进制字符串反转，再转成 int 去掉前导零；0 要正常处理。也可以用第 4 章的取余方法。未开始

巩固｜洛谷 P1914｜小书童——凯撒密码
训练重点与提示：用 ord/chr 和取余处理 z 回到 a。先在纸上走一遍靠近 z 的字符。未开始

过关标准： 能解释 s[1:4] 为何只有 3 个字符；能分清字符串反转与原地修改。

第07章 元组、集合与字典

先修：第 1–6 章。 列表回答“第几个”；集合回答“有没有”；字典回答“这个东西对应什么”。

7.1 元组与拆包

元组 tuple 把多个值放在一起，常用于坐标、边、记录。它与列表一样可读下标，但不能原地修改元组的元素。

point = (2, 5)
row = point[0]
col = point[1]
print(row, col)

可以写 row, col = point，这叫拆包：左边两个名字依次接住右边两个值。数量必须匹配。类似地，a,b = 3,8 可以一次赋两个值；a,b = b,a 可以交换值，因为右侧先整体求值。

a = 3
b = 8
a, b = b, a
print(a, b)

只含一个元素的元组必须带逗号，如 (5,)；(5) 只是带括号的整数。元组可保存列表，但不能因此断言其内部数据全部不可变。本书将元组主要用于整数和字符串等不可变值组成的记录。

7.2 集合：去重与判重

seen = set()
seen.add(5)
seen.add(2)
seen.add(5)
print(len(seen))
print(5 in seen)
print(8 in seen)

依次输出 2、True、False。重复加入同一值，只保留一份。空集合写作 set()，不能写 {}，因为 {} 是空字典。

seen.discard(x) 删除 x，不存在时不报错；seen.remove(x) 不存在时会报错。集合没有可依赖的排列顺序，不要以为输出集合就等于按输入顺序或按数值大小输出。

例 1：保留第一次出现的数。

a = [4, 2, 4, 1, 2]
seen = set()
answer = []
for x in a:
    if x not in seen:
        seen.add(x)
        answer.append(x)
print(answer)

输出 [4, 2, 1]。集合负责快速判定有没有见过，列表负责保留顺序。只写 list(set(a)) 无法表达“保留第一次出现的顺序”。

7.3 字典：键对应值

score = {}
score["Alice"] = 90
score["Bob"] = 85
print(score["Alice"])
score["Alice"] = 95
print(score["Alice"])

键是 "Alice"，值是 90 或更新后的 95。同一键再次赋值会覆盖旧值，不会产生两个 Alice。"Alice" in score 判断键是否存在，不是判断值。

读取不存在的键会出现 KeyError。score.get("Cindy",0) 则返回默认值 0，但并不会自动把 Cindy 加到字典里。

例 2：频次统计。

a = [2, 5, 2, 2, 5]
count = {}
for x in a:
    if x not in count:
        count[x] = 0
    count[x] += 1
print(count[2])
print(count[5])

输出 3 和 2。可以把循环内部缩写为 count[x] = count.get(x,0)+1。先取旧次数；没出现过就按 0；再加 1 存回去。

7.4 遍历字典与选择容器

count = {"a": 3, "b": 1}
for key in count:
    print(key, count[key])
for key, value in count.items():
    print(key, value)

items() 提供键和值配对的记录，再用拆包取出。keys() 只看键，values() 只看值。现代 Python 字典保持插入顺序，但这不是“自动按键排序”，不要把它当成有序搜索树。

列表、字典、集合本身是可变的，不能直接作为集合元素或字典键。整数、字符串，以及由可哈希值组成的元组，可以用于键。例如坐标可写 (row,col)，不能直接用 [row,col] 作为键。

例 3：找第一个只出现一次的字符。 先数次数，再按原串顺序扫描。

s = "swiss"
count = {}
for ch in s:
    count[ch] = count.get(ch, 0) + 1
answer = ""
for ch in s:
    if count[ch] == 1:
        answer = ch
        break
print(answer)

输出 w。先数次数与再找第一个是两个不同任务，不要还没统计完就宣布某个字符只出现一次。

本章不强行安排需要新提交接口的平台题。可以先做三道自编题：统计不同数字个数；统计每个小写字符次数；判断两行字符串是否使用完全相同的不同字符。第 10、13 章将接上对应平台练习。

第08章 函数、返回值、作用域与导入

先修：第 1–7 章。 模板通常就是一个解决明确问题的函数。

8.1 定义与调用

def add(a, b):
    result = a + b
    return result

answer = add(3, 5)
print(answer)

def 定义函数；add 是函数名；a,b 是参数，相当于这段计算的输入；return 把结果交回调用者。输出 8。

定义函数时不会立即执行函数体。执行 add(3,5) 才进入函数；参数 a 得到 3、b 得到 5；执行 return 后结束这次调用。调用语句之前，函数定义应当已经被执行。

8.2 return 和 print 不能互相代替

def square(x):
    return x * x

value = square(4)
print(value + 1)

输出 17。函数返回 16，调用者拿着 16 继续计算。

一个只执行 print(x*x) 而不 return 的函数，会把结果写到屏幕，但调用者拿到的是 None，不是平方数。None 表示没有这个值；没有显式 return 的函数默认返回 None。

return 还表示立即结束本次函数。函数里找到了答案时可直接返回，不一定需要先存变量再 break。

def first_position(a, target):
    for i in range(len(a)):
        if a[i] == target:
            return i
    return -1

print(first_position([4, 7, 4], 7))
print(first_position([4, 7, 4], 8))

输出 1 和 -1。最后的 return -1 在循环外，必须等所有位置都检查完才能说没有。

8.3 自编例题：把阶乘封装成函数

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial(0))
print(factorial(5))
print(factorial(7))

输出 1、120、5040。一个函数可以被调用很多次，每次都从自己的参数和局部变量开始。本例参数要求 n 是非负整数。

8.4 作用域与可变参数

函数内定义的普通变量属于这次调用，外面不能随便访问。优先把需要的数据通过参数传入、结果通过 return 传出，不要让模板偷偷依赖很多全局变量。

但是，传入列表时，函数拿到的是同一个列表对象的引用：

def change(a):
    a[0] = 99

nums = [1, 2]
change(nums)
print(nums)

输出 [99, 2]。要保护原列表，可以把 nums.copy() 传入，或在函数内部复制。本书每个可能修改输入的模板会说明这一点。

不要定义 def f(a=[]) 后把它当成每次调用都会新建一个空列表。默认参数是在定义时建立的，可变对象可能被多次调用共享。入门模板尽量不使用可变默认参数。

函数也可以定义在另一个函数内部，供当前任务使用。内部函数可以读取外层变量，也可以修改外层列表的元素；如果要给外层名字直接重新赋值，则涉及 nonlocal，本书的核心回溯模板用参数或列表收集答案，避免你必须先学这一机制。

8.5 import：使用标准库

Python 的标准库是随解释器提供的一组模块，不需要安装第三方包。下面用 gcd 展示导入方式：最大公约数就是能同时整除两个整数的最大正整数，18 和 24 都能被 6 整除，而且没有更大的共同正约数，所以结果是 6。数学算法在第 22 章再展开，这里只需理解调用已经提供的工具。

import math
print(math.gcd(18, 24))

这里先导入 math 模块，再调用其中的 gcd 功能，结果为 6。最大公约数的数学含义和手写方法在第 22 章详细讲，本小段只展示导入语法。

也可以只导入需要的名称：

from math import gcd
print(gcd(18, 24))

导入哪个名字，就采用对应的调用形式。不要写了 from math import gcd 却期待 math 这个模块名自动可用。不要把自己的代码文件命名为 math.py、heapq.py 或 collections.py，以免遮住标准库。

8.6 测试函数与本章练习

assert 条件 表示“我期待这个条件成立”；不成立时会报错。它用于本地测试，不是替代题目的正常输出。

def double(x):
    return x * 2

assert double(0) == 0
assert double(-3) == -6
assert double(7) == 14
print("tests passed")

巩固｜洛谷 P5739｜【深基7.例7】计算阶乘
训练重点与提示：先用本章函数封装循环求阶乘。题面“不使用循环”的挑战留到第 24 章递归后再做，现在不要求完成。未开始

自练： 编写求列表最大值的函数、判断回文的函数、统计目标出现次数的函数。每个函数至少测普通数据、一个元素和题意允许的边界。

第09章 常见简写、排序与可读代码

先修：第 1–8 章。 本章每个简写都有之前的展开版本；不要求把代码压到一行。

9.1 map 为什么经常出现在输入模板里

map(函数,序列) 对序列中的每个元素应用同一个函数，得到一个可以依次取出结果的对象。它不是已经存好全部结果的列表。

a = list(map(int, input().split()))
print(a)

从里往外看：读一行字符串；split 成字符串列表；map 对每一项使用 int；list 把转换后的结果收集成整数列表。这正是第 5 章手工循环的简写。

n, m = map(int, input().split())
print(n + m)

这里不创建 list，而是把两个转换结果拆包到 n、m。前提是这一行恰好有两个值；多一个或少一个都会报错。不要把 n,a = map(...) 误当作“第一个数给 n，剩余所有数给列表 a”。

map 的结果取完就没有了。需要反复使用时先转成 list。

9.2 列表推导式

squares = []
for x in range(1, 6):
    squares.append(x * x)
print(squares)

等价简写：

squares = [x * x for x in range(1, 6)]
print(squares)

带条件的形式 [表达式 for 变量 in 序列 if 条件] 只保留满足条件的结果。例如 [x for x in a if x>0] 得到正数列表。

正确创建二维列表：

rows = 2
cols = 3
grid = [[0] * cols for _ in range(rows)]
print(grid)

_ 只是一个普通变量名，在这里表示“次数要用，但每次取到的编号不重要”。每轮执行 [0]*cols，创建一个独立的新行。

二维复制可写 [row.copy() for row in grid]；本书的二维表保存数字，这样复制每行就足够。仅 grid.copy() 只复制外层，里面的行仍共享。

9.3 enumerate、zip 与输出拆包

a = [8, 3, 6]
for i, x in enumerate(a):
    print(i, x)

enumerate 同时提供下标和值。默认从 0 编号；enumerate(a,1) 从 1 编号，得到的是自定义编号，不再是列表真实下标。

names = ["A", "B"]
scores = [90, 80]
for name, score in zip(names, scores):
    print(name, score)

zip 同时配对两个序列；默认到较短的一个结束。需要一一对应时，先确保长度一致，避免静默丢掉多出的元素。

print(*a) 把列表成员拆成多个 print 参数，输出 8 3 6。这个位置的 * 表示拆包，不是乘法。大量输出也可以使用第 6 章的 join；两者都不应输出列表的方括号。

9.4 sort 与 sorted

a = [5, 2, 8, 2]
b = sorted(a)
print(a)
print(b)
a.sort(reverse=True)
print(a)

sorted(a) 返回新的升序列表，a 不变；a.sort() 修改原列表，本身返回 None；reverse=True 表示降序。不能写 a=a.sort()，否则 a 会变成 None。

字符串按字符顺序比较，数字按数值大小比较。["10","2"] 排序时 "10" 可能在 "2" 前面，因此该转 int 的输入必须先转。

9.5 自定义排序：先普通函数，再 lambda

假设一条记录为 (姓名,分数)，要求分数从高到低，相同分数按姓名从小到大。

students = [("Bob", 90), ("Ada", 95), ("Ann", 90)]

def order_key(item):
    return (-item[1], item[0])

students.sort(key=order_key)
print(students)

输出 [("Ada",95),("Ann",90),("Bob",90)]，实际打印会包含正常空格。key 函数给每条记录产生一个比较用的“标签”。元组按第一项比较，相等再比第二项。负分数把原来的高分转成更小的数，因此用升序就能实现分数降序。

key=order_key 传入的是函数本身，不要写 key=order_key()，后者是立即调用且缺少参数。

同一个简单函数可以简写为 key=lambda item: (-item[1],item[0])。lambda 冒号后只有一个表达式，自动以该表达式作为结果。不熟悉时保留 def 完全可以。

Python 排序是稳定的：比较标签相同时保留原有先后顺序。需要多种混合方向时，用元组逐项表达，不能只加一个 reverse=True 就以为能单独翻转某一项。

9.6 平台练习

入门｜洛谷 P1177｜【模板】排序
训练重点与提示：先用内置 sort 完成排序与输出。此时目标是熟悉输入输出和排序 API，不要求手写快速排序。未开始

巩固｜洛谷 P1059｜【NOIP 2006 普及组】明明的随机数
训练重点与提示：set 去重后 sorted 排序；第一行输出去重后的数量，第二行输出结果。与“保留第一次出现顺序”不是同一要求。未开始

提高｜洛谷 P1093｜【NOIP 2007 普及组】奖学金
训练重点与提示：记录总分、语文分和学号；排序标签为负总分、负语文分、正学号。所有需要的元组和 key 语法已在本章讲过。未开始

第10章 提交方式、输入输出、复杂度与调试

先修：第 1–9 章。 从这一章开始，书中的力扣练习可以直接进入训练。

10.1 两类程序入口不能混写

标准输入输出型。 程序自己读取 input、完成计算、print 答案。很多洛谷题和竞赛题属于这种形式，具体以题面为准。

# 两个整数在同一行
x, y = map(int, input().split())
print(x + y)

函数接口型。 平台已经读取数据，只要求你实现指定函数，并 return 结果。力扣常见如下外壳：

class Solution:
    def sum(self, num1, num2):
        return num1 + num2

class Solution 是平台约定的类名，可以理解成装解法函数的外壳。self 代表当前对象，由平台调用时自动传入；真正的题目参数从 num1 开始。方法名必须按题目提供的名字写，不能随意重命名。不要在函数里再次 input，也不要只 print 而不 return。

你不需要在此学完整面向对象，但必须知道这两层缩进：类内部一层、函数内部再一层。平台给出的 num1: int 或 -> int 是类型标注，用来说明参数、返回值的类型，不是输入转换。保留平台骨架最稳妥；本书常省略非必要标注，避免语法干扰。

10.2 带初始化的力扣设计题

部分题目先构造对象，再多次调用方法，例如数组区间查询。__init__ 是创建对象时执行的初始化方法，名字两边各两个下划线。

class NumberBox:
    def __init__(self, value):
        self.value = value

    def add(self, extra):
        return self.value + extra

box = NumberBox(10)
print(box.add(3))

输出 13。self.value 把数据保存在这个对象里，供后续方法访问。普通局部变量 value 则只属于这次调用。这里的实例演示用于理解接口，第 14 章会把保存的 value 换成前缀和数组。

如果题目要求“原地修改数组，返回新长度”，返回数组本身并不正确。读题时必须分清：返回数值、返回列表、修改原列表、打印文本，是四种不同要求。

10.3 固定多组、直到结束、空行与 EOF

第一行 T 表示有 T 组时，按组循环，而且每组状态重新初始化：

T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    print(a + b)

如果题面没有 T，就不能自己先读一个数当 T。

直到文件结束时，推荐逐行遍历标准输入：

import sys

for line in sys.stdin:
    if line.strip() == "":
        continue
    a, b = map(int, line.split())
    print(a + b)

本例假设每个非空行刚好两个整数，空行不是有效数据。若题面把空行当作字符串内容，就不能跳过。

EOF 表示输入真的结束，不是普通空行。input() 遇到 EOF 会抛出 EOFError；sys.stdin.readline() 在 EOF 返回空字符串，在空行返回 "\n"。

try/except 可捕获指定异常，例如下面只处理 EOF，不能用不加类型的 except 把所有真实错误吞掉：

while True:
    try:
        line = input()
    except EOFError:
        break
    print(line)

10.4 更快的逐行输入与跨行整数

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
print(sum(a))

这里把名字 input 重新绑定到读取一行的方法，是明确、有意的替换。注意它保留行末换行；读取字符串时根据题意用 rstrip("\n")，若可能有 \r\n 行末则去除相应换行，不要误删有效空格。

当题目只按空白分隔所有数字、不在意行的边界时，可以一次读取。if data 是判断列表是否非空。空列表、空字符串、数字 0、None 在条件中为假，其他普通非空容器为真。这里先判断，避免完全没有输入时访问 data[0]。

下面是完整演示：

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
if data:
    n = data[0]
    a = data[1:1 + n]
    print(sum(a))

sys.stdin.buffer 读取原始字节；read() 读取剩余全部内容；字节串的 split 仍能按空白切分；int 可以直接处理表示整数的字节片段。b"abc" 是 bytes，不等于 "abc"；需要普通字符串时使用 .decode()，其默认按 UTF-8 解码。

一次性读取需要同时保存输入缓冲、分割片段及可能的整数列表，内存用量会明显大于原始文件大小。字符串题、需要保留行空格的题、交互题不要套这个模板。大输入且内存紧时优先逐行读取，不能只追求更短。

10.5 输出收集与 main 入口

import sys

def solve():
    input = sys.stdin.readline
    T = int(input())
    answers = []
    for _ in range(T):
        a, b = map(int, input().split())
        answers.append(str(a + b))
    sys.stdout.write("\n".join(answers))

if __name__ == "__main__":
    solve()

solve 封装本题流程。直接执行这个文件时，__name__ 为 "__main__"，于是调用 solve；作为模块导入时不自动读输入。这是代码包完整程序采用的入口，不是每道题必须机械写出的特殊算法。

sys.stdout.write 只接收字符串，不自动增加换行。join 将多行结果拼好再输出，适合较多答案。若 T 巨大，保存全部答案也占内存，可改为适当分批输出。

10.6 复杂度：不要只数代码有几行

时间复杂度描述输入规模增长时，主要操作量怎样增长；空间复杂度描述额外存储怎样增长。n 一般是数组长度，m 常表示边数或列数，使用前要明确。O 表示增长量级，不是具体秒数。

例如 n=100000，两层 n 次循环约有 10^10 次主体操作，通常应立即重新考虑算法；不要盯着“只有两行代码”。n=20 的子集约有一百万个，但每个子集还要复制、检查，实际工作量不只是一百万。

“Python 每秒固定能跑多少次”没有通用保证。解释器、机器、哈希、大整数、函数调用、对象分配都影响常数。数据范围用于排除明显不合理算法，再用实际测试判断临界性能。

10.7 常见操作的代价

列表下标访问 O(1)，末尾 append 为均摊 O(1)，末尾 pop 为 O(1)；从头部 pop(0)、中间插入或删除通常 O(n)。列表 x in a、count、sum、max、min 都需要扫描。排序一般 O(n log n)。长度为 k 的切片通常需要 O(k) 时间和空间。

字典和集合的单次查询、插入、删除平均 O(1)，不是所有情况下绝对最坏 O(1)。字符串哈希、比较和大整数操作还取决于对象长度。本书的简单复杂度以常规大小整数为基本操作，遇到高精度数时要单独考虑位数。

嵌套循环不必然是 O(n²)：如果左右指针各自只前进 n 次，总量可能仍是 O(n)。反过来，一层循环中每次 sum(a[:i])，也可能把总量变成 O(n²)。

10.8 从错误信息定位问题

SyntaxError 常见于漏冒号、括号不配对；IndentationError 是缩进；NameError 是名字未定义；TypeError 是类型或参数不对；ValueError 常见于非法转换或拆包数量不对；IndexError 是下标越界；KeyError 是字典键不存在；RecursionError 是递归过深。

先看报错最后一行和指出的代码位置，不要看到英文就全部重写。WA 表示结果错误，TLE 表示超时，MLE 表示超内存，RE 表示运行异常。能运行不等于结果正确，样例通过也不等于所有数据通过。

提交前至少测：最小合法输入；只有一个元素；全部相同；全负数（允许时）；找不到答案；目标在边界；重复值；空集（题意允许时）。调试 print 必须删除，尤其不能输出“请输入 n”。

10.9 平台练习与第一次综合检查

入门｜力扣 2235｜两整数相加
训练重点与提示：第一次熟悉 class Solution/self/return。不要把 input 和 print 的程序直接粘进方法内部。未开始

入门｜力扣 1929｜数组串联
训练重点与提示：返回两份数组串联的结果。可以用两次遍历 append，也可以用已讲过的列表连接。未开始

巩固｜力扣 217｜存在重复元素
训练重点与提示：用集合判断重复，返回布尔值 True/False。别返回字符串 "True"。未开始

巩固｜洛谷 P4305｜【JLOI2011】不重复数字
训练重点与提示：第一行 T，多组独立数据。集合判重、列表保序、逐组重置，最后空格分隔输出。未开始

阶段验收： 独立完成“一行 n，下一行 n 个整数，输出最大值、去重后数量与原顺序去重结果”的完整程序。能解释所有输入语句、每个容器的用途以及总体复杂度，才进入算法主线。

第11章 枚举与模拟：先写出正确的朴素解法

先修：第 1–10 章。 枚举是逐一尝试可能情况；模拟是按题目的规则逐步改变状态。

11.1 枚举时先确定范围和重复规则

要枚举列表中两个不同位置，可以固定第一个位置 i，再让 j 从 i+1 开始。这样不会选中同一个位置，也不会把 (i,j) 与 (j,i) 重复计算。

自编例题 1：两数和等于 target 的位置对有多少个。 相同数值出现在不同位置，仍然算不同位置对。

代码文件：t11_enumerate_pairs.py

def count_pairs(a, target):
    answer = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == target:
                answer += 1
    return answer

对 a=[1,2,2,3]、target=4，合法下标对为 (0,3)、(1,2)，答案 2。不要用集合去重数值后再算，否则会改变“位置对”的含义。

一共有 n(n-1)/2 对，时间 O(n²)，额外空间 O(1)。输入只有几百个数时，朴素枚举往往适合先验证；输入十万时，就需要第 13 或 16 章的方法。

11.2 枚举连续区间：别额外再求一次和

例 2：小数组里有多少个非空连续区间的和为 k。

代码文件：t11_brute_subarray.py

def count_subarrays_brute(a, k):
    answer = 0
    for left in range(len(a)):
        total = 0
        for right in range(left, len(a)):
            total += a[right]
            if total == k:
                answer += 1
    return answer

固定 left 后，每次右端点只增加一个元素，所以 total 接着累加即可。若在每个区间里再 sum(a[left:right+1])，就可能从 O(n²) 变成 O(n³)。

a=[1,-1,1]、k=1 时，答案为 3：两个单独的 1，以及整个数组。允许负数时，当前和太大也不能随便 break，因为后续负数可能让它降回来。

11.3 模拟先列状态，再列一步的顺序

例 3：存钱过程。 每月先收入 100，再支出预算；剩余的钱中，每完整 50 元就存起来，存款暂时不能拿回。给出三个月预算 [40,80,20]，问是否够用以及最终现金和存款。

budgets = [40, 80, 20]
cash = 0
saved = 0
failed_month = 0
for month in range(len(budgets)):
    cash += 100
    cash -= budgets[month]
    if cash < 0:
        failed_month = month + 1
        break
    deposit = cash // 50 * 50
    cash -= deposit
    saved += deposit
if failed_month != 0:
    print(-failed_month)
else:
    print(cash, saved)

逐月手算：第一月支出后 60，存 50，现金 10；第二月支出后 30，不存；第三月支出后 110，存 100，现金 10。最终输出 10 150。

这道自编题的收入、存款单位与平台储蓄题不同，只用来练状态机。程序中“收入→支出→检查够不够→存入”必须和规则一致。

11.4 自编例题 4：数字出现次数

n, digit = map(int, input().split())
wanted = str(digit)
answer = 0
for value in range(1, n + 1):
    for ch in str(value):
        if ch == wanted:
            answer += 1
print(answer)

输入 13 1，输出 6，来自 1、10、11 中的两个 1、12、13。也可以用 str(value).count(wanted) 替换内层循环；这是已经学过的等价简化，而不是神秘新算法。

11.5 习题与检查

入门｜洛谷 P1428｜小鱼比可爱
训练重点与提示：每条鱼只与左边所有鱼比较，枚举 j<i。注意题目要求严格更小，相等不计。未开始

巩固｜洛谷 P1980｜【NOIP 2013 普及组】计数问题
训练重点与提示：逐个数字、逐位统计；同一个数中出现两次要计两次。可比较字符串版与取余版的结果。未开始

巩固｜洛谷 P1035｜【NOIP 2002 普及组】级数求和
训练重点与提示：维护 n 和调和和，直到严格大于 k；注意不是大于等于。未开始

提高｜洛谷 P1089｜【NOIP 2004 提高组】津津的储蓄计划
训练重点与提示：收入、预算、现金、已存金额分别建变量。首次不足时记录月份；最终利息可利用整百存款用整数运算。未开始

检查口诀： 有没有漏情况？有没有重复？是否把同一个位置选了两次？状态是否每轮正确保留或重置？停止条件是 > 还是 >=？

第12章 排序：建立顺序，再解决问题

先修：第 9–11 章，尤其是 key 和复杂度。 比赛中一般优先使用内置排序；手写排序用于理解过程或题目确有特殊要求。

12.1 为什么排序后更容易处理

排序能让相同元素聚在一起、相邻差值变得有意义，让双指针和二分有机会利用单调性。但排序会改变原顺序。题目要求原下标或子序列顺序时，不能直接 sort 后当作原问题。

例 1：排序后找相邻最小差。 至少两个数，求任意两数差的绝对值最小是多少。

代码文件：t12_min_gap.py

def minimum_gap(a):
    # 前提：至少两个数；不修改调用者的列表
    b = sorted(a)
    answer = b[1] - b[0]
    for i in range(2, len(b)):
        answer = min(answer, b[i] - b[i - 1])
    return answer

[9,1,5,3] 排序后是 [1,3,5,9]，相邻差为 2、2、4，答案 2。为何只看相邻？若两数之间夹着别的数，它们的差等于若干相邻非负差的和，不可能比其中每一段都小。

排序 O(n log n)，扫描 O(n)，总时间 O(n log n)，复制数组需要 O(n) 额外空间。不要把 Python 内置 sort 的辅助空间笼统写成一定 O(1)。

12.2 自编例题 2：保留原位置进行排序

a = [40, 10, 30]
records = []
for i, value in enumerate(a):
    records.append((value, i))
records.sort()
for value, old_index in records:
    print(value, old_index)

输出顺序是 10 1、30 2、40 0。数值改变了位置，但原下标作为记录字段一直保存着。重复值默认再按下标比较；需要不同规则就明确指定 key。

12.3 选学：插入排序帮助理解“已排好部分”

想象把扑克牌逐张插入已经排好的手牌。位置 i 的值暂存为 x，左边比 x 大的元素向右挪，直到找到空位。

代码文件：t12_insertion_sort.py

def insertion_sort(a):
    # 原地修改 a；适合学习过程，不用于大规模常规排序
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x

对 [4,2,3]：先把 2 插到 4 前，成为 [2,4,3]；再把 3 插到 4 前，成为 [2,3,4]。j>=0 必须在访问 a[j] 前判断，利用短路阻止错误边界。

最坏时间 O(n²)，额外空间 O(1)。这段教学实现不替代 sort。下一章的计数排序则适合另一种前提：值域足够小。

自练： 最小差数组改为含重复值，答案应可为 0；给记录添加“先数值升序，同值按原下标降序”的 key；用插入排序和 sorted 对比至少五个小数组。

平台巩固： 回到第 9 章的排序与奖学金题，解释排序标签里每一项负责哪条题意。不要为凑题目数量再做一批完全相同的纯排序题。

第13章 计数、哈希与离散化

先修：列表、集合、字典、排序与枚举。 关键不是记某个容器名，而是选择需要保存的信息。

13.1 小值域用计数数组

若所有数都在 0 到 9 之间，可以直接用下标表示数值。

a = [2, 0, 2, 9, 0]
count = [0] * 10
for x in a:
    count[x] += 1
for value in range(10):
    if count[value] > 0:
        print(value, count[value])

输出 0 出现 2 次、2 出现 2 次、9 出现 1 次。总时间 O(n+U)，U 是值域大小。若数值可达十亿，不能为“只出现十几个数”创建十亿长度列表，应改用字典。

计数排序。 统计之后，按数值顺序把每个值输出 count[value] 次，就是一种 O(n+U) 的排序。它不适合任意巨大值域。

代码文件：t13_counting_sort.py

def counting_sort(a, upper):
    # 前提：所有元素都是 0..upper 的整数，upper 不宜过大
    count = [0] * (upper + 1)
    for x in a:
        count[x] += 1
    result = []
    for x in range(upper + 1):
        for _ in range(count[x]):
            result.append(x)
    return result

13.2 哈希表保存“见过的值对应什么”

例 1：寻找两个不同位置，使和为 target，返回一组下标。 扫描当前值 x 时，只需要问“之前有没有 target-x”。

代码文件：t13_two_sum.py

def two_sum(a, target):
    position = {}
    for i, x in enumerate(a):
        need = target - x
        if need in position:
            return [position[need], i]
        position[x] = i
    return []

[4,7,4]、target=8：第一轮没有 4，记录 4→0；第二轮找 1，不存在；第三轮找到之前的 4，返回 [0,2]。

必须先查，再放当前值。 否则 target=8、当前 x=4 时，可能用自己和自己配对。字典中维护的严格是“当前下标之前出现过的位置”。平均时间 O(n)，空间 O(n)。若有多组解，本模板只返回首先找到的一组。

13.3 例 2：两个词是否由相同字母组成

频次数组相同，就说明每种字母出现次数都相同，顺序不重要。字符串只含小写英文字母时，使用 26 个格子。

代码文件：t13_anagram.py

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord("a")] += 1
    for ch in t:
        count[ord(ch) - ord("a")] -= 1
    for value in count:
        if value != 0:
            return False
    return True

"abb" 与 "bab" 返回 True，"abb" 与 "baa" 返回 False。如果字符范围不止 26 个字母，改用字典，不要沿用这个索引假设。

标准库 Counter 可作为已理解频次后的便利工具：

from collections import Counter

count = Counter("banana")
print(count["a"])
print(count["x"])

输出 3 和 0。Counter 是计数字典；本书核心算法仍给普通 dict 写法，避免必须熟记额外 API。

13.4 离散化：压缩排名，不保留距离

输入 [1000000000,-20,300,1000000000]，只关心大小关系时，可以把不同值排序成 [-20,300,1000000000]，对应编号 0、1、2。原列表映射为 [2,0,1,2]。

代码文件：t13_discretize.py

def discretize(a):
    values = sorted(set(a))
    rank = {}
    for i, value in enumerate(values):
        rank[value] = i
    compressed = []
    for value in a:
        compressed.append(rank[value])
    return compressed, values

返回两个结果组成的元组；用 compressed,values=discretize(a) 拆包接收。values[id] 可以找回这个编号对应的原数。

离散化保留相等与大小关系，不保留真实差值。100 和 1000000 可能成为相邻编号，但不能据此说它们在原坐标上只相距 1。需要长度、面积时必须使用原坐标差。

排序用 O(n log n)，字典映射平均 O(n)，空间 O(n)。与 Java TreeMap/TreeSet 不同，Python 的普通 dict/set 不提供自动有序的前驱后继操作；静态有序查询可以在第 18 章使用排序列表和 bisect，动态插入仍有移动代价。

13.5 平台练习

巩固｜力扣 1｜两数之和
训练重点与提示：先画出“之前的值→下标”字典，每轮先查补数后记录当前值。不能重复使用同一位置。未开始

巩固｜力扣 242｜有效的字母异位词
训练重点与提示：26 格计数数组或普通字典均可；比较的是次数，不只是出现过哪些字符。未开始

巩固｜力扣 1331｜数组序号转换
训练重点与提示：套用离散化，但题目排名从 1 开始，因此编号要加 1；重复数必须得到相同名次。未开始

自练： 用字典把第 11 章“满足和的所有位置对数量”优化为平均 O(n)。提示：保存出现次数而不是只保存一个位置，每轮先把 count.get(target-x,0) 加到答案，再增加当前 x 的次数。

第14章 前缀和：把重复累加变成相减

先修：列表、二维表、字典与第 11 章区间枚举。 前缀和适合数据基本不变、区间查询很多的情形。

14.1 从手算理解定义

设 a=[3,1,4,2]。定义 pre[i] 为“前 i 个元素的和”，因此 pre[0]=0，pre[1]=3，pre[2]=4，pre[3]=8，pre[4]=10。

要算下标区间 [1,3)，即 a[1]+a[2]，用 pre[3]-pre[1]=8-3=5。先把前 3 个全拿来，再减掉前 1 个，剩下的恰好是需要的部分。

公式： 0-based 半开区间 [l,r) 的和为 pre[r]-pre[l]。0-based 闭区间 [l,r] 的和为 pre[r+1]-pre[l]。题目若用 1-based 闭区间 [L,R]，则是 pre[R]-pre[L-1]。三种写法并非不同算法，只是输入编号不同。

14.2 一维模板与完整调用

代码文件：t14_prefix_sum.py

def build_prefix(a):
    pre = [0] * (len(a) + 1)
    for i in range(len(a)):
        pre[i + 1] = pre[i] + a[i]
    return pre


def range_sum(pre, left, right):
    # 查询原数组的半开区间 [left, right)
    # 前提：0 <= left <= right <= 原数组长度
    return pre[right] - pre[left]

调用 pre=build_prefix([3,1,4,2])，再 range_sum(pre,1,3) 得到 5；查询 (0,4) 得到 10；查询 (2,2) 得到 0，因为空区间没有元素。

建表 O(n)，每次查询 O(1)，q 次查询总 O(n+q)，空间 O(n)。原数组改了之后，旧 pre 不会自动更新。

自编完整例题： 第一行 n q，第二行 n 个整数，随后 q 行输入 1-based 闭区间 L R，输出区间和。

代码文件：prefix_queries.py

import sys


def solve():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    answers = []
    for _ in range(q):
        left, right = map(int, input().split())
        answers.append(str(pre[right] - pre[left - 1]))
    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()

输入 4 2、3 1 4 2、2 3、1 4（各自一行），输出 5 和 10。此输入格式为自编约定，不等同于所有平台的格式。

14.3 二维前缀和：重复的左上角要补回来

定义 pre[r][c] 为前 r 行、前 c 列的总和，多开全零的第 0 行和第 0 列。新格子对应的前缀和是：上面区域＋左边区域－重复的左上区域＋当前格。

这里出现一个新的简写：A if 条件 else B 是条件表达式，条件成立取 A，否则取 B。m = len(grid[0]) if n>0 else 0 因此不会在空矩阵时读取 grid[0]。后文可使用这个已解释的写法。

代码文件：t14_prefix_sum_2d.py

def build_prefix_2d(grid):
    n = len(grid)
    m = len(grid[0]) if n > 0 else 0
    pre = [[0] * (m + 1) for _ in range(n + 1)]
    for r in range(n):
        for c in range(m):
            pre[r + 1][c + 1] = (
                pre[r][c + 1] + pre[r + 1][c]
                - pre[r][c] + grid[r][c]
            )
    return pre


def rectangle_sum(pre, r1, c1, r2, c2):
    # 原矩阵的 [r1,r2) 行、[c1,c2) 列，两个方向都半开
    return (pre[r2][c2] - pre[r1][c2]
            - pre[r2][c1] + pre[r1][c1])

例 2： 矩阵 [[1,2,3],[4,5,6]] 的全部前缀表为 [[0,0,0,0],[0,1,3,6],[0,5,12,21]]。查询两行、后两列，即 (r1,c1,r2,c2)=(0,1,2,3)，得到 21-0-5+0=16，对应 2+3+5+6。

建表 O(nm)，每次查询 O(1)，空间 O(nm)。这里假设每行长度相同。

14.4 提高：前缀和＋哈希统计区间数量

要找和为 k 的非空连续区间，设当前前缀和为 total。我们想找以前的前缀和 old，使 total-old=k，即 old=total-k。因此保存每种旧前缀和出现过多少次。

代码文件：t14_subarray_hash.py

def count_subarrays(a, k):
    frequency = {0: 1}
    total = 0
    answer = 0
    for x in a:
        total += x
        answer += frequency.get(total - k, 0)
        frequency[total] = frequency.get(total, 0) + 1
    return answer

frequency={0:1} 表示在读取任何元素之前，有一个空前缀；它允许统计从下标 0 开始的区间。不是在把空区间算为答案。

对 [1,-1,1]、k=1：total 依次为 1、0、1；每轮增加答案 1、0、2，总数 3。第三轮有两个旧前缀和 0，因此对应两个不同的合法起点。

先查询再记录当前前缀，避免 k=0 时把长度为 0 的区间误计入。允许负数与零，平均 O(n) 时间、O(n) 空间。

14.5 不要推广到不能相减的统计量

前缀计数可以相减，前缀异或可用异或消去；但是两个前缀最大值或最小值不能简单相减恢复任意区间的最大最小值。原参考笔记列举过前缀最值，本书特别区分：“可以维护前缀最值”不等于“任意区间最值也能用相同相减公式”。

14.6 平台练习

入门｜力扣 1480｜一维数组的动态和
训练重点与提示：先练最朴素的前缀累加；输出每个位置到开头的和，不需要区间查询。未开始

巩固｜洛谷 P8218｜【深进1.例1】求区间和
训练重点与提示：标准输入输出练习。该题第一行只有 n，第三行才是查询个数 m，不能原样照抄本章自编 n q 输入。未开始

巩固｜力扣 303｜区域和检索 - 数组不可变
训练重点与提示：用第 10 章的 init 保存 self.pre；sumRange 的 right 是闭端点，公式应使用 right+1。未开始

提高｜力扣 304｜二维区域和检索 - 矩阵不可变
训练重点与提示：二维版本，四个角的正负号要用手算矩阵验证；平台给的是包含右下角的闭矩形。未开始

提高｜力扣 560｜和为 K 的子数组
训练重点与提示：使用前缀和次数字典；允许负数，因此不要直接套“窗口和超标就缩小”的方法。未开始

第15章 差分：把区间修改集中到边界

先修：前缀和。 差分适合“做很多次区间加减，最后统一取结果”，不是同时高效支持任意修改与查询的万能结构。

15.1 为什么只需要改两个位置

对 a=[2,5,5,1]，差分为 diff=[2,3,0,-4]：第一项是原值，后面每项是当前项减前一项。对 diff 求前缀和又恢复 a。

如果给闭区间 [1,2] 都加 3，得到 [2,8,8,1]。区间内部相邻两项都加 3，它们的差不变；只有开始处多 3，结束后的第一个位置少 3。因此只需 diff[1]+=3、diff[3]-=3。

用变化信号理解：left 位置开启增量，right+1 位置撤销增量。一定不是在 right 撤销，因为 right 仍属于要修改的区间。

15.2 一维通用模板

代码文件：t15_difference.py

def apply_range_adds(a, updates):
    # updates 中每项为 (left, right, delta)
    # 使用原数组 0-based 闭区间；不修改 a
    n = len(a)
    diff = [0] * (n + 1)
    previous = 0
    for i in range(n):
        diff[i] = a[i] - previous
        previous = a[i]
    for left, right, delta in updates:
        diff[left] += delta
        diff[right + 1] -= delta
    result = []
    current = 0
    for i in range(n):
        current += diff[i]
        result.append(current)
    return result

多开一位，允许 right=n-1 时写 diff[n]。这只是结束信号，不属于原数组输出。

例 1： a 为 [2,5,5,1]，修改依次 (1,2,3)、(0,3,-1)。第一步 [2,8,8,1]，第二步 [1,7,7,0]，函数应返回后者。减法就是 delta 取负。

例 2：区间覆盖次数。 原数组全零，每覆盖一个闭区间就加 1。恢复后大于 0 的位置被覆盖过，等于 0 的位置未覆盖。重叠处可能大于 1，不要直接拿覆盖次数之和当成覆盖位置数。

总时间 O(n+q)，空间 O(n)。前提是各更新下标合法；空数组时只能没有更新。

15.3 半开事件与“先下车再上车”

若一个人在位置 L 上车、位置 R 下车，他占用的是 [L,R) 的路段，因此写 diff[L]+=人数、diff[R]-=人数，不是 R+1。差分符号不变，关键是题意中的右端是否仍受影响。

同一个位置先下车后上车，使用各事件的净变化恢复该位置离开时的载客数即可。涉及“到达前”还是“离开后”的问题，先明确你统计的时刻。

15.4 二维差分：四个角的信号

在矩形闭区间 (r1,c1) 到 (r2,c2) 加 delta：左上加，下一行左端减，右边一列上端减，右下外角再加。最后做二维前缀恢复增量。

代码文件：t15_difference_2d.py

def add_rectangles(grid, updates):
    n = len(grid)
    m = len(grid[0]) if n > 0 else 0
    diff = [[0] * (m + 1) for _ in range(n + 1)]
    for r1, c1, r2, c2, delta in updates:
        diff[r1][c1] += delta
        diff[r2 + 1][c1] -= delta
        diff[r1][c2 + 1] -= delta
        diff[r2 + 1][c2 + 1] += delta
    answer = [row.copy() for row in grid]
    for r in range(n):
        for c in range(m):
            if r > 0:
                diff[r][c] += diff[r - 1][c]
            if c > 0:
                diff[r][c] += diff[r][c - 1]
            if r > 0 and c > 0:
                diff[r][c] -= diff[r - 1][c - 1]
            answer[r][c] += diff[r][c]
    return answer

本模板把“原矩阵”和“新增变化”分开，只对变化建立差分，所以不用先把原矩阵转成二维差分。输入不得是长短不一的行；更新坐标必须在矩阵内。

例 3： 原矩阵 [[1,1,1],[1,1,1]]，给 (0,1) 到 (1,2) 加 2，结果为 [[1,3,3],[1,3,3]]。用小矩阵画出四个角，确认增量不会泄漏到第 0 列。

15.5 不能套用的情况

频繁更新后立刻询问任意区间和，普通差分每次恢复都需要扫描，不再有本章的总 O(n+q) 优势；通常需要树状数组或线段树等后续结构。本书暂不把这些当作零基础必学内容。

15.6 平台练习

巩固｜力扣 1109｜航班预订统计
训练重点与提示：航班编号从 1 开始，两端都包含。可先转为 0-based 闭区间再使用差分。未开始

巩固｜洛谷 P1047｜【NOIP 2005 普及组】校门外的树
训练重点与提示：0 到 l 共 l+1 棵树，包含两个端点。求未被覆盖的位置数，不是简单减去各区间长度。未开始

提高｜力扣 1094｜拼车
训练重点与提示：乘客占用 [from,to)，下车处就要减，不写 to+1；检查恢复后的载客量是否超容量。未开始

提高｜洛谷 P3397｜地毯
训练重点与提示：二维差分与恢复；题面坐标从 1 开始，读入统一减 1。先用一块地毯验证四角符号。未开始

第16章 双指针：让两个位置有方向地移动

先修：列表、下标、排序、复杂度。 “指针”在这里就是保存位置的整数变量，不需要学习内存地址。

16.1 相向双指针与原地反转

left 从最左边开始，right 从最右边开始。交换两端，再向中间移动。

代码文件：t16_reverse.py

def reverse_in_place(a):
    left = 0
    right = len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1

对 [1,2,3,4,5]：交换 1/5，再交换 2/4，中间的 3 不动。结果是 [5,4,3,2,1]。函数修改原列表，返回 None；调用后查看 a，不要写 a=reverse_in_place(a)。

为什么条件是 <？left==right 时是同一个中间位置，再交换无意义。空列表 right=-1，循环自然不执行。O(n) 时间、O(1) 额外空间，不需要创建反转切片。

16.2 有序数组两数之和：为什么可以排除一整批

数组已从小到大排列，要求找两个不同位置的和等于 target。

代码文件：t16_sorted_two_sum.py

def sorted_two_sum(a, target):
    left = 0
    right = len(a) - 1
    while left < right:
        current = a[left] + a[right]
        if current == target:
            return [left, right]
        if current < target:
            left += 1
        else:
            right -= 1
    return []

若当前和太小，固定 left 后，右边能选到的最大值就是 a[right]，连它都不够，其他更小的右值也不够，因此当前 left 可以彻底排除。若和太大，同理排除当前 right。不是凭感觉左右移动。

例 1： [1,3,4,8,10]，target=12：1+10=11，左移到 3；3+10=13，右移到 8；3+8=11，左移到 4；4+8=12，返回 [2,3]。

两个指针各自最多移动 n 次，因此 O(n) 时间、O(1) 额外空间。要求数组已经有序；如果先排序，则总时间包含 O(n log n)，并且原下标会改变。

16.3 同向双指针：读位置与写位置

例 2：把非零数保持相对顺序放到前面，其余补零。 read 负责读原位置，write 表示下一个非零数应写入的位置。

代码文件：t16_move_zeroes.py

def move_zeroes(a):
    write = 0
    for read in range(len(a)):
        if a[read] != 0:
            a[write] = a[read]
            write += 1
    for i in range(write, len(a)):
        a[i] = 0

对 [0,3,0,1]，先把 3 写到下标 0，把 1 写到下标 1，再把下标 2、3 补零，得到 [3,1,0,0]。始终有 write≤read，写入不会覆盖尚未读取的未来位置。

例 3：有序列表原地去重。

代码文件：t16_unique.py

def unique_sorted_in_place(a):
    if not a:
        return 0
    write = 1
    for read in range(1, len(a)):
        if a[read] != a[write - 1]:
            a[write] = a[read]
            write += 1
    return write

对 [1,1,2,2,3] 返回 3，前 3 项变为 [1,2,3]；后面内容无须有意义。返回的是有效长度，不是新列表。前提是有序，相同元素才能挤在一起。

16.4 自编例题 4：合并两个有序序列

i、j 分别指向两个列表中尚未处理的第一个数。每次取更小的数放入答案。

代码文件：t16_merge_sorted.py

def merge_sorted(a, b):
    i = 0
    j = 0
    answer = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            answer.append(a[i])
            i += 1
        else:
            answer.append(b[j])
            j += 1
    while i < len(a):
        answer.append(a[i])
        i += 1
    while j < len(b):
        answer.append(b[j])
        j += 1
    return answer

[1,4,7] 与 [2,4] 得到 [1,2,4,4,7]。一个列表耗尽后，另一个的剩余部分本来就有序，可以直接接上。O(n+m) 时间，结果占 O(n+m) 空间。

16.5 平台练习

入门｜力扣 344｜反转字符串
训练重点与提示：输入是字符列表而非不可变字符串；要求原地修改，不能用额外的反转列表代替。未开始

巩固｜力扣 283｜移动零
训练重点与提示：读写双指针，保持非零元素相对顺序，最后补零。未开始

巩固｜力扣 26｜删除有序数组中的重复项
训练重点与提示：返回有效长度 k，并保证前 k 项正确；后面的旧数据可以忽略。未开始

巩固｜力扣 167｜两数之和 II - 输入有序数组
训练重点与提示：利用有序性移动两端；平台答案编号从 1 开始，返回时把下标各加 1。未开始

提高｜力扣 125｜验证回文串
训练重点与提示：先说明忽略非字母数字、忽略大小写的规则，再用 isalnum/lower 与双指针；这些字符方法已在第 6 章讲过。未开始

第17章 滑动窗口：维护连续区间

先修：双指针、计数、区间长度。 窗口是数组或字符串的一段连续区域，不是任意挑选的子序列。

17.1 固定长度窗口：进一个、出一个

例 1：长度恰好为 k 的连续区间最大和。 第一个窗口求出和，之后右边加入一个新元素，左边移出一个旧元素。

代码文件：t17_fixed_window.py

def max_fixed_window_sum(a, k):
    # 前提：1 <= k <= len(a)，允许负数
    total = sum(a[:k])
    answer = total
    for right in range(k, len(a)):
        total += a[right]
        total -= a[right - k]
        answer = max(answer, total)
    return answer

[2,-1,3,4,-2]、k=3：窗口和依次为 4、6、5，答案 6。先以第一个真实窗口初始化答案，避免全负数时错答 0。

固定长度窗口仅仅更新和，允许负数。这个事实不能推广到下一节依赖单调性的变长窗口。

17.2 和不超过 limit 的最长区间

前提：数组元素非负、limit≥0。右端加入元素会使和不减，左端移出元素会使和不增，因此超标时可以不断缩小左边。

代码文件：t17_longest_limit.py

def longest_sum_at_most(a, limit):
    # 前提：a 中元素非负，limit >= 0
    left = 0
    total = 0
    answer = 0
    for right in range(len(a)):
        total += a[right]
        while left <= right and total > limit:
            total -= a[left]
            left += 1
        answer = max(answer, right - left + 1)
    return answer

例 2： a=[2,1,3,1,1]，limit=4。右端到下标 2 时和为 6，去掉左端的 2 后和为 4，窗口成为 [1,3]；右端到下标 3 时，和变为 5，移出左端的 1，窗口成为 [3,1]；再加入最后的 1，和又变为 5，移出 3 后留下 [1,1]。过程中最长合法窗口长度是 2。三个长度为 3 的区间和分别为 6、5、5，均超过限制，也能独立核对答案。

再换 a=[2,1,1,3]、limit=4，最长为 [2,1,1]，答案 3。两组相近输入能检查你有没有把“窗口内三个数字”误认为自动合法。

17.3 和至少为 target 的最短区间

前提：元素为正整数、target>0。这次窗口一旦满足要求，就记录答案，并尝试缩短。注意记录答案发生在缩小之前。

代码文件：t17_shortest_target.py

def shortest_sum_at_least(a, target):
    # 前提：所有元素 > 0，target > 0
    left = 0
    total = 0
    answer = len(a) + 1
    for right in range(len(a)):
        total += a[right]
        while total >= target:
            answer = min(answer, right - left + 1)
            total -= a[left]
            left += 1
    if answer == len(a) + 1:
        return 0
    return answer

例 3： [2,1,4,2]、target=6。到 4 时窗口和为 7，记录长度 3，去掉 2 后变 5；加入最后的 2 后为 7，先记录长度 3，再去掉 1 后为 6，记录长度 2，最终答案 2，对应 [4,2]。

两个 while/for 嵌套，但 left 和 right 都只前进，总时间 O(n)，额外空间 O(1)。如果有负数，例如 [1,-1,5]，移出负数会让和变大，以上排除逻辑就不成立。

17.4 无重复字符的最长子串

右端新字符加入后，如果它重复，就移动左端，把旧字符逐个移出，直到当前字符在窗口中只出现一次。

代码文件：t17_distinct_window.py

def longest_distinct_substring(s):
    count = {}
    left = 0
    answer = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            old = s[left]
            count[old] -= 1
            left += 1
        answer = max(answer, right - left + 1)
    return answer

例 4： "abba"。读到第二个 b 时，不能只删掉一个左字符 a 就停止；窗口仍有两个 b，还需移出旧 b。最终最长长度 2。这里用 while，不是 if。

平均 O(n) 时间，字典占 O(字符种类数) 空间。空串返回 0。即使某个字符计数降为 0，本模板保留这个键也不影响“次数>1”的判定。

17.5 提高练习的桥梁：固定窗口比较频次

要找某个词的所有异位词子串，先在第 13 章建立目标词的 26 格计数，再维护长度等于目标词长度的窗口计数。右端字符次数加一，超出长度时把左端字符次数减一；窗口形成后比较两个列表是否相等，相等就保存左端下标。

两个长度为 26 的列表可直接用 == 比较每项是否相等。这需要 O(26) 时间，在固定小写字母范围下是常数。不要每轮重新切片、排序整个窗口。

17.6 平台练习

入门｜力扣 643｜子数组最大平均数 I
训练重点与提示：固定长度最大和最后除以 k 得到平均数；题目允许负数，答案不能初始化为 0。未开始

巩固｜力扣 209｜长度最小的子数组
训练重点与提示：正数数组、最短达到目标的窗口；无解按题面返回 0。未开始

巩固｜力扣 3｜无重复字符的最长子串
训练重点与提示：使用字符次数字典；遇到重复字符时循环缩小，不要只移动一次。未开始

提高｜力扣 438｜找到字符串中所有字母异位词
训练重点与提示：固定长度窗口＋26 格计数；上一节已给出组合步骤。s 比 p 短时答案为空列表。未开始

第18章 普通二分与 bisect

先修：有序数组、while、半开区间。 二分的本质是利用单调性，每轮排除一半不可能的范围。

18.1 先只学一种边界：左闭右开

我们寻找第一个大于等于 target 的位置。令 left=0、right=len(a)；尚未确定的位置范围用 [left,right) 表示。right 可以等于 n，但从不直接访问 a[n]。

代码文件：t18_bounds.py

def lower_bound(a, target):
    # a 必须非递减排列；返回第一个 >= target 的位置
    left = 0
    right = len(a)
    while left < right:
        mid = (left + right) // 2
        if a[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left


def upper_bound(a, target):
    # 返回第一个 > target 的位置
    left = 0
    right = len(a)
    while left < right:
        mid = (left + right) // 2
        if a[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left

lower_bound 中，a[mid] 已经够大时 mid 本身可能就是第一个，所以保留 mid 作为边界；a[mid] 太小时，mid 及更左都不合适，令 left=mid+1。循环每轮缩小区间，left==right 时答案唯一。

没有满足条件的元素时返回 n。这是合法的“插入位置”，但不是合法的元素下标。空列表自然返回 0。

18.2 手算两种边界

例 1： a=[1,2,2,2,5]，target=2。

lower_bound：初始 [0,5)，mid=2，值 2 够大，right=2；范围 [0,2)，mid=1，值 2 够大，right=1；范围 [0,1)，mid=0，值 1 太小，left=1。返回 1。

upper_bound：mid=2 的值不大于 2，所以 left=3；继续最终返回 4。因此 target 出现次数为 4-1=3，第一次位置 1，最后一次位置 3。

例 2： target=3，两个边界都为 4，次数 0。例 3： target=10，两个边界都为 5。不能因为得到一个数字位置就宣布找到了 target。

18.3 查找存在性与最后一个位置

from bisect import bisect_left

a = [1, 2, 2, 5]
target = 3
pos = bisect_left(a, target)
if pos < len(a) and a[pos] == target:
    print(pos)
else:
    print(-1)

标准库 bisect_left 与本章 lower_bound 含义一致；bisect_right 与 upper_bound 一致。使用前需要 from bisect 导入。

“最后一个 ≤x”的位置是 upper_bound(a,x)-1；“最后一个 <x”的位置是 lower_bound(a,x)-1。结果可能为 -1，表示不存在，不要拿 a[-1] 当作找到了最后一项。

18.4 二分查询快，不代表列表插入快

二分 O(log n)，但把元素插到列表中间仍需要移动后续元素，通常 O(n)。bisect.insort 是找到插入位置再插入，不会把 Python 列表变成平衡搜索树。本书建议初学先把 bisect 用于静态排序列表的查询。

二分无需每次切片，切片不仅增加开销，也会改变下标坐标。循环使用两个整数边界即可。每次查询 O(log n)，额外空间 O(1)；如果先排序，总时间还要加上排序部分。

18.5 平台练习

入门｜力扣 704｜二分查找
训练重点与提示：用 lower_bound 后检查是否真的相等，或者独立练习闭区间查找；先别混用两套更新规则。未开始

巩固｜力扣 35｜搜索插入位置
训练重点与提示：返回插入位置，即 lower_bound，允许结果等于数组长度。未开始

巩固｜力扣 34｜在排序数组中查找元素的第一个和最后一个位置
训练重点与提示：先查左边界判断存在，再用右边界减一；无解返回 [-1,-1]。未开始

提高｜洛谷 P2249｜【深基13.例1】查找
训练重点与提示：首次出现编号从 1 开始；大输入用较快逐行读取，输出集中处理，别逐次重新排序。未开始

第19章 二分答案：把“最优”变成“可不可行”

先修：二分、函数、枚举、整数向上取整。 不一定要在数组里二分，也可以在可能的答案数轴上二分。

19.1 第一步不是写循环，而是证明单调

例如速度越快，完成工作所需时间不会更多。于是“速度 v 能否在期限内完成”按 v 从小到大排列时，是一段 False 后接一段 True。需要找第一个 True，就是最小可行值。

切割长度越长，能切出的段数不会更多。“长度 L 能否切出至少 k 段”是一段 True 后接一段 False。需要找最后一个 True，就是最大可行值。

如果可行性可能反复真假交替，普通二分不能直接使用。只看到“最大”“最小”不代表一定能二分。

19.2 两个完整边界工具，允许没有可行值

这里 check 是一个已经写好的函数：传入候选答案，返回 True/False。第 9 章给 sort 传 key 函数时，已经学过把函数当参数传入。

代码文件：t19_answer_boundaries.py

def first_true(left, right, check):
    # 在整数闭区间 [left,right] 找第一个 True
    # 前提：False...False, True...True；无解返回 None
    answer = None
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer


def last_true(left, right, check):
    # 前提：True...True, False...False；无解返回 None
    answer = None
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer

本节为了记录明确候选，使用闭区间 left<=right，与上一章的半开区间不同。每个模板内部自洽，不能把上一章的 right=mid 混入这个版本。

19.3 自编例题 1：最小处理速度

有若干工作批次，一小时只能处理其中一批，最多处理 speed 个单位；一批剩余不足 speed 也占一小时。要求在 hours 小时内全部完成，求最小正整数速度。

一批 size 所需时间是 (size+speed-1)//speed。把每批时间加起来即可检查候选速度。

代码文件：t19_minimum_speed.py

def minimum_speed(piles, hours):
    # piles 为非空正整数列表
    if hours < len(piles):
        return None
    left = 1
    right = max(piles)
    answer = right
    while left <= right:
        speed = (left + right) // 2
        used = 0
        for size in piles:
            used += (size + speed - 1) // speed
            if used > hours:
                break
        if used <= hours:
            answer = speed
            right = speed - 1
        else:
            left = speed + 1
    return answer

例 1： piles=[4,7,9]、hours=6。速度 3 用时 2+3+3=8，不行；速度 4 用时 1+2+3=6，可行；速度更大不会让时间增加，因此最小速度 4。

下界不能从 0 开始，否则 check 中会除零。上界 max(piles) 保证每批只需一小时，前提是 hours≥批次数。不足批次数时本模板返回 None，不能假装一定有解。

时间 O(n log M)，M 是最大批次大小，额外空间 O(1)。

19.4 自编例题 2：最长等长木段

长度为 L 的木头可切出 L//piece 段，每段不能跨原木拼接。求能得到至少 need 段的最大正整数长度；没有可行正长度时输出 0。

代码文件：t19_cut_wood.py

def maximum_piece_length(lengths, need):
    # 前提：lengths 非空且非负，need > 0
    left = 1
    right = max(lengths)
    answer = 0
    while left <= right:
        piece = (left + right) // 2
        count = 0
        for length in lengths:
            count += length // piece
        if count >= need:
            answer = piece
            left = piece + 1
        else:
            right = piece - 1
    return answer

[8,5]、need=4：长度 3 能切 2+1=3 段，不行；长度 2 能切 4+2=6 段，可行，答案 2。不能用 sum(lengths)//piece，那相当于允许把不同木头拼接。

19.5 例 3：砍树高度与木段长度不同

锯片高度 h 下，一棵树 height 贡献 max(0,height-h)，不是 height//h。将这些贡献相加，判断是否至少需要的木材，寻找最大可行 h。两题同样二分最大值，但 check 的数学模型完全不同。

习惯：先用一个很小的候选值手算 check，再写二分循环。区间包含零时也要确认 check 没有除零行为。

19.6 平台练习

巩固｜力扣 875｜爱吃香蕉的珂珂
训练重点与提示：最小速度，逐堆向上取整后再求和；不能把所有香蕉总数除以速度，因为每小时只处理一堆。未开始

巩固｜洛谷 P2440｜木材加工
训练重点与提示：原木逐根输入；查找最大正长度，无解按题意输出 0。未开始

提高｜洛谷 P1873｜EKO / 砍树
训练重点与提示：每棵树贡献 max(0,height-h)，查最大锯片高度。大规模输入与多次全扫描可能影响 Python 性能，注意题目环境和常数。未开始

第20章 贪心：每一步的选择需要理由

先修：排序、双指针与前缀累积。 贪心每次做一个局部选择，然后不撤销。它不是“随便选看起来最好的”。

20.1 区间安排：为什么优先结束早的

每个活动都有开始、结束时间，只能参加不重叠的活动，结束时刻等于下一活动开始时刻允许衔接。目标是活动数量最多。

最早结束的活动给后面留下的时间最多。把任意最优方案的第一个活动换成全体中结束最早的那个，不会让后续活动变得不可参加，数量也不会减少。因此一定存在以它开头的最优方案；剩余部分重复同样道理。

is None 是判断某个值是否就是特殊值 None 的标准写法；这里首次将它作为状态标志明确使用。它不同于一般数值是否相等的 ==，后续只用 is None 检查“没有值”，不拿 is 比较普通整数或字符串。

代码文件：t20_interval_schedule.py

def maximum_activities(intervals):
    # 每项 (start,end)，要求 start < end
    # 允许上一项 end == 下一项 start
    ordered = sorted(intervals, key=lambda item: item[1])
    chosen = []
    last_end = None
    for start, end in ordered:
        if last_end is None or start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

例 1： (1,4),(2,3),(3,5),(5,6)，按结束时间处理，选 (2,3),(3,5),(5,6)，共 3 个。只按开始时间最早贪心可能先选 (1,4)，最后只能选 2 个。

O(n log n) 时间。本模板返回具体方案，空间 O(n)；只问数量时，chosen 可以改为整数计数。

20.2 合并区间不是选择最多区间

合并区间要求把所有覆盖范围保留下来，因此先按开始时间排序，维护当前合并段的右端。与前面的“结束时间排序、选部分活动”是不同模型。

代码文件：t20_merge_intervals.py

def merge_intervals(intervals):
    # 本模板按闭区间理解，相接或重叠的端点归入同一段
    ordered = sorted(intervals)
    result = []
    for start, end in ordered:
        if not result or start > result[-1][1]:
            result.append([start, end])
        else:
            result[-1][1] = max(result[-1][1], end)
    return result

例 2： [[1,3],[2,6],[8,10],[10,12]] 合并后是 [[1,6],[8,12]]。如果当前区间被旧区间完全包含，右端不应缩短，所以必须使用 max。

20.3 排队等待：短任务放前面

两个人的处理时间为 a、b。在他们之前已等待的时间相同时，a 在前对两人的新增等待贡献是 a，b 在前则是 b，所以较短的放前面不会更差。不断交换相邻逆序对，可得到按时长升序的最优顺序。

代码文件：t20_waiting_time.py

def minimum_total_wait(times):
    ordered = sorted(times)
    elapsed = 0
    total_wait = 0
    for duration in ordered:
        total_wait += elapsed
        elapsed += duration
    return total_wait

例 3： [3,1,2] 排成 [1,2,3]。三人的等待分别是 0、1、3，总和 4，不是所有人完成时刻的和。如果问平均等待，最后再除以人数；如果还要原编号，使用第 12 章的 (时长,编号) 记录。

20.4 饼干与需求：小资源优先满足小需求

将需求与资源都升序排序。拿最小未使用资源尝试满足最小未满足需求；不足就跳过该资源，足够就同时推进两个指针。把小需求交给能满足它的最小资源，不会抢走更大需求唯一能用的大资源。

例 4： 需求 [1,2,4]、资源 [1,3]。1 满足需求 1，3 满足需求 2，共满足 2 人。这里要求每人至多一个资源、资源不能拆分，也不追求总收益；若问题目标不同，贪心规则不一定仍对。

反例意识： 面值 [1,3,4] 凑金额 6，每次选最大会用 4+1+1 共 3 枚，而 3+3 只需 2 枚。不能把“硬币越大越好”当通用定理，第 33 章会用动态规划解决一般情况。

20.5 平台练习

入门｜力扣 455｜分发饼干
训练重点与提示：排序＋双指针，匹配最小未满足需求；匹配数量才是答案。未开始

巩固｜力扣 56｜合并区间
训练重点与提示：练习合并所有区间，排序依据是开始时间，而不是区间选择的结束时间。未开始

巩固｜力扣 435｜无重叠区间
训练重点与提示：求最少删除个数可以转为总数减去最多保留的不重叠区间数；端点相接是否冲突按题面规则。未开始

提高｜洛谷 P1223｜排队接水
训练重点与提示：排序时保留原编号，累计每个人开始前已经消耗的时间；按题面要求输出平均值的小数位。未开始

提高｜洛谷 P1803｜凌乱的 yyy / 线段覆盖
训练重点与提示：最多活动数量，按结束时间贪心；数据可能很大，先核对 Python/PyPy 与内存条件，不把建许多对象的模板当性能承诺。未开始

第21章 栈、队列、双端队列与堆

先修：列表、字典、标准库导入、贪心。 它们的主要差别在于“下一次该取出谁”。

21.1 栈：后进先出

像叠盘子，最后放上去的先取出。用 list 的末尾表示栈顶：append 入栈，pop 出栈，stack[-1] 查看栈顶但不删除。

stack = []
stack.append(3)
stack.append(8)
print(stack[-1])
print(stack.pop())
print(stack.pop())

输出 8、8、3。读取栈顶或弹出前需要确保非空。末尾操作很适合栈，不需要从列表开头移元素。

例 1：括号匹配。 遇到左括号就等待匹配；遇到右括号时，它应该与最近一个尚未匹配的左括号配对，所以使用栈。

代码文件：t21_brackets.py

def valid_brackets(s):
    # 前提：s 只包含 ()[]{} 六种括号
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack[-1] != pair[ch]:
                return False
            stack.pop()
    return len(stack) == 0

([])：依次压入 (、[，遇到 ] 弹出 [，遇到 ) 弹出 (，最后空栈，合法。([)] 虽然三种括号数量可能匹配，但顺序不对，在 ) 处立即失败。

时间 O(n)，空间 O(n)。只计左右括号数量不能处理这种嵌套关系。

21.2 例 2：相邻重复字符抵消

扫描字符时，栈表示当前尚未被删除的结果。新字符等于栈顶就抵消，否则入栈。

代码文件：t21_remove_adjacent.py

def remove_adjacent_pairs(s):
    stack = []
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

"abbaca" 中两个 b 抵消后，原来的两个 a 新近相邻，也会在扫描过程中自然抵消，最终得到 "ca"。不需要反复对整串进行 replace，避免重复扫描。

21.3 队列：先进先出

像排队买票，先加入的先处理。使用 collections.deque，读作双端队列。

from collections import deque

queue = deque()
queue.append(3)
queue.append(8)
print(queue[0])
print(queue.popleft())
print(queue.popleft())

输出 3、3、8。append 从右边入队，popleft 从左边出队，两端操作通常 O(1)。不要在大量队列操作中使用 list.pop(0)，它需要不断移动后面的元素。

deque 还支持 appendleft 在左边加入、pop 从右边移出。它适合两端操作，不适合频繁随机访问中间位置。

例 3：最近一段时间的请求。 时间严格递增，每次把 t 入队，然后不断移除小于 t-3000 的旧时间；剩余长度就是闭区间 [t-3000,t] 的请求数。等于左端点的请求要保留。

代码文件：t21_recent_calls.py

from collections import deque


def recent_counts(times, width):
    # 前提：times 非递减，width >= 0
    queue = deque()
    answer = []
    for t in times:
        queue.append(t)
        while queue and queue[0] < t - width:
            queue.popleft()
        answer.append(len(queue))
    return answer

times=[1,100,3001,3002]、width=3000，结果 [1,2,3,3]。每个时间最多入队、出队一次，总时间 O(n)。这是第 17 章窗口思想在队列上的实现。

21.4 堆：每次取优先级最高的

当下一次要取最小值，而不是最早或最晚插入的值时，使用小根堆。标准库 heapq 把一个普通列表维护为堆。

import heapq

heap = [5, 1, 8]
heapq.heapify(heap)
heapq.heappush(heap, 3)
print(heap[0])
print(heapq.heappop(heap))
print(heapq.heappop(heap))

输出 1、1、3。heapify 将整个列表原地建堆，时间 O(n)；heappush 入堆和 heappop 出堆为 O(log n)；heap[0] 查看最小值 O(1)。

堆不是完全排好序的列表。 只保证堆顶最小，直接遍历 heap 不会自动升序。若需要全部排序结果，通常用 sorted 更直观。

要取最大值，可把数字取负后放入小根堆，弹出时再取负。这样不依赖较新解释器才有的最大堆接口。

堆中可以放 (距离,节点编号) 元组，先比较距离，相同再比较编号。若后一项是不能相互比较的自定义对象，可能出错；本书图算法使用整数节点编号，避免这个问题。

21.5 例 4：最小合并代价

每次合并两堆，代价是它们重量之和，合并后的新堆还要参加后续合并。规则是每次选最小的两堆。

为什么小的先合？每个原堆的重量会在它参与的每一层合并中重复计费。将合并过程看成“两条分支汇合为一个新堆”的层级图，总费用等于原重量乘各自参与层数再求和。存在一个最优层级安排，使最轻的两个原堆在最深处成对：把更轻的重量换到更深处不会增加费用。先把这两堆合成一个整体，剩余问题形式相同。

代码文件：t21_merge_cost.py

import heapq


def minimum_merge_cost(weights):
    # 前提：重量非负；不修改原列表
    heap = weights.copy()
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        merged = first + second
        total += merged
        heapq.heappush(heap, merged)
    return total

[1,2,7]：先合 1+2，代价 3；再合 3+7，代价 10；总 13。若先合 2+7，总代价是 9+10=19。只有一堆时无需合并，答案 0。O(n log n) 时间、O(n) 空间。

21.6 平台练习

巩固｜力扣 20｜有效的括号
训练重点与提示：括号匹配，必须检查类型和嵌套顺序；末尾还剩左括号也不合法。未开始

巩固｜力扣 1047｜删除字符串中的所有相邻重复项
训练重点与提示：栈保存删除后的前缀结果，当前字符与栈顶相同则抵消。未开始

巩固｜力扣 933｜最近的请求次数
训练重点与提示：按第 10 章的对象初始化写 self.queue，每次 ping 更新队列；恰好 t-3000 的请求仍保留。未开始

巩固｜洛谷 P3378｜【模板】堆
训练重点与提示：根据操作类型入堆、查看堆顶、弹出；百万次操作时注意输入输出。未开始

巩固｜力扣 1046｜最后一块石头的重量
训练重点与提示：用负数模拟最大堆，按照题目规定每次取最重两块，不是最小合并模型。未开始

提高｜洛谷 P1090｜【NOIP 2004 提高组】合并果子
训练重点与提示：最小合并代价。新合并的重量必须重新入堆，不能只把原数组排序后相邻配对一次。未开始

第22章 最大公约数、进制与高精度整数

先修：整除、取余、循环、函数、字符串。 先明确数学含义，再使用库函数。

22.1 约数、倍数与互质

如果 a 能被 d 整除，就说 d 是 a 的约数，a 是 d 的倍数。两个正整数共有的最大正约数叫最大公约数，简称 GCD；共同的最小正倍数叫最小公倍数，简称 LCM。GCD 为 1 时，两个数互质。

例如 18 的正约数为 1、2、3、6、9、18，24 的正约数为 1、2、3、4、6、8、12、24，最大公约数为 6。最小公倍数为 72。

22.2 辗转相除为何成立

若 a = q*b + r，同时整除 a 和 b 的数也能整除 r；反过来，同时整除 b 和 r 的数也能整除 a。因此 gcd(a,b)=gcd(b,a%b)。余数越来越小，最终变成 0，另一个数就是答案。

代码文件：t22_gcd_lcm.py

def gcd(a, b):
    a = abs(a)
    b = abs(b)
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    # 编程约定：任意一个为 0 时返回 0
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)

gcd(48,18)：(48,18)→(18,12)→(12,6)→(6,0)，结果 6。这里对 gcd(0,0) 采用编程约定返回 0；避免让 lcm(0,0) 发生除零。

对非零整数，有 lcm(a,b)=abs(a//gcd(a,b)*b)。先除后乘不会改变整数精确性，也避免制造不必要的大中间值。辗转相除的轮数为对数级；高精度情形还需计入每轮大整数求余成本。

标准库使用 math.gcd(a,b)；支持相应版本时可用 math.lcm(a,b)，手写版本没有该接口的版本依赖。

22.3 自编例题 1：分数约分

输入两个正整数 numerator、denominator，先求 gcd，再把两者都除以 gcd。

from math import gcd

numerator, denominator = map(int, input().split())
g = gcd(numerator, denominator)
print(numerator // g, denominator // g)

输入 18 24，输出 3 4。本例要求分母为正；若允许负分母，先把符号移动到分子。若分母为 0，数学上不能作为普通分数。

22.4 自编例题 2：给定 GCD 和 LCM 反求配对

设目标 GCD 为 g、LCM 为 l，写成 P=gx、Q=gy。必须 x、y 互质，且 x*y=l/g。若 l 不能被 g 整除，无解。

令 product=l//g，只枚举 d 到平方根，若 d 整除 product，再检查 d 和 product//d 是否互质。不同的一对因子贡献两个有序对；相同因子只贡献一个。这样使用了枚举与 GCD，不需要突然引入未学的质因数分解定理。

例如 g=2、l=12，product=6；互质因子对为 1/6 与 2/3，得到 (2,12),(12,2),(4,6),(6,4) 共 4 个有序对。

22.5 进制：位权与反复取余

十进制的 307 是 3*10²+0*10+7；二进制的 1011 是 1*2³+0*2²+1*2+1=11。每位的权重来自进制的幂。

从高位往低位计算时，可反复“旧结果乘进制，再加当前位”。从十进制转出时，每次取 n%base 得到最低位，再 n//=base 去掉这一位，最后反序。

代码文件：t22_base_conversion.py

def to_base(n, base):
    # 前提：n >= 0，2 <= base <= 36
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if n == 0:
        return "0"
    answer = []
    while n > 0:
        answer.append(digits[n % base])
        n //= base
    return "".join(answer[::-1])

例 3： 26 转二进制，余数依次 0、1、0、1、1，反向得到 11010。0 必须单独返回 "0"，否则循环不执行会得到空串。

Python 可用 int(text,base) 把合法的 2–36 进制字符串转为整数；bin(n)、oct(n)、hex(n) 分别生成带 0b、0o、0x 前缀的表示。非负数只要数字部分时可以切掉前两个字符；负数还有负号，不能无条件对所有数都 [2:]。

22.6 高精度：通常不用另写 BigInteger

Python 的 int 可直接做大整数加、减、乘、整除、比较与取余，通常不用翻译 Java BigInteger 的方法调用。例如两行大整数相加，仍然只需两个 int(input()) 再相加。

例 4： 求 100!，用第 8 章的 factorial 函数即可。位数很大时，运算和输出都会变慢；“没有固定 int/long 溢出”不是“无限免费”。

某些 Python 环境会限制超长十进制字符串与整数之间的转换，以防异常资源消耗。遇到相关 ValueError 时先确认数值位数与评测要求，不应误判为普通整数溢出。处理可信竞赛输入时可以按官方文档调整配置，附录给出核对入口；不要把解除限制的代码无条件带到处理不可信请求的服务中。

22.7 平台练习

入门｜力扣 1979｜找出数组的最大公约数
训练重点与提示：题目实际求的是数组最小值与最大值的 GCD，不是所有元素的整体 GCD；先读清对象。未开始

入门｜洛谷 P1601｜A+B Problem（高精）
训练重点与提示：直接用 Python 大整数加法。注意输入是两行，输出不加说明。未开始

巩固｜洛谷 P1143｜进制转换
训练重点与提示：先 int(text,source_base)，再用本章 to_base 转到目标进制；字母大小写按题面。未开始

提高｜洛谷 P1029｜最大公约数和最小公倍数问题
训练重点与提示：先判断 l%g，再枚举 product=l//g 的因子对并检查互质；有序对的两个方向要计数。未开始

第23章 素数、筛法、取模、快速幂与位运算

先修：第 22 章、循环和列表。 位运算为选学，不影响先掌握本章前半部分。

23.1 单个数是否为素数

素数是大于 1、正约数只有 1 和自身的整数。0、1 都不是素数。若 n 是合数，可以写成两个大于 1 的因子相乘，其中至少一个不超过平方根，否则乘积就超过 n。

代码文件：t23_prime.py

def is_prime(n):
    if n < 2:
        return False
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            return False
        divisor += 1
    return True

例 1： 49 会在 divisor=7 时判断为合数，所以条件必须包含等号。2 的循环不执行，正确返回 True。只要发现一个因子就可提前返回 False，不需要继续枚举。

时间 O(√n)，空间 O(1)。用整数乘法比较避免浮点平方根在大数边界上的精度问题。math.isqrt(n) 也能求非负整数平方根的向下取整值。

23.2 很多个查询：埃氏筛先做一张表

要知道 0 到 n 每个数是不是素数，没必要对每个数独立试除。先把 2 以上都当作候选；遇到一个还没被删掉的数 p，就把它的倍数删掉。小于 pp 的倍数已经有更小因子处理过，从 pp 开始即可。

代码文件：t23_sieve.py

def sieve(n):
    # 前提：n >= 0；返回 0..n 的素数标记
    prime = [True] * (n + 1)
    prime[0] = False
    if n >= 1:
        prime[1] = False
    p = 2
    while p * p <= n:
        if prime[p]:
            for multiple in range(p * p, n + 1, p):
                prime[multiple] = False
        p += 1
    return prime

例 2： n=12。p=2 删除 4、6、8、10、12；p=3 删除 9、12；剩余 2、3、5、7、11。不是从 1 开始筛，也不能把 p 自己删除。

常用分析为 O(n log log n) 时间、O(n) 空间。Python 布尔列表实际是列表元素引用，不是一格一位的位图；很大上界时需要关注内存。

23.3 选学：较省内存的标记表

bytearray 是可修改的字节数组，每项是 0–255 的整数。用于真假标记时只放 0、1，比 Python 列表保存布尔引用更紧凑。bytearray([1])*(n+1) 建立一排 1。

扩展切片 flag[start:stop:step] 选中等间隔位置；给它赋值时，新内容长度必须与选中的位置数量相同。b"\x00" 是一个值为 0 的字节，乘以 count 得到 count 个零字节。

代码文件：t23_compact_sieve.py

def compact_sieve(n):
    # 前提：n >= 0；返回 0..n 的 0/1 标记
    flag = bytearray([1]) * (n + 1)
    flag[0] = 0
    if n >= 1:
        flag[1] = 0
    p = 2
    while p * p <= n:
        if flag[p]:
            start = p * p
            count = (n - start) // p + 1
            flag[start:n + 1:p] = b"\x00" * count
        p += 1
    return flag

这是同一算法的表示与批量赋值优化，不是新素数原理。切片右侧也产生临时内存，但整体仍为 O(n)。先学会布尔列表版本，再使用它。

23.4 取模不等于随便把每一步都改成余数

对正模数 mod，加法、减法、乘法可以先取模再组合，因为这些操作保持同余关系。例如 (a*b)%mod 等于 ((a%mod)*(b%mod))%mod。

但大小比较和普通除法不能这样直接替换。8 比 5 大，可模 7 后 1 比 5 小；(a//b)%mod 一般也不等于 (a%mod)//(b%mod)。

模意义下的除法涉及“逆元”：例如模 7 时，3*5 的余数为 1，所以 5 是 3 的逆元。并不是每个数在每个模数下都存在逆元。本书基础模板不把未证明条件的模逆元公式作为普通除法使用。

Python 对正模数的 % 已返回非负余数，例如 (-1)%7=6，不需要照搬 Java 的二次修正写法。

23.5 快速幂：每轮把指数减半

求 a^exponent % mod，不先制造完整的巨大 a**exponent。指数为偶数时，可把 a 平方、指数减半；为奇数时，先把一个 a 乘到答案，再做同样处理。

代码文件：t23_fast_power.py

def mod_power(a, exponent, mod):
    # 前提：exponent >= 0，mod > 0
    answer = 1 % mod
    a %= mod
    while exponent > 0:
        if exponent % 2 == 1:
            answer = answer * a % mod
        a = a * a % mod
        exponent //= 2
    return answer

例 3： 求 3^5 mod 7。初始 answer=1、a=3、指数5；奇数，答案变3，底数平方余2，指数2；偶数，答案不变，底数变4，指数1；奇数，答案变3*4 mod7=5，指数归零，返回5。

指数每轮减半，所以只有 O(log exponent) 轮；每轮乘法本身还与模数位数相关。answer=1%mod 可以正确处理 exponent=0、mod=1 的边界。

标准库内置函数 pow(a,exponent,mod) 已提供高效模幂，比赛通常直接使用；手写模板用于理解。只有两个参数的 pow(a,b) 才是普通幂，不要混淆。

23.6 选学：二进制位操作

非负整数可以写成二进制，每一位是 0 或 1。& 是按位与，两位都 1 才为 1；| 是按位或，至少一个 1 就为 1；^ 是按位异或，不同为 1、相同为 0。

第 k 位从最低位起编号 0，可用 (x>>k)&1 取出；x&1 看最低位，因此可判断奇偶。新手不熟悉时仍可写 x%2，快速幂并不必须使用位运算。

例 4：除一个数外其余均出现两次。 异或满足 x^x=0、x^0=x，顺序可以交换，全部异或后成对的数消去。

代码文件：t23_xor_unique.py

def single_by_xor(a):
    # 前提：恰有一个数出现一次，其他每个数恰好出现两次
    answer = 0
    for x in a:
        answer ^= x
    return answer

例 5：非负整数中有多少个二进制 1。 不需要新技巧，反复累加 x%2 并 x//=2。或者在已学位运算后使用 x&1、x>>=1。不要对负数直接套“右移直到 0”，负数的符号扩展可能让循环不能归零。

23.7 平台练习

入门｜洛谷 P5736｜【深基7.例2】质数筛
训练重点与提示：对每个输入调用 is_prime，保留原顺序；本题 n 较小，也可预先筛到最大值。未开始

巩固｜洛谷 P5723｜【深基4.例13】质数口袋
训练重点与提示：素数判断＋累计和模拟；下一个素数装不下时停止，并输出已装个数。未开始

提高｜力扣 204｜计数质数
训练重点与提示：问严格小于 n 的素数数量，不包含 n；n 很大时优先考虑本章紧凑筛法，先处理 n<2。未开始

巩固｜洛谷 P1226｜【模板】快速幂
训练重点与提示：模幂；题目要求输出 a^b mod p=s 这种特定字符串格式，不能只输出结果数字。未开始

选学巩固｜力扣 136｜只出现一次的数字
训练重点与提示：只在“其余恰好两次”的前提下使用全部异或；不用额外计数字典。未开始

选学巩固｜力扣 191｜位 1 的个数
训练重点与提示：反复检查最低位并右移；使用题目规定的非负或正整数输入范围。未开始

第24章 递归：函数暂停，解决更小的问题

先修：函数、return、栈。 递归不是背一句“自己调用自己”，而是设计规模变小且能停止的过程。

24.1 三件事先写清

每个递归函数要明确：这一层负责什么；什么时候可以直接回答；如何把问题交给规模更小的同类问题。规模如果不变，就可能无限调用。

例 1：阶乘。 n! 可以写成 n*(n-1)!，0! 定义为 1。

代码文件：t24_factorial.py

def factorial_recursive(n):
    # 前提：n >= 0；只用于小规模递归教学
    if n == 0:
        return 1
    smaller = factorial_recursive(n - 1)
    return n * smaller

调用 f(3) 时，当前层先暂停等待 f(2)；f(2) 等待 f(1)；f(1) 等待 f(0)；f(0) 返回 1。随后逐层恢复：f(1)=1，f(2)=2，f(3)=6。

这些暂停的调用存在“调用栈”里，最后暂停的先恢复，正是第 21 章后进先出的规律。每层的 n 都是各自的局部值，不是一个共享 n 被反复改坏。

24.2 返回之后还会做什么

def show(n):
    if n == 0:
        return
    print("enter", n)
    show(n - 1)
    print("leave", n)

show(3)

输出顺序：enter 3、enter 2、enter 1、leave 1、leave 2、leave 3。递归调用结束后，当前层会继续执行调用语句后面的代码，除非当前层自己 return。

这就是回溯中“递归回来后撤销选择”的基础。不要以为调用了下一层，当前层就永久消失。

24.3 自编例题 2：递归求列表后缀和

代码文件：t24_suffix_sum.py

def suffix_sum_recursive(a, index):
    # 前提：0 <= index <= len(a)，小规模教学
    if index == len(a):
        return 0
    return a[index] + suffix_sum_recursive(a, index + 1)

对 [4,2,7] 从 index=0 开始，拆为 4 + (2 + (7 + 0))=13。本例不使用 a[1:] 每次切片，避免产生重复复制。但即使如此，循环求和仍然更直接，也没有递归深度风险。

24.4 递归深度与重复计算

Python 对递归层数有限制。把 sys.setrecursionlimit 调很大，不会让系统栈、内存或执行环境变成无限，也不保证所有实现都安全。递归很深的图、链、网格优先用显式栈或队列，后文会给迭代模板。

同一个子问题如果被反复计算，递归可能很慢。例如直接递归斐波那契会多次计算 f(n-2)、f(n-3) 等。第 30 章将先用表存结果，再讲动态规划；现在不要求靠提高递归上限解决速度问题。

24.5 本章练习

回到第 8 章 P5739，完成“不使用 for/while”的递归挑战。再做三道自编题：① 递归打印 1 到 n（把 print 放在递归调用后）；② 递归打印 n 到 1（放在调用前）；③ 判断给出的递归是否每次让参数接近终止条件。

过关标准： 能不运行代码，画出 f(3) 的调用与返回顺序；能解释“调用栈”和“显式列表栈”解决的是相似的暂存问题。

第25章 回溯：做选择、进入下一层、撤销选择

先修：递归、列表复制、布尔标记、枚举。 回溯用于系统地生成并检查许多可能方案，常见规模是较小的 n。

25.1 子集：每个元素选或不选

对 [2,5]，方案有空集、只选 2、只选 5、都选。令 dfs(index) 决定从下标 index 往后如何选择；path 保存已经选好的元素。

代码文件：t25_subsets.py

def subsets(a):
    # 前提：a 的元素互不相同；返回所有子集
    result = []
    path = []

    def dfs(index):
        if index == len(a):
            result.append(path.copy())
            return
        dfs(index + 1)  # 不选当前元素
        path.append(a[index])
        dfs(index + 1)  # 选择当前元素
        path.pop()  # 撤销本层刚加入的选择

    dfs(0)
    return result

返回顺序为 [[],[5],[2],[2,5]]，不一定与其他写法的顺序相同；如果题目不要求顺序，这并不影响正确性。

为什么 path.copy？ 如果写 result.append(path)，保存的是同一个可变列表的引用，之后 pop 会影响已经保存的方案。这里应保存当前内容的独立快照。

为什么必须 pop？ 做完“选 2”的一条分支后，其他分支不能继续带着之前的选择。撤销应与添加一一对应。

共有 2^n 个子集，完整收集方案的输出规模本身可达 O(n*2^n)，因此不能只说 O(2^n) 就忽略复制与存储。递归路径额外 O(n)，返回结果另计。

25.2 全排列：每个位置放一个尚未用过的数

排列考虑顺序，[2,5] 与 [5,2] 是不同排列。used[i] 记录第 i 个原元素是否已出现在当前路径中。

代码文件：t25_permutations.py

def permutations(a):
    # 前提：元素互不相同
    result = []
    path = []
    used = [False] * len(a)

    def dfs():
        if len(path) == len(a):
            result.append(path.copy())
            return
        for i in range(len(a)):
            if used[i]:
                continue
            used[i] = True
            path.append(a[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

例 2： [1,2,3] 先得到 123，回退最后一层；接着换成 132，再回退第一层改放 2，依次生成 213、231、312、321。每次回退都恢复 path 和 used 两种状态。

同一个值在输入中重复时，这个模板会生成重复排列；不能声称它自动去重。去重排列需要额外的同层跳过规则，本书主线先用互不相同的输入。

收集全部排列需 O(n*n!) 时间和输出空间；递归与标记本身 O(n)。n=10 时已有 3628800 个排列，要考虑输出规模，而不只是程序能不能递归。

25.3 组合：选择 k 个，顺序不重要

从 1 到 n 选 k 个，只按递增顺序选择，就不会同时生成 [1,2] 和 [2,1]。start 表示下一次允许选择的最小数。

代码文件：t25_combinations.py

def combinations(n, k):
    # 前提：n >= 0，k >= 0
    result = []
    path = []

    def dfs(start):
        if len(path) == k:
            result.append(path.copy())
            return
        need = k - len(path)
        last_start = n - need + 1
        for value in range(start, last_start + 1):
            path.append(value)
            dfs(value + 1)
            path.pop()

    dfs(1)
    return result

例 3： n=4、k=2，结果为 12、13、14、23、24、34。还缺 need 个数时，当前起点最多到 n-need+1，否则后面数量不够，这叫剪枝：提前排除不可能完成的分支。

剪枝必须有理由，不能因为某个值“看起来不合适”就随意跳过。k=0 时返回 [[]]，表示一种什么也不选的方案；k>n 时没有方案，返回 []。

25.4 搜索中的状态分别归谁

path 是当前分支共享的一条工作路径，所以进入/退出时修改和恢复；result 是最终输出，应该累计而不是回退；used 是本条排列路径的占用标记，不能错误地“一个值在全局用过就永远不再用”。

这与后面的图搜索 visited 不同：图的连通性遍历通常希望一个节点全程只访问一次，而回溯要探索同一个位置在不同方案中的选择。不要把两个模板的标记恢复规则机械混用。

25.5 平台练习

入门｜力扣 78｜子集
训练重点与提示：子集包含空集，保存 path.copy；本题元素互异，符合模板前提。未开始

巩固｜力扣 77｜组合
训练重点与提示：组合用 start 防止顺序重复，理解剩余数量剪枝。未开始

巩固｜力扣 46｜全排列
训练重点与提示：排列用 used 标记原下标，递归返回时恢复 used 和 path。未开始

提高｜洛谷 P1706｜全排列问题
训练重点与提示：输出 1 到 n 的全排列，注意题目要求每个数字保留指定场宽，可用第 6 章的 f-string 宽度格式；大量方案更适合生成后及时输出而不是全部常驻内存。未开始

第26章 图是什么：先把关系存下来

先修：列表、二维列表、元组、排序。 本章不急着搜索，先把题目中的“关系”变成可以遍历的数据。

26.1 顶点、边与方向

图由顶点和边组成。顶点也叫节点，可以表示城市、学生、课程或一个状态；边表示两个节点之间允许发生的连接或移动。通常用 n 表示节点数、m 表示输入边数。

无向边 u—v 表示两个方向都能走；有向边 u→v 只允许从 u 走到 v。带权边还附带一个数，例如距离、时间或费用。权值是代价，不是节点编号。

例 1： 四个节点编号 0、1、2、3，无向边为 (0,1)、(0,2)、(2,3)。0 的邻居是 1、2；3 的邻居只有 2。从 1 到 3 的一条路径是 1→0→2→3，经过 3 条边、4 个节点。最短“步数”通常数边，不是数节点。

路径是连续经过若干条边得到的节点序列。连通表示存在路径，不是必须有一条直接边。无向图中的一个连通块，是一组彼此能够到达、且不能再扩展的节点。没有任何边的节点也单独构成一个连通块。有向图的可达性有方向，不能照搬无向连通块的定义。

环表示绕若干条边后回到原处。树是一种连通且无环的无向图；n 个节点的树有 n−1 条边。选定根节点后，可把通往根的相邻节点称为父节点，其余向下相邻节点称为子节点。树不是必须“每个节点只有两个孩子”；那是二叉树额外的限制。本书的图模板也能表示一般树。

26.2 邻接矩阵：二维表格

用 matrix[u][v] 表示 u 到 v 是否有直接边，1 表示有、0 表示无。

n = 4
matrix = [[0] * n for _ in range(n)]
edges = [(0, 1), (0, 2), (2, 3)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1

matrix[1][3] 是 0，但从 1 到 3 仍然有路径。矩阵存的是直接关系，不是所有可达关系。

矩阵需要 O(n²) 空间，检查一条直接边为 O(1)，枚举一个节点的全部邻居则要扫描一整行 O(n)。n=100000 时，n² 个位置无法作为普通 Python 二维列表存储。不要因为矩阵形式直观就忽略规模。

带权图不能总把 0 当作“没有边”，因为边权可能恰好为 0；应单独用 None 等标记不存在，或改用邻接表。

26.3 邻接表：每个节点保存自己的邻居

代码文件：t26_graph.py

def build_graph(n, edges, directed=False):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph


def build_weighted_graph(n, edges, directed=False):
    graph = [[] for _ in range(n)]
    for u, v, weight in edges:
        graph[u].append((v, weight))
        if not directed:
            graph[v].append((u, weight))
    return graph

例 2： 对 26.1 的边调用 build_graph(4, edges)，得到 [[1,2],[0],[0,3],[2]]。外层下标是“当前节点是谁”，内层每个整数是“可以直接走到谁”。

带权邻接表里的 (v, weight) 是一个二元组：第一个数是邻居，第二个数才是边权。遍历写成 for v, weight in graph[u]:，用的是第 7、9 章已经讲过的解包。

无向图输入 m 条边，通常保存 2m 个邻接记录；有向图通常保存 m 个。邻接表空间 O(n+m)，遍历全部节点和全部邻接记录也是 O(n+m)。平行边指同一对端点间有多条边；本模板原样保留，不擅自去重。

26.4 编号转换与常见错误

题面节点为 1 到 n 时，可读入后执行 u -= 1; v -= 1，内部统一 0 到 n−1，输出编号时再加 1。另一种方法是建立 n+1 个位置并空着 0；两种都可以，但同一份代码必须统一。

绝不能写 graph = [[]] * n：所有位置会共用同一个内层列表。不要把“所有边按输入顺序存下来”误认为“邻居已经按编号排序”。题目要求优先访问较小编号时，必须逐行排序：

for neighbors in graph:
    neighbors.sort()

本章自检。 建立有向边 (0,1)、(2,0)，回答 graph[0]、graph[1]、graph[2] 各是什么。答案依次为 [1]、[]、[0]。从 1 能否顺着有向边到 0？不能。正式可达性练习放在下一章，不要求现在凭空写搜索。

第27章 图搜索：DFS、BFS 与无权最短路

先修：第 21 章栈和队列、第 24 章递归、第 26 章邻接表。 本章模板用显式栈或队列，避免把很深的图交给 Python 递归栈。

27.1 为什么需要 visited

在无向边 0—1 中，从 0 走到 1 后还能走回 0。如果不记录已经处理的节点，程序就可能反复绕圈。visited[u] 是布尔值，表示节点 u 是否已经被发现或处理；具体标记时机必须与模板配套。

深度优先搜索 DFS 的直觉是“先沿一个分支往深处走，再回来探索其他分支”；广度优先搜索 BFS 的直觉是“先看一步能到的，再看两步能到的”。两者都能判断可达性，但只有 BFS 的分层顺序直接保证无权最短步数。

27.2 用栈判断哪些点可达

代码文件：t27_reachable.py

def reachable_nodes(graph, start):
    visited = [False] * len(graph)
    visited[start] = True
    stack = [start]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)
    return visited

入栈时立刻标记，使每个节点最多入栈一次。每条邻接记录最多扫描一次，时间 O(n+m)，额外空间 O(n)。

这个简单模板保证可达性结果正确，但我们不承诺它的输出顺序等同于某个递归 DFS 的先序顺序。遍历顺序是题目要求的一部分时，必须认真处理“何时标记”和邻居先后次序。

27.3 需要精确模拟递归顺序时

递归在访问完一个孩子后，要回到父节点继续下一个孩子。显式栈可以保存 (节点, 下一个待检查邻居的下标)，相当于保存每次调用进行到哪里。

代码文件：t27_dfs_order.py

def dfs_preorder(graph, start):
    visited = [False] * len(graph)
    visited[start] = True
    order = [start]
    stack = [(start, 0)]
    while stack:
        u, index = stack[-1]
        if index == len(graph[u]):
            stack.pop()
            continue
        stack[-1] = (u, index + 1)
        v = graph[u][index]
        if not visited[v]:
            visited[v] = True
            order.append(v)
            stack.append((v, 0))
    return order

例 1： graph=[[1,2],[3],[],[]]。先记录 0，进入 1，再进入 3；3 没有邻居，退回 1；1 也结束，退回 0；最后访问 2。结果 [0,1,3,2]。栈顶的 index 增加，表示“这条边已经检查过，下次从下一条继续”，不是修改原图。

27.4 BFS 为什么能求最少边数

初始只有起点，距离 0。起点的未访问邻居距离为 1；它们进入队尾。队列先处理所有距离为 1 的节点，再处理距离为 2 的节点。因此一个节点第一次被发现时，不可能存在尚未处理的更短层数通向它。

代码文件：t27_bfs.py

from collections import deque


def bfs_distances(graph, start):
    n = len(graph)
    distance = [-1] * n
    parent = [-1] * n
    distance[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent


def restore_path(parent, start, target):
    # parent 必须来自以上 BFS；start 的 parent 为 -1
    path = []
    current = target
    while current != -1:
        path.append(current)
        if current == start:
            path.reverse()
            return path
        current = parent[current]
    return []

distance 同时表示距离与访问状态，−1 专门表示未到达。parent[v] 记录第一次发现 v 时从哪个节点走来；从终点不断找 parent，得到反向路径，再反转。多个最短路径同时存在时，本模板返回其中一条，不额外保证字典序最小。

例 2： 无向边 (0,1),(0,2),(1,3),(2,3)，另有孤立点 4。起点 0 的距离为 [0,1,1,2,-1]；若先扫描 1，再扫描 2，节点 3 的 parent 为 1，恢复路径 [0,1,3]。起点等于终点时路径只有一个节点，距离为 0。

入队时就写 distance，不能等出队时才标记，否则同一个节点可能被很多前驱重复加入队列。边权不相同时，“最少边数”未必是“最小总权值”；第 36 章再处理非负带权最短路。

27.5 连通块与隐式图

无向图可能从一个起点走不遍。对所有节点循环：遇到未访问节点，就计数加一，并从它出发标记整个连通块。每个节点仍只处理一次，总复杂度不变。

代码文件：t27_components.py

def count_components(graph):
    # 前提：graph 是无向图
    visited = [False] * len(graph)
    count = 0
    for start in range(len(graph)):
        if visited[start]:
            continue
        count += 1
        visited[start] = True
        stack = [start]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
    return count

有些题没有直接给边：例如楼层 i 可以到 i+step[i] 或 i-step[i]。这叫隐式图，只需在取出 i 后计算合法邻居，不必预先建完整邻接表。合法范围、相同状态判重、每步代价为 1，这三件事与普通 BFS 完全相同。

27.6 平台练习

入门｜力扣 1971｜寻找图中是否存在路径
训练重点与提示：无向图的可达性，建立邻接表后从 source 搜索，返回 visited[destination]。未开始

巩固｜力扣 547｜省份数量
训练重点与提示：输入已是邻接矩阵；可以直接扫描每行，或先转换为邻接表，再用连通块计数。未开始

巩固｜洛谷 P1135｜奇怪的电梯
训练重点与提示：把楼层当节点，按本章隐式图方法生成两个候选楼层，用 BFS 求最少按钮次数；越界不入队。未开始

提高｜洛谷 P5318｜【深基18.例3】查找文献
训练重点与提示：有向图，从编号 1 出发；每个节点的邻居先排序，用本章精确 DFS 模板与 BFS 分别生成访问顺序，两个过程的访问状态必须独立。数据较大，重点检查输入和内存。未开始

第28章 网格搜索、迷宫与多源 BFS

先修：第 5 章二维列表、第 27 章图搜索。 网格并不是新的一类神秘结构：每个可进入的格子就是一个节点，合法移动就是边。

28.1 行列、方向与边界

坐标 (r,c) 中 r 是行、c 是列。向下行号加 1，向右列号加 1。四方向为 (-1,0),(1,0),(0,-1),(0,1)；八方向还包括四个对角线。方向是否允许，必须读题，不能用“常见模板”替题目决定。

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
    nr = r + dr
    nc = c + dc
    # 先确认 0 <= nr < n 且 0 <= nc < m，才能访问 grid[nr][nc]

Python 的负下标会从末尾取元素，因此 grid[-1][0] 往往不会报错，而是悄悄取到最后一行。网格算法中更要先判边界。

28.2 数连通区域与求面积

代码文件：t28_island_areas.py

def island_areas(grid):
    # 前提：矩形网格，整数 1 是陆地、整数 0 是水；四方向连通
    if not grid or not grid[0]:
        return []
    n = len(grid)
    m = len(grid[0])
    visited = [[False] * m for _ in range(n)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    areas = []
    for r in range(n):
        for c in range(m):
            if grid[r][c] != 1 or visited[r][c]:
                continue
            visited[r][c] = True
            stack = [(r, c)]
            area = 0
            while stack:
                x, y = stack.pop()
                area += 1
                for dx, dy in directions:
                    nx = x + dx
                    ny = y + dy
                    if not (0 <= nx < n and 0 <= ny < m):
                        continue
                    if grid[nx][ny] == 1 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        stack.append((nx, ny))
            areas.append(area)
    return areas

例 1： [[1,1,0],[0,1,0],[1,0,1]] 的区域面积是 [3,1,1]，所以岛屿数为 3，最大面积为 3。左下角与中间陆地只是斜着相邻，在四方向规则下不属于同一岛屿。

外层循环负责“找到一个尚未统计的岛”；内层栈负责“统计完整个岛”。area 每进入一个格子加 1，不是遇见每条相邻边就加 1。每个格子最多访问一次，时间 O(nm)，额外空间 O(nm)。修改原网格也能代替 visited，但本模板保留输入，方便复用与测试。

28.3 迷宫最短步数

这里明确约定：'#' 是墙，其余字符可以进入；每次四方向移动一步；起终点为 0-based 坐标。模板返回最少移动次数，不可达返回 −1。

代码文件：t28_maze_bfs.py

from collections import deque


def maze_distance(grid, start, target):
    if not grid or not grid[0]:
        return -1
    n = len(grid)
    m = len(grid[0])
    sr, sc = start
    tr, tc = target
    if not (0 <= sr < n and 0 <= sc < m):
        return -1
    if not (0 <= tr < n and 0 <= tc < m):
        return -1
    if grid[sr][sc] == '#' or grid[tr][tc] == '#':
        return -1
    distance = [[-1] * m for _ in range(n)]
    distance[sr][sc] = 0
    queue = deque([(sr, sc)])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        r, c = queue.popleft()
        if (r, c) == (tr, tc):
            return distance[r][c]
        for dr, dc in directions:
            nr = r + dr
            nc = c + dc
            if not (0 <= nr < n and 0 <= nc < m):
                continue
            if grid[nr][nc] == '#' or distance[nr][nc] != -1:
                continue
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))
    return -1

例 2： grid=['...','##.','...']，从 (0,0) 到 (2,0)，唯一通路先向右、再向下、再向左，共 6 步；不能直接沿第一列穿墙。起终点同为可走格时返回 0。

换成马的移动，只改方向为 (±1,±2)、(±2,±1) 共八种组合，不能使用普通八邻域代替。题目要求所有格子距离时，不在某个终点提前返回，最后输出 distance。

28.4 多个起点同时扩散

求每个格子到最近起点的距离，不需要从每个起点分别跑一遍 BFS。先把所有起点以距离 0 加入同一个队列，再执行一次 BFS；第一波向外走一步，第二波向外走两步，最先到达者自然来自最近源。

代码文件：t28_multi_source.py

from collections import deque


def nearest_source_distances(passable, sources):
    # passable[r][c] 为 True/1 表示可走，False/0 表示障碍
    if not passable or not passable[0]:
        return []
    n = len(passable)
    m = len(passable[0])
    distance = [[-1] * m for _ in range(n)]
    queue = deque()
    for r, c in sources:
        if not (0 <= r < n and 0 <= c < m):
            continue
        if passable[r][c] and distance[r][c] == -1:
            distance[r][c] = 0
            queue.append((r, c))
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr = r + dr
            nc = c + dc
            if not (0 <= nr < n and 0 <= nc < m):
                continue
            if not passable[nr][nc] or distance[nr][nc] != -1:
                continue
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))
    return distance

例 3： 一行 5 格全部可走，起点为第 0、4 格，距离为 [0,1,2,1,0]。起点已全部排在队列中，任何一个起点都不需要等待另一个起点扩散完。

本模板把“能否走”和“是不是源”分开，防止题意冲突：01 矩阵求最近 0 时，0 和 1 都能走，0 是源；腐烂橘子题中，0 是空地不能传播，2 是源，1 是待传播位置。两道题都含 0，但语义完全不同。

腐烂时间的答案是所有原本新鲜格子的距离最大值；若其中有 −1 则无法全部腐烂；原本没有新鲜橘子时答案为 0。封闭区域则可反过来想：从边界上的空格出发，能走到的是外部；未到达的空格才是被包围区域。

28.5 平台练习

入门｜力扣 200｜岛屿数量
训练重点与提示：统计岛屿数。此题网格元素是字符串 '1' 和 '0'，必须把模板判断改为字符比较，不能拿整数 1 去比。未开始

巩固｜力扣 695｜岛屿的最大面积
训练重点与提示：此题网格是整数 0/1，可以直接用面积模板；没有陆地时最大面积应为 0。未开始

巩固｜洛谷 P1443｜马的遍历
训练重点与提示：马有八种跳法，输出每个位置的最短步数；统一题面 1-based 坐标与内部 0-based。未开始

巩固｜力扣 542｜01 矩阵
训练重点与提示：把所有 0 同时设为源，所有格子都可走；不要把 0 错当成墙。未开始

提高｜力扣 994｜腐烂的橘子
训练重点与提示：多源扩散后只统计原新鲜橘子，分别处理不可达、没有新鲜橘子、正常传播三种情况。未开始

提高｜洛谷 P1162｜填涂颜色
训练重点与提示：先搜索边界能到达的 0，剩余未标记的 0 才需要填色；不必猜测某一个内部起点。未开始

第29章 并查集：动态合并集合

先修：列表、函数、第 10 章最小类语法、图的连通性。 并查集回答“是否属于同一个集合”，不负责告诉你具体经过哪些边。

29.1 代表与父指针

最初每个节点各自成一个集合。parent[x] 记录向集合代表走的下一站；如果 parent[x] == x，x 就是这个集合的根。find(x) 沿父指针向上找根。两个节点根相同，就属于同一集合。

union(a,b) 不是简单执行 parent[a]=b，而是先找到两个根，再把一个根挂到另一个根下。随意修改非根节点可能把集合拆坏，也不能可靠判断原本是否已经连通。

29.2 完整模板与每个字段的意义

这里使用 class 只是把相关列表和函数放在一起。self.parent 是这一个并查集对象的父指针列表；self.size 是根所代表的集合大小；self.components 是当前集合数。DSU(n) 会调用 __init__，建立 n 个独立集合。

代码文件：t29_dsu.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)

find 中的路径折半把当前节点直接挂到祖父节点上，使后续查找更短；全程迭代，不依赖递归深度。按大小合并把小集合挂到大集合根上，避免无谓长链。size 只有根位置的值需要保持正确，查询集合大小应写 dsu.size[dsu.find(x)]，不能直接读任意 size[x]。

29.3 手算一次合并过程

例 1： dsu=DSU(5)，初始 components=5。执行 union(0,1)，成功合并，集合为 {0,1},{2},{3},{4}，components=4。再 union(1,2)，先把 1 找到根 0，因此得到 {0,1,2},{3},{4}，components=3。再 union(0,2)，两者根已相同，返回 False，components 仍为 3。

# 此演示接在上面的 DSU 定义之后运行
sample = DSU(5)
print(sample.union(0, 1))  # True
print(sample.union(1, 2))  # True
print(sample.union(0, 2))  # False
print(sample.same(0, 2))  # True
print(sample.components)  # 3

例 2：冗余边。 无向图按顺序加入边。若加入 (u,v) 前 u、v 已经连通，那么新边会形成一个环，union 返回 False 正好可以捕捉这一点。如果题目有多条冗余边、要求第一条或最后一条，要按题目更新答案，而不是见到一条就机械停止。

同时使用路径压缩与按大小合并时，一长串操作的平均摊还代价极低，常写 O(α(n))；α 是增长极慢的反阿克曼函数，入门无需推导，但不要把最坏单次查询严格写成永远 O(1)。空间 O(n)。

29.4 什么问题不该直接用并查集

有向图中 a 能到 b，不意味着 b 能到 a，因此普通并查集不能直接回答有向可达性。它也不提供最短路，不擅长直接删除边、拆分集合。删除操作有时可以离线倒序变成加边，但必须先有完整操作记录并证明逆序对应关系，本书不要求新人凭空套用。

29.5 平台练习

入门｜洛谷 P3367｜【模板】并查集
训练重点与提示：操作分为合并与查询，节点编号统一后调用 union/same；输出按题面要求使用 Y 或 N。未开始

巩固｜洛谷 P1551｜亲戚
训练重点与提示：亲戚关系具有传递性，先把已知关系合并，再回答查询。未开始

巩固｜力扣 684｜冗余连接
训练重点与提示：无向图加边时根已相同则形成环，使用 union 的布尔返回值；按题意保留需要删除的那条边。未开始

第30章 动态规划入门：先说清楚 dp 的含义

先修：循环、列表、函数、递归。 动态规划简称 DP。不是只要创建名为 dp 的数组就叫学会 DP；关键是把重复的子问题归纳成有限状态，并按依赖顺序计算。

30.1 从重复递归走向保存结果

斐波那契数定义 F(0)=0、F(1)=1、F(n)=F(n-1)+F(n-2)。直接递归算 F(5)，会算 F(4) 和 F(3)；算 F(4) 又会算 F(3)，同一问题重复出现。递归版慢的原因不是“用了函数”，而是反复计算同一个状态。

记忆化搜索是在算过后保存结果，再遇到相同状态直接取出；递推则从最小状态开始主动填表。这两种写法都利用相同的状态关系。本书主线优先递推，既便于看清依赖，也避免深递归。

代码文件：t30_fibonacci.py

def fibonacci(n):
    # 前提：n >= 0
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

例 1： n=6，数组依次确定为 0,1,1,2,3,5,8，最后返回 8。每个 i 只算一次；在普通数值范围下按 O(n) 次状态转移分析，保存 n+1 个状态。若整数位数随 n 很大，大整数加法本身也有位数代价，不能无限期当 O(1)。

30.2 爬楼梯：从“最后一步”推导

自编例题： 从第 0 级出发，每次爬 1 或 2 级，到第 n 级有多少种动作序列？

定义 dp[i] = 恰好到达第 i 级的方案数。最后一步如果爬 1 级，前一步一定在 i−1；如果爬 2 级，前一步一定在 i−2。两种情况按最后一步区分，互不重复，而且覆盖了全部方案，所以相加。

dp[0]=1 表示“不走任何一步”是一种到达 0 的方式；这不是随便填出来的技巧。若写成 0，后续从起点出发的方案会丢失。n=0 时，按本自编题约定答案也是 1。

代码文件：t30_stairs.py

def count_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        if i >= 2:
            dp[i] += dp[i - 2]
    return dp[n]

例 2： n=4，方案为 1111、112、121、211、22，共 5 种。表中 dp[0..4]=[1,1,2,3,5]。注意这不是“选了几枚 1 和 2 的组合数”；112 与 121 的动作顺序不同，应分别计算。

30.3 五个问题缺一不可

“状态”就是足以决定后续计算的必要信息。只记录答案值，不记录当前在哪里，往往无法决定下一步。反过来，把完整历史路径都当状态又会过大。入门先模仿清楚的状态句，再学习缩减信息。

30.4 最小花费：把加法换成 min 之前先改状态

给 cost 列表，从下标 0 或 1 开始，离开台阶 i 要付 cost[i]，一次向上 1 或 2 级，到达下标 n 的楼顶。定义 dp[i] = 到达位置 i 时已经支付的最少费用。开始可直接站在 0 或 1，所以 dp[0]=dp[1]=0。

到 i 的最后一步从 i−1 或 i−2 跳来，因此候选费用是 dp[i-1]+cost[i-1] 和 dp[i-2]+cost[i-2]。本题是最小费用，不是方案数量，用 min 选择更优候选。

代码文件：t30_min_stair_cost.py

def min_stair_cost(cost):
    # 前提：len(cost) >= 2，费用非负
    n = len(cost)
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1],
                    dp[i - 2] + cost[i - 2])
    return dp[n]

例 3： cost=[4,2,7,3]，dp[2]=2、dp[3]=2、dp[4]=5。从 1 出发，支付 2 到 3，再支付 3 到顶，总花费 5。不要把楼顶 n 当成还有一个 cost[n] 的台阶，那会越界。

30.5 什么时候再优化空间

斐波那契每次只需要前两项，所以可以用两个变量滚动保存；但先写对数组，再优化。多重赋值右边先按旧值计算，是第 7 章已讲的规则。

代码文件：t30_fibonacci_rolling.py

def fibonacci_rolling(n):
    previous = 0
    current = 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

这两个变量的含义与上一版 dp 数组不同，不能看见“前两项”就随便排列赋值顺序。若要求恢复整个选择方案，往往需要保留额外状态，不能只保留最终一个数。

30.6 平台练习

入门｜力扣 509｜斐波那契数
训练重点与提示：从确定 F(0)、F(1) 开始，先数组递推，再比较两个变量版本。未开始

入门｜力扣 70｜爬楼梯
训练重点与提示：按最后一步拆分，解释为什么这里的初始状态与斐波那契并不完全相同。未开始

巩固｜力扣 746｜使用最小花费爬楼梯
训练重点与提示：状态是到达位置时已经付的钱，付费发生在离开上一台阶时，答案位置是 n。未开始

第31章 线性 DP：最大子段和与不相邻选数

先修：第 30 章状态、转移、初值。 同样沿数组往右递推，状态含义不同，式子就不同。

31.1 最大子段和为什么要“以当前位置结尾”

求非空连续子数组的最大和。定义 dp[i] = 必须以 a[i] 结尾的非空连续子数组的最大和。为了保持连续，到 i 时只有两种选择：只选 a[i]，或把 a[i] 接到“以 i−1 结尾的最好区间”后面。

转移为 dp[i]=max(a[i],dp[i-1]+a[i])。dp[i] 并不是“前 i 个数中任意区间的最好值”，因此最终还要对所有结尾取最大值。

代码文件：t31_max_subarray.py

def max_subarray(a):
    # 前提：a 非空，要求至少选一个元素
    current = a[0]
    answer = a[0]
    for i in range(1, len(a)):
        current = max(a[i], current + a[i])
        answer = max(answer, current)
    return answer

例 1： a=[−3,4,−1,2,−5]。

答案来自 [4,-1,2]，为 5。例 2： a=[−8,−2,−6]，答案是 −2，不是 0，因为不能选择空子数组。初始化为 a[0] 正是为了遵守这个条件。时间 O(n)，额外空间 O(1)。

31.2 不相邻选数：允许一个也不选

现在不要求连续，反而禁止同时选相邻位置。定义 dp[i] = 只考虑前 i 个元素、允许不选任何元素时的最大总和。这里 i 表示“已经考虑的数量”，对应新元素的下标是 i−1。

不选新元素：答案为 dp[i−1]。选择新元素：前一个不能选，只能接在前 i−2 个元素的最佳结果后，得到 dp[i−2]+a[i−1]。取二者较大。

代码文件：t31_non_adjacent.py

def max_non_adjacent(a):
    n = len(a)
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[1] = max(0, a[0])
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1])
    return dp[n]


def max_non_adjacent_rolling(a):
    two_back = 0
    one_back = 0
    for value in a:
        current = max(one_back, two_back + value)
        two_back = one_back
        one_back = current
    return one_back

例 3： a=[3,8,4,6]，dp 为 [0,3,8,8,14]，选 8 和 6 得到 14。只选当前最大的 8 然后随意删邻居不是完整证明；DP 明确比较了所有合法来源。

本模板允许空选择，因此全负数组返回 0。参考 Java 笔记的常见初始化偏向非负金额场景；本书明确写出空选择规则，不能把不同题目的初值直接混用。题面要求至少选一个时，需要另设“已经选择过”的状态或单独处理全负情况。

31.3 首尾也相邻怎么办

环形排列中，第一个和最后一个不能同时选。每个合法方案至少排除其中一个，因此分别求“不考虑最后一个”的线性问题和“不考虑第一个”的线性问题，取较大值。这两类可能重叠，但求最大值不会因为重复计算而出错。

代码文件：t31_circular_non_adjacent.py

def max_circular_non_adjacent(a):
    if not a:
        return 0
    if len(a) == 1:
        return max(0, a[0])

    def solve(left, right):
        two_back = 0
        one_back = 0
        for i in range(left, right):
            current = max(one_back, two_back + a[i])
            two_back = one_back
            one_back = current
        return one_back

    return max(solve(0, len(a) - 1), solve(1, len(a)))

这里 solve 使用半开区间，不创建切片，额外空间 O(1)。只有一个元素时必须单独处理，否则两个排除区间都为空。

31.4 平台练习

入门｜力扣 53｜最大子数组和
训练重点与提示：严格使用非空区间初始化，自己增加全负、单元素、正负交替三组测试。未开始

巩固｜力扣 198｜打家劫舍
训练重点与提示：本题金额非负，可用不相邻选数模板；先说明 dp[i] 是前 i 个还是以 i 结尾。未开始

提高｜力扣 213｜打家劫舍 II
训练重点与提示：先单独处理只有一间房，再拆成两个线性区间，不允许首尾同时选。未开始

第32章 01 背包：每件物品最多选一次

先修：第 30–31 章 DP、二维列表、倒序 range。 “01”读作“零一”，意思是每件物品只有不选或选一次两种状态。

32.1 先把题目翻译成四个量

n 件物品，每件有重量 weight 和价值 value，背包容量 capacity。总重量不能超过容量，希望总价值最大。耗时与收益、金额与满意度也可以套用这个模型，但前提必须是“每件最多一次”。

定义 dp[i][c] = 只考虑前 i 件物品、容量上限为 c 时，最多能得到的价值。这里容量是上限，不要求恰好用满。允许不选物品，所以第 0 行全为 0。

第 i 件物品实际下标为 i−1：不选时继承 dp[i-1][c]；能装下时，还可以取 dp[i-1][c-weight[i-1]]+value[i-1]。来源都是上一行，因此不会重复拿当前物品。

代码文件：t32_knapsack_2d.py

def knapsack_01_2d(weights, values, capacity):
    # 前提：长度相等，重量是正整数，capacity >= 0
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if c >= weight:
                dp[i][c] = max(dp[i][c],
                               dp[i - 1][c - weight] + value)
    return dp[n][capacity]

例 1： weights=[2,3,4]，values=[3,4,5]，capacity=5。

容量 5 的最好方案是拿前两件，价值 7；第三件价值更大，但并不意味着它必选。时间 O(nC)，二维空间 O(nC)，C 为容量，不是物品数量。

32.2 一维优化为什么必须倒序

只保留一行 dp，更新 dp[c] 时必须读取“当前物品还没处理过”的 dp[c-weight]。容量从大到小走，因为 c−weight 更小，尚未被本轮覆盖，恰好仍是上一轮结果。

代码文件：t32_knapsack_1d.py

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]

例 2：专门看错误。 只有一件重 3、值 5 的物品，容量 6。正确答案最多 5。若容量正序，先更新 dp[3]=5，之后 dp[6] 又读取刚更新的 dp[3] 得到 10，相当于拿了同一件两次。倒序时先计算 dp[6]，读取的旧 dp[3] 还是 0，就不会重复。

这里 range(capacity, weight-1, -1) 包含 weight，不包含 weight−1。不要写成 range(capacity, weight, -1)，那会漏掉恰好装下一件的容量。

32.3 “恰好达到”不能全部初始化为可行

若要求恰好组成 target，状态可以是布尔值：possible[s] 表示是否能从已考虑元素中选出总和 s。初始只有 0 可行，其余必须 False。

代码文件：t32_subset_sum.py

def can_make_sum(numbers, target):
    # 前提：numbers 中均为正整数，target >= 0
    possible = [False] * (target + 1)
    possible[0] = True
    for value in numbers:
        for total in range(target, value - 1, -1):
            possible[total] = (possible[total]
                               or possible[total - value])
    return possible[target]

例 3： numbers=[2,5]，target=4，答案 False：只有一个 2，不能用两次。target=7 为 True。分割成两份等和：先求总和 S；S 为奇数不可能平分；否则检查能否选出 S//2，另一部分自然也是 S//2。

恰好装满并最大化价值时，应把不可达状态设为 None 或负无穷，不能全设 0。因为“价值为 0 的可达方案”和“根本到不了”是两件事。常用 float('-inf') 表示负无穷，它比所有有限数小；只有 dp[0]=0，其余为负无穷，转移前确认来源可达。结果仍为负无穷表示无解。

32.4 方案数量：不是 max，而是相加

每件物品依然最多选一次，ways[s] 表示恰好凑出 s 的选择方案数。空选择是凑出 0 的一种方案，所以 ways[0]=1。处理当前物品时，所有包含它的新方案由“原来凑出 s−value 的方案”增加而来。

代码文件：t32_subset_count.py

def count_subset_sums(numbers, target):
    # 相同数值的不同位置，视为不同物品
    ways = [0] * (target + 1)
    ways[0] = 1
    for value in numbers:
        for total in range(target, value - 1, -1):
            ways[total] += ways[total - value]
    return ways[target]

例 4： 有三件价格分别为 [2,2,3] 的不同物品，要花 4，有一种方案：选两个 2。要花 5，有两种方案：第一个 2 配 3，或第二个 2 配 3。不能擅自对输入去重，因为数值相同不等于物品相同。

32.5 平台练习

入门｜洛谷 P1048｜【NOIP 2005 普及组】采药
训练重点与提示：采药时间是重量，总时间是容量，药材价值是收益，每株最多采一次；先用二维，再改一维。未开始

巩固｜力扣 416｜分割等和子集
训练重点与提示：总和为奇数先返回 False，否则做目标为总和一半的 01 子集和。未开始

巩固｜洛谷 P1164｜小 A 点菜
训练重点与提示：每种菜只有一份，求恰好花完的钱的方案数；价格相同的两种菜仍是不同选择。未开始

第33章 完全背包、最少硬币与方案顺序

先修：第 32 章 01 背包。 完全背包中，每种物品可以使用任意非负整数次。重量必须为正；零重量、正收益会导致无界答案，不能直接套下面的有限模板。

33.1 正序容量有意允许重复使用

代码文件：t33_complete_knapsack.py

def complete_knapsack(weights, values, capacity):
    # 前提：重量为正整数，允许不选，容量为上限
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(weight, capacity + 1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]

本轮 dp[c-weight] 已可能包含当前物品，现在再加一件正是题意允许的操作。例 1： 只有重 3、值 5 的物品，容量 6，先得到 dp[3]=5，再得到 dp[6]=10，这次是正确答案。

时间 O(nC)，空间 O(C)。不要把“01 倒序、完全正序”当成没有理由的口诀：方向控制的是读旧状态，还是允许读本轮的新状态。

33.2 最少硬币：不可达状态要足够大

给正整数面额 coins，每种无限，凑出 amount 所需最少枚数。定义 dp[s] = 恰好凑出 s 的最少枚数。dp[0]=0，其他先设为 amount+1。由于每枚面额至少 1，任何可行最少方案不会超过 amount 枚，所以 amount+1 可安全表示“不可能”。

代码文件：t33_min_coins.py

def minimum_coins(coins, amount):
    unreachable = amount + 1
    dp = [unreachable] * (amount + 1)
    dp[0] = 0
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                dp[total] = min(dp[total], dp[total - coin] + 1)
    if dp[amount] == unreachable:
        return -1
    return dp[amount]

这里按最后一枚硬币分类。所有 total-coin 都比 total 小，所以当前金额从小到大计算就满足依赖顺序。

例 2： coins=[1,3,4]、amount=6，dp[0..6]=[0,1,2,1,1,2,2]。最少是 3+3 两枚；每次优先取最大面额会得到 4+1+1 三枚，贪心并不总成立。coins=[2]、amount=3 返回 −1；amount=0 返回 0。

33.3 不同面额的组合数

现在问“有几种面额数量搭配”，不区分使用顺序。先枚举面额，再正序枚举金额，就只会按固定面额处理顺序生成方案。

代码文件：t33_coin_combinations.py

def count_coin_combinations(coins, amount):
    # 前提：coins 为互不相同的正整数；顺序不同不算新方案
    ways = [0] * (amount + 1)
    ways[0] = 1
    for coin in coins:
        for total in range(coin, amount + 1):
            ways[total] += ways[total - coin]
    return ways[amount]

例 3： coins=[1,2]、amount=3。处理 1 后，每个金额都只有全由 1 组成的一种方法；处理 2 后，金额 3 新增“原金额 1 的方案再加一枚 2”，最终两种：111、12。21 不单独计算，因为面额数量与 12 一样。

33.4 顺序不同也算不同：交换外层意义

若 12 与 21 视为不同动作序列，就按“最后一个选什么数”分类。先枚举金额，再枚举最后的面额。

代码文件：t33_ordered_sums.py

def count_ordered_sums(numbers, target):
    # 前提：互不相同的正整数，每个数可重复用，顺序不同算不同
    ways = [0] * (target + 1)
    ways[0] = 1
    for total in range(1, target + 1):
        for value in numbers:
            if value <= total:
                ways[total] += ways[total - value]
    return ways[target]

还是 [1,2]、目标 3，这次得到 111、12、21 共 3 种。两个程序转移语句看起来一样，循环顺序改变了状态所枚举的集合。题目标题含“组合”也不能替代题面定义；必须确认顺序是否计入区别。

如果允许 0，可能不断添加 0 而产生无限多个序列；允许正负数，也可能靠相互抵消无限增长。因此这些模板要求正整数，不是为了省略判断，而是保证状态依赖和答案有意义。

33.5 平台练习

入门｜力扣 322｜零钱兑换
训练重点与提示：最少枚数用 min，不可达初始化为 amount+1；与第 20 章错误贪心反例对照。未开始

巩固｜力扣 518｜零钱兑换 II
训练重点与提示：不区分排列顺序，面额放外层、金额正序；ways[0]=1。未开始

提高｜力扣 377｜组合总和 Ⅳ
训练重点与提示：题面把不同顺序算作不同答案，因此金额放外层；用 [1,2] 和目标 3 检查应得到 3 而不是 2。未开始

第34章 网格 DP：路径数量、最小和与数字三角形

先修：二维列表、第 30 章 DP。 本章的移动方向受到限制，通常只能向右、向下。与可以来回走的迷宫不同，这些状态不存在循环依赖。

34.1 从上方和左方到来

定义 dp[r][c] = 到达格子 (r,c) 的路径数。最后一步只能从 (r-1,c) 向下，或从 (r,c-1) 向右而来，因此两者相加。起点有一种空动作路径，设为 1。

代码文件：t34_grid_paths.py

def grid_path_count(rows, cols):
    if rows <= 0 or cols <= 0:
        return 0
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1
    for r in range(rows):
        for c in range(cols):
            if r > 0:
                dp[r][c] += dp[r - 1][c]
            if c > 0:
                dp[r][c] += dp[r][c - 1]
    return dp[rows - 1][cols - 1]

例 1： 2 行 3 列，表为第一行 [1,1,1]，第二行 [1,2,3]。答案 3。第一行不可能从上方来，第一列不可能从左方来；边界通过 r>0、c>0 判断处理，不读取负下标。

34.2 有障碍时，不能把边界全部设为 1

代码文件：t34_obstacle_paths.py

def obstacle_path_count(grid):
    # 整数 1 为障碍，0 为可走；只许向右或向下
    if not grid or not grid[0]:
        return 0
    rows = len(grid)
    cols = len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    if grid[0][0] == 1:
        return 0
    dp[0][0] = 1
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                dp[r][c] = 0
                continue
            if r > 0:
                dp[r][c] += dp[r - 1][c]
            if c > 0:
                dp[r][c] += dp[r][c - 1]
    return dp[-1][-1]

例 2： grid=[[0,1,0],[0,0,0]]，第一行第三格的路径数是 0，因为唯一的横向路被挡住；第二行全部可以沿下方路径到达，终点答案 1。起点或终点被挡时不能算作一条路。

34.3 最小路径和

把状态改成到达当前格的最小代价，候选来源取 min，再加当前格的数。起点代价包括它自己的值。

代码文件：t34_min_path_sum.py

def minimum_grid_path_sum(grid):
    # 前提：非空矩形网格，无障碍，只能右/下；起终点值都计入
    rows = len(grid)
    cols = len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]
    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c]
    return dp[-1][-1]

例 3： [[2,1,4],[3,2,1]]，dp 第一行 [2,3,7]，第二行 [5,5,6]，最小和 6，对应 2→1→2→1。即使无障碍网格中的值含负数，只要仍只向右或向下，这个递推也成立，因为没有绕圈；不能因此推广为任意四方向带负权路径。

以上三种二维模板都为 O(rows×cols) 时间与空间。滚动成一行时，新 dp[c] 的旧值来自上方，dp[c−1] 的新值来自左方，因此 c 正序更新；障碍位置必须置零，不能留下上一行的值。

34.4 数字三角形：从底向上更容易处理边界

第 r 行有 r+1 个数，从 (r,c) 可走到 (r+1,c) 或 (r+1,c+1)。求从顶到底的最大和。先复制最底行，dp[c] 表示从当前处理层的某个位置到底的最大路径和，然后逐层向上。

代码文件：t34_triangle.py

def maximum_triangle_sum(triangle):
    if not triangle:
        return 0
    dp = triangle[-1].copy()
    for r in range(len(triangle) - 2, -1, -1):
        for c in range(r + 1):
            dp[c] = triangle[r][c] + max(dp[c], dp[c + 1])
    return dp[0]

例 4： [[5],[2,4],[7,1,3]]。初始 dp=[7,1,3]，上一层更新为 [9,7,...]，顶层为 5+max(9,7)=14。选路径 5→2→7。内层从左到右时，dp[c]、dp[c+1] 都还保留下一层所需的旧值；换方向可能读到刚覆盖的值。

34.5 平台练习

入门｜力扣 62｜不同路径
训练重点与提示：没有障碍，先画出一个小矩形的 dp 表，不急着用组合公式。未开始

巩固｜力扣 63｜不同路径 II
训练重点与提示：障碍令当前方案数为 0，特别检查起点、终点和第一行遇障碍。未开始

巩固｜力扣 64｜最小路径和
训练重点与提示：路径数的加法改成最小代价选择时，初始状态也要随状态含义改变。未开始

巩固｜洛谷 P1216｜数字三角形 Number Triangles
训练重点与提示：每一行长度不同，使用数字三角形模板；不能当成固定宽度矩阵随便补 0，因为补出的格子不是合法路径。未开始

第35章 最长递增子序列：从 O(n²) 到 O(n log n)

先修：第 18 章二分、第 30 章 DP。 LIS 是 Longest Increasing Subsequence 的缩写，本章默认严格递增。

35.1 子数组与子序列先区分

子数组必须连续；子序列可以删掉中间一些元素，但不能改变剩余元素的先后顺序。a=[3,1,2,5,4] 中 [1,2,4] 是递增子序列，长度 3；不能把整个数组排序成 [1,2,3,4,5] 后声称答案 5，因为排序改变了原顺序。

严格递增使用 <，不下降使用 <=。a=[2,2,2] 的严格递增长度为 1，不下降长度为 3。这一个等号会影响 DP 和二分边界。

35.2 最容易解释的 O(n²) DP

定义 dp[i] = 以 a[i] 作为最后一个元素的最长严格递增子序列长度。每个元素自己至少形成长度 1。枚举前面的 j，只有 a[j]<a[i] 才能把 a[i] 接在以 j 结尾的序列后。

代码文件：t35_lis_quadratic.py

def lis_quadratic(a):
    if not a:
        return 0
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

例 1： a=[3,1,2,5,4]，dp=[1,1,2,3,3]，答案 3。为什么不直接返回 dp[-1]？因为最佳序列不一定以最后一个元素结尾；例如 [1,2,3,0] 的 dp[-1] 为 1，真实答案是 3。

时间 O(n²)，空间 O(n)。此版适合先推导、手算、给更快算法做小数据对照，不应面对 n=100000 时仍双重枚举。

35.3 更小的结尾更容易接新数

维护 tails：tails[k] 表示“在已经处理的元素里，长度为 k+1 的递增子序列能够拥有的最小结尾值”。同样长度的序列，末尾越小，后续越容易接一个更大的数，因此只保留最小结尾即可。

新数 x 到来，找到 tails 中第一个 >=x 的位置 pos。pos 左边全都小于 x，所以可把 x 接到长度 pos 的序列后，形成长度 pos+1 的候选。若 pos 等于当前长度，就出现更长的序列；否则用更小或相同的结尾替换原位置。

代码文件：t35_lis_fast.py

from bisect import bisect_left


def lis_length(a):
    tails = []
    for value in a:
        pos = bisect_left(tails, value)
        if pos == len(tails):
            tails.append(value)
        else:
            tails[pos] = value
    return len(tails)

例 2： a=[4,7,2,5,3,8]。

每次二分 O(log n)，随后替换或尾部追加，不是在中间 insert，因此总时间 O(n log n)，空间 O(n)。若用 insort 而不是“替换”，既改变状态含义，又会引入 O(n) 移动，不能混为一谈。

35.4 tails 不是实际答案序列

例如输入 [2,6,8,3,4,5,1]，最终 tails=[1,3,4,5]，但 1 出现在原数组最后面，不可能位于 3、4、5 之前。tails 保存的是不同长度的最优结尾信息，它们未必来自同一条路径。题目只求长度时返回 len(tails)；要求输出实际序列需要记录来源下标等额外信息，不可以直接打印 tails 冒充。

最长不下降子序列把 bisect_left 改成 bisect_right，因为相同值允许接在后面。连续递增段则只比较 a[i] 与 a[i−1]：能继续就长度加 1，不能继续就重置为 1，不需要 LIS 的二分模板。

35.5 平台练习

入门｜力扣 674｜最长连续递增序列
训练重点与提示：题目要求连续递增段，按本章末尾的相邻比较方法解决，刻意区分它与 LIS。未开始

巩固｜力扣 300｜最长递增子序列
训练重点与提示：先实现 O(n²) 并解释状态，再写 tails 版本；用全相等、严格递减、有重复值的数组比较两版结果。未开始

第36章 Dijkstra：非负边权的单源最短路

先修：第 21 章堆、第 26–27 章图与 BFS。 单源表示只有一个出发点；边权非负表示所有边的代价都大于等于 0。

36.1 为什么普通队列不够

例 1： 有向边 0→1 权重 9，0→2 权重 2，2→1 权重 1。直接走到 1 只有一条边，费用 9；绕过 2 虽有两条边，费用却只有 3。BFS 按边数分层，不会自动按费用排序。

Dijkstra 始终优先处理“当前已知距离最小”的候选节点。distance[u] 表示目前找到的从起点到 u 的最短候选距离，不是每条边单独的权值。通过 u 到 v 的候选为 distance[u]+weight；比 distance[v] 小就更新，这一步叫松弛。

36.2 非负边权为何重要

假设当前取出的节点 u 已拥有最小候选距离。任何尚未确定的节点，其候选距离不会更小；再沿非负边绕过这些节点，也不可能产生一条更便宜的路线回到 u。因此当前距离可以确定。

若存在负权边，后续路径可能突然减少费用，这个推理不再成立。本书的 Dijkstra 模板不支持负权图，更不处理负环。不要因为某个带负边的小样例碰巧算对，就声称算法普遍适用。

36.3 堆里存的是“候选快照”

float('inf') 表示正无穷，比任意有限距离大，适合初始化不可达节点。它是一个标记；有限路径的计算仍从整数 0 开始加整数边权，结果保持整数，不会为了设初值而把每条路径都变成浮点数。

代码文件：t36_dijkstra.py

import heapq


def dijkstra(graph, start):
    # graph[u] 中元素为 (v, weight)，所有 weight >= 0
    distance = [float('inf')] * len(graph)
    distance[start] = 0
    heap = [(0, start)]
    while heap:
        current_distance, u = heapq.heappop(heap)
        if current_distance != distance[u]:
            continue
        for v, weight in graph[u]:
            new_distance = current_distance + weight
            if new_distance < distance[v]:
                distance[v] = new_distance
                heapq.heappush(heap, (new_distance, v))
    return distance

这里堆元组第一个位置是距离，第二个是节点，所以最小堆会优先比较距离。把二者写反会按节点编号排序，不是 Dijkstra 的取点规则。

例 2： 对 36.1 的图，处理 0 后入堆 (9,1)、(2,2)；先取 (2,2)，发现去 1 只需 3，于是再入堆 (3,1)。旧 (9,1) 没有被从堆中删除；它后来被取出时，发现 9 不等于 distance[1]=3，就跳过。这个判断是过滤旧状态，不是可有可无的装饰。

按这种允许旧记录的二叉堆实现，最坏堆记录数可与边数同阶，复杂度可写 O((n+m) log(n+m))，空间 O(n+m)；常见简单图条件下也写 O((n+m) log n)。不要宣称堆中永远只存在 n 条记录。

36.4 不可达、方向与最大到达时间

返回的 distance 中仍等于正无穷的节点不可达。具体输出 −1、其他指定数值或保证全部可达，取决于题目。原封不动 print(float('inf')) 会输出 inf，通常不是判题器要的格式。

网络信号从起点向所有节点传播，若各节点最早收到信号的时间分别为 distance，那么所有节点都收到所需的时间是其中最大值，不是距离之和。多个传播分支可以同时进行。

如需记录一条最短路径，在成功松弛时设置 parent[v]=u，随后用第 27 章的前驱回溯思想恢复。只在严格变短时更新前驱，避免零权边情况下随意覆盖等距前驱导致复杂的恢复问题。

36.5 平台练习

入门｜洛谷 P4779｜【模板】单源最短路径（标准版）
训练重点与提示：有向、非负边权，题面保证从起点到所有节点可达；建边不要多加反向边，节点编号统一。规模较大时用快速输入并留意堆内存。未开始

巩固｜力扣 743｜网络延迟时间
训练重点与提示：Dijkstra 后检查是否有不可达点；全部可达时返回最短距离中的最大值，不是求和。未开始

第37章 拓扑排序：依赖关系的合法顺序

先修：队列、有向图、第 30 章 DP。 拓扑排序不是把编号从小到大排列，而是保证每一条依赖边的起点排在终点之前。

37.1 入度为 0 表示不再欠前置条件

有向边 u→v 表示 u 必须在 v 之前完成。入度 indegree[v] 是指向 v 的边数，也就是尚需满足的前置关系数量。入度 0 的节点当前可以处理；处理它后，相当于删除它的出边，使后继入度减一。

有向无环图简称 DAG。存在有向环时，环上的节点可能互相等待，不存在覆盖全部节点的拓扑顺序。无向图不能直接拿这套入度逻辑判断环。

代码文件：t37_topological_sort.py

from collections import deque


def topological_sort(graph):
    n = len(graph)
    indegree = [0] * n
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1
    queue = deque()
    for u in range(n):
        if indegree[u] == 0:
            queue.append(u)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    if len(order) != n:
        return None
    return order

模板内部重新计算入度，避免把调用者的原列表原地扣到全零，导致第二次执行出错。返回 None 表示有环；n=0 的空图返回空列表，是合法顺序，不应简单用 if not order 区分二者。

37.2 手算依赖过程

例 1： 边为 0→2、1→2、2→3。入度 [0,0,2,1]，队列初始 [0,1]。处理 0 后，2 的入度变 1，不能入队；处理 1 后才变 0，于是 2 入队；处理 2 后 3 入队。一个合法顺序是 [0,1,2,3]，[1,0,2,3] 也合法。

例 2： 0→1、1→0，两个节点入度都不是 0，队列初始为空，处理数量 0<n，因此判定有环。若只有图的一部分有环，程序可能处理掉其他节点后停下，仍需要检查最终数量，不能仅检查队列初始是否为空。

时间 O(n+m)，额外空间 O(n)。如果题目要求字典序最小的合法顺序，用第 21 章小根堆代替普通队列，每次取当前所有可选节点中编号最小者；这时会增加对数因子。

37.3 依赖任务可以并行：DP 接在拓扑顺序上

每个任务有 duration[u]，前置任务全部结束后才能开始，不受工人数量限制。定义 finish[u] 是 u 最早结束的时刻。没有前驱时，finish[u]=duration[u]。若 u 是 v 的前置任务，则 v 不可能早于 finish[u] 开始，因此更新：

finish[v]=max(finish[v], finish[u]+duration[v])。

为什么取 max，不取 min？所有前置任务都要完成，必须等待最晚完成的那个；不是任意一个完成就能开始。

代码文件：t37_task_finish.py

from collections import deque


def earliest_finish_times(graph, duration):
    n = len(graph)
    indegree = [0] * n
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1
    finish = duration.copy()
    queue = deque([u for u in range(n) if indegree[u] == 0])
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v in graph[u]:
            finish[v] = max(finish[v], finish[u] + duration[v])
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    if processed != n:
        return None
    return finish

例 3： 任务 0、1 用时分别为 3、5，任务 2 用时 2，且依赖 0、1 都结束。0、1 可以同时做，任务 2 最早在第 5 时刻开始，第 7 时刻结束。总时间是 7，不是 3+5+2=10，也不是 3+2=5。

37.4 平台练习

入门｜力扣 207｜课程表
训练重点与提示：[a,b] 表示 b 是 a 的前置课程，正确建边方向为 b→a；拓扑排序能处理全部节点才可完成。未开始

巩固｜力扣 210｜课程表 II
训练重点与提示：与上一题相同的图，额外返回合法顺序；有环按题面返回空数组。未开始

提高｜洛谷 P1113｜【USACO02FEB】杂务
训练重点与提示：任务可并行，答案是所有最早结束时间中的最大值；每行前驱列表以 0 结束，这个 0 不是一门任务。题面已经保证前驱编号更小，也可直接按给定顺序递推。未开始

第38章 Kruskal：连接全部节点的最小总费用

先修：排序、第 29 章并查集、树的定义。 最小生成树简称 MST，不是“从某个起点到每个点都最短”的树。

38.1 两种“最小”不是同一个目标

生成树要把所有节点连起来，同时不形成环；n 个节点必须选 n−1 条边。最小生成树希望所选边权的总和最小。最短路则希望从一个起点到指定点的路径长度最小，目标不同。

例 1： 三个节点的无向边 0—1 权 2、1—2 权 2、0—2 权 3。最小生成树选前两条，总费用 4；但从 0 到 2，原图直接边费用 3，比树上的路径费用 4 更短。MST 不保证保留所有原图最短路。

38.2 为什么按边权从小到大合并

初始每个节点单独一块。按边权从小到大看边，如果两个端点属于不同块，就选择并合并；若同属一块，选择后会形成环，跳过。

关键理由是交换：当前这条边连接了两个已有分块；任何把全图连通的生成树，都必须有某条边跨过相应分割。选当前最轻的可用跨割边，能够用它替换一个不更轻的连接而不增加总费用。反复进行可得到最优生成树。不是所有“每次取最小”的问题都能这样证明，本算法依赖无向生成树的结构。

38.3 独立可复制模板

为了单独复制本文件就能使用，下面把第 29 章的查找与按大小合并写在函数内部；原理没有新增。输入 edges 每项为 (u,v,weight)，不是 (weight,u,v)，排序函数负责取第三个字段。

代码文件：t38_kruskal.py

def kruskal(n, edges):
    # 前提：n >= 1；无向图，节点编号 0..n-1
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    selected = []
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        root_u = find(u)
        root_v = find(v)
        if root_u == root_v:
            continue
        if size[root_u] < size[root_v]:
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        total += weight
        selected.append((u, v, weight))
        if len(selected) == n - 1:
            break
    if len(selected) != n - 1:
        return None
    return total, selected

例 2： 四点边为 (0,1,1),(1,2,2),(0,2,3),(2,3,4),(0,3,7)。先选权 1 和 2；权 3 的边两端已连通，跳过；选权 4 后已有 3 条边，完成，总费用 7。

n=1 时不需要边，返回 (0,[])。图不连通时，即使看完所有边也凑不够 n−1 条，返回 None。平行边可以保留，自环自然因为两端根相同被跳过。与 Dijkstra 不同，Kruskal 的生成树目标可以处理负边权，仍按权重排序即可。

排序 O(m log m)，并查集操作总计近似线性，额外存储 O(n+m)。边数为 0 时理解为只剩初始化与连通性判断，不对 log 0 做数值计算。

38.4 恰好保留 k 个连通块

初始 n 块，每次成功合并减少 1 块，因此希望最后 k 块，需要成功选择 n−k 条边。按同样的排序合并顺序，在达到这一数量时停止，得到最小总权值的 k 棵树组成的森林。

k=n 时一条边也不选，答案 0，必须在循环之前或合并计数逻辑中处理；k 不在 1 到 n 之间不合法。若全部边仍不能完成 n−k 次成功合并，则不可行。这个模型要求每块内部是树形连接；题目允许额外加负权环边的其他模型不能直接按此解释。

38.5 平台练习

入门｜洛谷 P3366｜【模板】最小生成树
训练重点与提示：无向图的标准最小生成树；图不连通时题面要求输出 orz，不能输出 None。未开始

巩固｜洛谷 P1195｜口袋的天空
训练重点与提示：目标不是一棵树而是 K 个连通块，成功合并 N−K 次就结束，先处理 K=N 的零费用情况。未开始

第39章 选学：单调栈与单调队列

先修：第 17 章滑动窗口、第 21 章栈与双端队列。 本章放在最后，不是入门语法的先修。第一次学习可以完成前面主线后再来。

39.1 右侧第一个更大的元素

对每个位置 i，找右侧第一个比 a[i] 大的元素下标，不存在记 −1。暴力向右扫描会重复工作。栈保存“还没找到答案”的下标，栈中对应的数值保持从底到顶不增。

新数 a[i] 大于栈顶 a[j] 时，i 就是 j 右侧第一个更大的位置：如果之前有更大值，j 早已出栈，不会等到现在。因此把 j 弹出并记录答案，继续处理新的栈顶。

代码文件：t39_next_greater.py

def next_greater_indices(a):
    answer = [-1] * len(a)
    stack = []
    for i in range(len(a)):
        while stack and a[stack[-1]] < a[i]:
            j = stack.pop()
            answer[j] = i
        stack.append(i)
    return answer

例 1： a=[3,1,2,4]。读 3：栈[0]；读 1：栈[0,1]；读 2：弹出下标 1，答案[1]=2，栈变[0,2]；读 4：先解决下标 2，再解决下标 0。最终下标答案 [3,2,3,-1]。

栈必须保存下标，才能回答距离 answer[i]-i，也能区分相同数值出现在不同位置。等于不是“更大”，因此本模板只在 < 时弹出。若题目要求“更大或相等”，条件需要相应调整。

虽然有嵌套 while，每个下标只入栈一次、出栈至多一次，总时间 O(n)，空间 O(n)。复杂度不能只凭“看见两层循环”就断定 O(n²)。

39.2 滑动窗口最大值不能靠窗口和维护

固定长度窗口的和可以加一个、减一个。但当前最大值移出后，不能只通过“减掉它”知道剩余最大值。每个窗口重新执行 max 又会耗费 O(k)，总共 O(nk)。

单调队列保存仍可能成为最大值的下标。队首下标最早且对应值最大；队尾遇到更大或相等的新值时可以淘汰：新值不更小、出现得更晚，会在未来窗口里存活得更久，因此旧值永远不会比它更值得保留。

代码文件：t39_window_max.py

from collections import deque


def sliding_window_maximum(a, k):
    # 前提：1 <= k <= len(a)
    queue = deque()
    answer = []
    for i in range(len(a)):
        while queue and queue[0] <= i - k:
            queue.popleft()
        while queue and a[queue[-1]] <= a[i]:
            queue.pop()
        queue.append(i)
        if i >= k - 1:
            answer.append(a[queue[0]])
    return answer

第一段 while 删除已经在窗口左边的下标；第二段 while 删除被新值支配的候选；追加 i 后，队首就是窗口最大值。窗口尚未长到 k 时不能提前输出。

例 2： a=[2,1,3,2,4]、k=3，三个窗口最大值为 [3,3,4]。处理第 2 个下标的值 3 时，旧候选 1、2 都被淘汰，因为它们更小而且更早到期。

每个下标入队一次，从头或尾出队至多一次，时间 O(n)，队列额外空间 O(k)，返回答案本身 O(n)。窗口中的值可以是负数，不依赖第 17 章“窗口和非负元素”的单调性，那是另一种条件。

39.3 平台练习

巩固｜力扣 739｜每日温度
训练重点与提示：先找下一个更高温度的下标，再用下标差表示等待天数；无答案时按题意填 0，而不是模板中的 −1。未开始

巩固｜力扣 496｜下一个更大元素 I
训练重点与提示：先在 nums2 上求下一个更大值，再用第 13 章字典把值映射到结果，回答 nums1 查询；此题数值互异，才能直接用数值做唯一键。未开始

提高｜力扣 239｜滑动窗口最大值
训练重点与提示：用单调队列，而不是固定窗口和模板；检查 k=1、k=n、全相等、严格递减、含负数。未开始

第40章 从会看模板到独立提交

先修：已完成自己所在阶段的章节。 本章不是增加一批新算法，而是把前面的能力组织成稳定的解题过程。

40.1 读题时写下六句话

先用自己的话写出输入表示什么、要输出什么、允许什么操作、哪些条件必须满足、数据范围有多大、没有答案时如何表示。尤其区分“恰好”与“不超过”、“连续”与“可跳过”、“每件一次”与“无限次”、“最少步数”与“最小权值”。

然后做一个最小样例，手算答案。最后才挑模板：模板适用条件必须来自题目，而不是因为题目里恰好出现了某个关键词。

40.2 模型选择速查

这张表是定位入口，不是充要条件大全。一个题目也可能组合多个模块，例如“前缀和＋字典”“排序＋二分答案＋贪心检查”。

40.3 Python 高频错误清单

不要用一个大 try/except 把所有异常吞掉然后输出 0。这样只是隐藏错误，不是修好算法。异常最后一行的类型和提示、以及自己代码对应的行号，通常比网上随便换一个模板更有价值。

40.4 每道题至少自测这几类

最小规模、最大边界附近、全相等、全正或全负、答案位于开头/结尾、无答案、多答案、恰好等于阈值。图再检查孤立点、环、起终点相同；DP 再检查容量 0、无法恰好达到、空选择规则；区间再检查只含一个元素与覆盖整个数组。

会写暴力时，可以用小随机数据比较优化版与暴力版。例如比较 count_subarrays 与第 11 章的 count_subarrays_brute，比较二分边界与线性扫描，比较两种 LIS 实现。随机对拍不能替代证明，但能快速找出自己没想到的边界。

这里首次使用 random：seed(2026) 固定随机序列便于复现；randint(l,r) 生成包含两端的随机整数；assert 条件, 信息 在条件不成立时报告该组数据。它们仅用于本地测试，不是解题算法的一部分，提交时删去测试入口。

# 先把第 11、14 章两个函数放在同一文件中，再运行此自测
import random
random.seed(2026)
for _ in range(100):
    a = [random.randint(-3, 3) for _ in range(8)]
    k = random.randint(-5, 5)
    slow = count_subarrays_brute(a, k)
    fast = count_subarrays(a, k)
    assert slow == fast, (a, k, slow, fast)
print('本地对拍通过')

40.5 分阶段练习路线，不靠死记天数

阶段 A：语法独立。 学完 1–10 章。至少能够独立读入单值、一行列表、多行矩阵，写条件与循环，解释函数返回值。先完成洛谷基础题，再做力扣 2235、1929、217。遇到一行代码看不懂，应退回对应语法节，而不是背整行。

阶段 B：基础数组题。 学完 11–20 章。能写 O(n²) 暴力并估算规模，能使用前缀和、差分、二分与字典；解释窗口使用条件。完成前缀和查询、航班预订、移动零、二分查找、爱吃香蕉的珂珂、区间调度等代表题。

阶段 C：数据结构与搜索。 学完 21–29 章。能解释栈与队列区别，建正确的图，在循环中安全遍历网格，写出回溯的选择与撤销，处理并查集合并。先做括号与岛屿，再做 BFS、多源传播和并查集。

阶段 D：DP 主线。 学完 30–35 章。每次先写状态句，再写转移，能够用“重 3 值 5 容量 6”解释背包循环方向；区分硬币组合与有序序列。先做爬楼梯、最大子段和、采药，再做等和分割、零钱兑换、网格路径和 LIS。

阶段 E：图论与选学。 学完 36–39 章。区分无权最短路、非负权最短路、最小生成树、拓扑依赖；再接触单调结构。第一次没有时间做完选学章，不影响回头巩固基本题。

每个阶段挑 3 道已学题，隔一段时间不看答案重新写。能重新推导的题比“看过题解但没写过”的题更能说明掌握情况。

40.6 提交前最后一次检查

删去提示文字、调试输出与本地测试。检查平台选择的是 Python 3 或题目允许的相应解释器，函数名/参数由平台给出时不随意改名。标准输入题要完整程序，函数接口题不要额外 input。模板涉及 return None、−1、空列表等内部约定时，按题面转换输出。

运行速度取决于数据规模、算法、解释器与评测限制，不给“Python 每秒固定能做多少次操作”的绝对承诺。先消除复杂度级别的问题，再考虑读入、内存和常数。也不要把本地通过几个样例写成“保证所有平台 AC”。

附录 A 参考材料、Python 差异与资料来源

A.1 与所提供 Java 笔记的对应关系

本书参考用户提供的《Java 蓝桥杯算法与模板笔记》，但不是逐行翻译。原笔记第 1–2 页列出知识与模板目录；第 3–29 页讲知识；第 29–53 页给 Java 模板。下面说明哪些部分沿用主题、哪些部分为适应零基础而新增。

本书不把所有可能的竞赛算法塞进入门主线。树状数组、线段树、复杂字符串算法、树形 DP、数位 DP、网络流等不在本版基础范围；遇到需要这些方法的题，不会把它列作尚未教学的必做练习。原笔记提到但未完整展开的线性筛等，亦不假装已在本书系统讲完。

A.2 不应机械照搬的 Java 习惯

另外，前缀最大值与前缀和都是“前缀信息”，但只有可逆的适当运算才允许通过两个前缀恢复任意区间值；不能把任意区间最大值写成两个前缀最大值相减。多源 BFS 可理解为多个距离为 0 的起点；若用虚拟超级源解释，需要零代价连到各源，或统一说明多出的距离偏移，不能无说明地添加普通单位边。

A.3 官方资料入口

以下为语言与接口核对资料，供查证与进一步阅读，不要求初学者在第 1 章前读完。访问核对日期为 2026 年 10 月 8 日；在线文档会更新，实际评测解释器以题目环境为准。本书尽量使用不依赖新版本特性的基础写法。

Python 官方教程：数字、字符串和列表；控制流程与函数；数据结构。

内置类型：int、str、list、dict、set 等；内置函数：input、print、range、map、pow 等；排序指南。

collections：deque 与 Counter；heapq：堆；bisect：二分边界；math：gcd 等数学工具。

sys：标准输入输出、递归与整数转换相关限制；类的基本机制；错误和异常；Windows 官方使用说明。

平台题目依据对应的官方题面入口核对，全部直达链接集中列在附录 D 与独立习题清单。未通过非官方转载题面推断平台题号，也未把本地自编样例当成官方样例。题面中的文字故事未在本书整段复制。

附录 B 统一模板索引

算法模板已在正文相应知识点后完整给出；本附录用于定位，而不是要求新人从这里开始背代码。代码包中的 templates 目录按章节保存独立文件，每个文件已含自身需要的标准库导入，不需要把前面所有章节的代码都复制进去。

下表的章节链接可回到讲解，文件名可在代码包中搜索。templates_quick_reference.md 另把所有模板完整集中，适合学完后速查。函数型模板直接运行可能没有输出：它只定义功能，需要传入参数调用；附录 C 才是读入并输出的完整程序。

附录 C 可直接运行的完整程序

本附录所有输入格式均为本书明确制定的演示格式，不宣称与某道平台题完全一致。先复制完整程序到相应 .py 文件，再运行并输入样例。输入是传给程序的数据，不是写在 Python 源代码里的语句。

代码包 programs 目录中每个程序都配有同名 .in 与 .out 文件。可在终端运行 python 程序名.py 后粘贴输入；在支持重定向的终端中也可传入 .in 文件。Windows PowerShell 可在资料包根目录执行 Get-Content .\programs\sum_cases.in | python .\programs\sum_cases.py，这种按行管道方式足够用于这些小型演示样例。输入文件和源代码文件不要混淆。

第 14 章的 prefix_queries.py 已是第一个完整程序：先读 n、q，再读 n 个整数，随后 q 行给 1-based 闭区间，输出各区间和。下面补齐另外七个常用场景。

C.1 多组 A+B

文件：sum_cases.py。第一行 T，随后每行两个整数；输出每组的和。

代码文件：sum_cases.py

import sys


def solve():
    input = sys.stdin.readline
    first = input().strip()
    if not first:
        return
    cases = int(first)
    answers = []
    for _ in range(cases):
        a, b = map(int, input().split())
        answers.append(str(a + b))
    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()

自编样例输入：

3
2 5
-3 8
0 0

输出：

7
5
0

C.2 区间加后统一输出

文件：difference_updates.py。第一行 n、q，第二行 n 个整数；随后 q 行 l、r、delta，其中 l、r 是 1-based 闭区间。

代码文件：difference_updates.py

def apply_range_adds(a, updates):
    # updates 中每项为 (left, right, delta)
    # 使用原数组 0-based 闭区间；不修改 a
    n = len(a)
    diff = [0] * (n + 1)
    previous = 0
    for i in range(n):
        diff[i] = a[i] - previous
        previous = a[i]
    for left, right, delta in updates:
        diff[left] += delta
        diff[right + 1] -= delta
    result = []
    current = 0
    for i in range(n):
        current += diff[i]
        result.append(current)
    return result


def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    updates = []
    for _ in range(q):
        left, right, delta = map(int, input().split())
        updates.append((left - 1, right - 1, delta))
    print(*apply_range_adds(a, updates))


if __name__ == "__main__":
    solve()

自编样例输入：

5 2
1 2 3 4 5
2 4 3
1 2 -1

输出：

0 4 6 7 5

C.3 迷宫最少步数

文件：maze_shortest.py。第一行 n、m，随后 n 行字符网格，# 为墙；最后一行 sr、sc、tr、tc，全部是 1-based 坐标。

代码文件：maze_shortest.py

from collections import deque


def maze_distance(grid, start, target):
    if not grid or not grid[0]:
        return -1
    n = len(grid)
    m = len(grid[0])
    sr, sc = start
    tr, tc = target
    if not (0 <= sr < n and 0 <= sc < m):
        return -1
    if not (0 <= tr < n and 0 <= tc < m):
        return -1
    if grid[sr][sc] == '#' or grid[tr][tc] == '#':
        return -1
    distance = [[-1] * m for _ in range(n)]
    distance[sr][sc] = 0
    queue = deque([(sr, sc)])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        r, c = queue.popleft()
        if (r, c) == (tr, tc):
            return distance[r][c]
        for dr, dc in directions:
            nr = r + dr
            nc = c + dc
            if not (0 <= nr < n and 0 <= nc < m):
                continue
            if grid[nr][nc] == '#' or distance[nr][nc] != -1:
                continue
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))
    return -1


def solve():
    rows, cols = map(int, input().split())
    grid = [input() for _ in range(rows)]
    sr, sc, tr, tc = map(int, input().split())
    print(maze_distance(grid, (sr - 1, sc - 1), (tr - 1, tc - 1)))


if __name__ == "__main__":
    solve()

自编样例输入：

3 3
...
##.
...
1 1 3 1

输出：

6

C.4 并查集合并与查询

文件：dsu_queries.py。第一行 n、q；后续 q 行 op、a、b，节点为 1 到 n。op=1 合并，op=2 查询；查询输出 Yes 或 No。

代码文件：dsu_queries.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)


def solve():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        op, a, b = map(int, input().split())
        a -= 1
        b -= 1
        if op == 1:
            dsu.union(a, b)
        elif op == 2:
            print("Yes" if dsu.same(a, b) else "No")


if __name__ == "__main__":
    solve()

自编样例输入：

4 5
1 1 2
2 1 3
1 2 3
2 1 3
2 3 4

输出：

No
Yes
No

C.5 01 背包最大价值

文件：knapsack_01.py。第一行 n、capacity；随后 n 行每行 weight、value。重量为正，每件物品最多选一次，允许不选。

代码文件：knapsack_01.py

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]


def solve():
    n, capacity = map(int, input().split())
    weights = []
    values = []
    for _ in range(n):
        weight, value = map(int, input().split())
        weights.append(weight)
        values.append(value)
    print(knapsack_01(weights, values, capacity))


if __name__ == "__main__":
    solve()

自编样例输入：

3 5
2 3
3 4
4 5

输出：

7

C.6 带权有向图最短路

文件：dijkstra_shortest.py。第一行 n、m、start；随后 m 行 u、v、weight，节点编号 1 到 n、权非负。输出到每个节点的距离，不可达输出 -1。

代码文件：dijkstra_shortest.py

import heapq


def dijkstra(graph, start):
    # graph[u] 中元素为 (v, weight)，所有 weight >= 0
    distance = [float('inf')] * len(graph)
    distance[start] = 0
    heap = [(0, start)]
    while heap:
        current_distance, u = heapq.heappop(heap)
        if current_distance != distance[u]:
            continue
        for v, weight in graph[u]:
            new_distance = current_distance + weight
            if new_distance < distance[v]:
                distance[v] = new_distance
                heapq.heappush(heap, (new_distance, v))
    return distance


def solve():
    n, m, start = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, weight = map(int, input().split())
        graph[u - 1].append((v - 1, weight))
    distance = dijkstra(graph, start - 1)
    answers = []
    for value in distance:
        answers.append(-1 if value == float('inf') else value)
    print(*answers)


if __name__ == "__main__":
    solve()

自编样例输入：

4 3 1
1 2 9
1 3 2
3 2 1

输出：

0 3 2 -1

C.7 最小生成树

文件：kruskal_mst.py。第一行 n、m；随后 m 行 u、v、weight，节点编号 1 到 n，无向边。连通输出最小总费用，不连通输出 Impossible。

代码文件：kruskal_mst.py

def kruskal(n, edges):
    # 前提：n >= 1；无向图，节点编号 0..n-1
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    selected = []
    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        root_u = find(u)
        root_v = find(v)
        if root_u == root_v:
            continue
        if size[root_u] < size[root_v]:
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        total += weight
        selected.append((u, v, weight))
        if len(selected) == n - 1:
            break
    if len(selected) != n - 1:
        return None
    return total, selected


def solve():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v, weight = map(int, input().split())
        edges.append((u - 1, v - 1, weight))
    result = kruskal(n, edges)
    if result is None:
        print("Impossible")
    else:
        total, selected = result
        print(total)


if __name__ == "__main__":
    solve()

自编样例输入：

4 5
1 2 1
2 3 2
1 3 3
3 4 4
1 4 7

输出：

7

附录 D 习题总表与学习记录

题目按本书第一次安排的位置收录。每道题在正文已有训练目标和注意事项；本表可作为复习入口。题目标题为可点击链接，完整 URL 同时保存在代码包的 exercise_catalog.json 与 习题清单.md 中。没有列出的题并非不值得做，只是本版优先保证先修关系清楚。

“入门、巩固、提高”是相对于本章的训练层次，不能与平台官方难度直接画等号。比如放在第 39 章的提高题，前提是已经学过单调队列，而不是让刚会 print 的新人直接尝试。

建议另记三种状态：未开始、独立完成、需要复习。看过题解不等于独立完成；复习时先遮住模板，从状态、循环边界和样例开始重新写。

附录 E 代码包使用与验证边界

templates 保存逐章函数模板；programs 保存完整输入输出程序与样例；tests 保存可重复运行的本地测试；templates_quick_reference.md 汇总完整模板；习题清单.md 与 exercise_catalog.json 保存题目链接。

在代码包根目录运行 python -m unittest discover -s tests -v 可执行本地自测。测试文件为验证工具，使用了部分不纳入入门教学主线的标准库测试写法；不要求初学者先看懂测试框架才能使用模板，也不要把测试脚本提交到 OJ。

本次验证包括正文 Python 代码块的语法解析、所有独立算法模板的本地调用，以及与小规模暴力枚举、独立参考实现或标准库结果的对照；完整程序配有输入输出样例测试。具体结果见代码包 验证说明.md。这些测试不能证明所有可能输入都正确，也不代表已在力扣或洛谷逐题获得 AC，更没有代替题面时间和内存限制测试。

学习时优先读正文，比赛前再用索引；复制模板后先核对参数、下标、闭区间或半开区间、空输入和无解返回规则，再接上本题输入输出。模板的目的，是减少重复劳动，不是替代对题意的理解。