1贪心为何对
面值 1,3,4 凑 6 元，贪心（先取最大）用几张？最优几张？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2交换论证法
交换论证的核心假设是什么？
3排序不等式
把 {1,2,3} 与 {4,5,6} 一一配对相乘再求和，怎样配和最大？
4邻项交换
排队打水，每人耗时 t[i]，求所有人总等待最小，应按什么排？
5区间调度
区间 [1,3],[2,4],[3,5]，最多选几个不重叠？
6区间覆盖
覆盖 [0,4]，有 [0,2],[1,3],[2,4]，最少几个？
7合并果子
果子 1,2,9 的最小合并代价是多少？
8部分背包
容量 10，A(w6,v18)、B(w5,v10)，先拿谁？总价值多少？
9加油站问题
判断“能否绕圈一周”只需看什么量？
10贪心的反例
01 背包能用“按单位价值贪心”吗？
第 1 页 · 背面（答案）
参考答案（家长）：假设最优解与贪心不同，且一次交换不使解变差。
参考答案（家长）：贪心取 4+1+1=3 张，最优 3+3=2 张，说明此时贪心错误。
参考答案（家长）：按 t 从小到大（耗时短的先打水）。
参考答案（家长）：同序配对 1×4+2×5+3×6=32 最大。
参考答案（家长）：2 个，如 [0,2]+[2,4]。
参考答案（家长）：2 个，如 [1,3] 与 [3,5]。
参考答案（家长）：A 单位价值 3>B 的 2，先拿 A（占 6），再拿 4 单位 B（价值 8），共 26。
参考答案（家长）：1+2=3，3+9=12，共 3+12=15。
参考答案（家长）：不能，物品不可切分，贪心会漏最优，需 DP。
参考答案（家长）：看 sum(gas) 是否 ≥ sum(cost)。
第 2 页 · 正面（题目）
11二分答案套路
二分答案依赖的前提性质叫什么？
12写好 check
求“最大值最小”时，check(x) 一般判定什么？
13最大值最小
序列 7,2,5,10,8 分 2 段，最大段和最小是多少？
14最小值最大
位置 1,2,8 放 2 头牛，最大的最小间距是多少？
15分组二分
“m 人抄 n 本书，使抄得最慢的人用时最少”该二分什么？
16实数二分
实数二分为什么常写成固定循环次数？
17双指针入门
反向双指针一般用在什么样的数组上？
18尺取法
尺取法中每个元素最多被 l、r 各访问几次？
19滑动窗口
求所有长度为 3 的连续子段和，窗口右移一格如何 O(1) 更新？
20两数之和
数组 1,3,5,7 找和为 8 的对，指针最终停在哪？
第 2 页 · 背面（答案）
参考答案（家长）：判定“限定每份不超过 x 时，能否满足分组条件”。
参考答案（家长）：单调性（可行性沿答案方向单调分界）。
参考答案（家长）：7（放在 1 和 8）。
参考答案（家长）：18（切成 7+2+5=14 与 10+8=18）。
参考答案（家长）：避免浮点精度导致 while 条件永不满足而死循环。
参考答案（家长）：二分“每人最大抄写量（时间上限）”。
参考答案（家长）：各一次，故总复杂度 O(n)。
参考答案（家长）：有序（单调）数组，如求两数之和。
参考答案（家长）：1+7=8 命中（l=0,r=3）。
参考答案（家长）：新和 = 旧和 + a[r] - a[l]（加右减左）。
第 3 页 · 正面（题目）
21构造题特点
构造题与最优化题最大的区别是什么？
22小规模找规律
求 1+2+…+n，算 n=1,2,3 得 1,3,6，猜通项公式？
23奇偶性构造
用 1×2 骨牌铺满 3×3 棋盘可能吗？为什么？
24递归对称构造
“用小结构拼大结构”的思想在哪个算法范式里也常见？
25一维前缀和
a=1,2,3,4，用前缀和求 a[2..4] 之和。
26差分数组
对全 0 数组的 [2,4] 加 5，差分数组哪两处改变？
27二维前缀和
二维前缀和递推里为什么要减 s[i-1][j-1]？
28二维差分
二维差分一次矩阵修改要打几个标记？
29记忆化搜索
记忆化数组的初值为何不能设成可能出现的合法答案？
30可行性剪枝
走迷宫 DFS 中，走到墙或界外应如何剪枝？
第 3 页 · 背面（答案）
参考答案（家长）：n(n+1)/2。
参考答案（家长）：构造只需任一可行解，不必最优。
参考答案（家长）：分治（divide and conquer）。
参考答案（家长）：不能，格子数 9 为奇，每块盖 2 格无法铺满。
参考答案（家长）：d[2]+=5，d[5]-=5。
参考答案（家长）：s=0,1,3,6,10，s[4]-s[1]=10-1=9。
参考答案（家长）：4 个（四个角）。
参考答案（家长）：上、左两块都加了左上角部分，减一次去重（容斥）。
参考答案（家长）：直接 return，不再从该格继续搜。
参考答案（家长）：会与真实结果混淆，无法区分“算过”与“未算”。