FOUNDATIONS · BEGINNER'S APPROACHES
通用解题方法 · 从关系到算法 算法就是“一份别人照着做，也能做对的步骤说明”。先认出题目要什么，再选一条能解释清楚的做法。不需要先学会写代码。
① 找输入 别人给了我什么？
② 找输出 我要交回什么？
③ 找保证 题目特别告诉我什么？
按大类学习通用做法，展开后才看具体例子。当前内容归入第 1 周学习记录；课件来源仅使用2026 T3 Welcome与Foundations；题目指南归纳和自编例子另行标明。周数按悉尼日期与开学日 2026-09-14 计算，不等于官方考核范围。
选择学习周次 全部周 第 1 周
搜索通用方法或其中的例子
复制课件更新指令 复制后粘贴到 Codex 发送，即手动执行一次：收集 COMP3121 新课件并更新方法笔记。
手动执行指令 $comp3121-lecture-sync 更新3121课件并补充按周解题方法笔记。 第 1 周 / 通用方法
关系改写与特征分组 故事 → 数学关系 → 等价变形 → 单个对象的特征 → 分组或查找
先把“两个人之间满足什么”写成关系 R(i,j)，再尝试把 i 的项与 j 的项分开。如果能等价改写成 g(i)=g(j)，就为每个对象单独计算 g，特征相同的对象放在一组。不是所有关系都能这样拆。
把两对象的关系，改写成单对象的特征
01 / 建模
把两对象的关系，改写成单对象的特征 看到什么，就想起它？ 条件里同时出现 i、j，但加减移项后可能把两个对象分开。先检查能否得到 g(i)=g(j)。
先用生活里的话理解 给每个对象算一张“特征标签”。如果原条件等价于标签相同，就不必逐对检查，直接找同标签的对象。
做法公式 · Approach R(i,j) ⇔ g(i)=g(j) → 算出所有 g(i) → 排序分组 → 按问题取组大小或对象
R(i,j) 是两个对象满足的原关系；g(i) 是只由第 i 个对象及其原位置计算出的特征。⇔ 表示双向等价；n 是对象总数。
具体例子 · 2026 T3 当前课件 来自当前题目指南的 1.4（不是已确认的 lecture PPT 例题）：A[i]−A[j]=i−j。两边移项得到 A[i]−i=A[j]−j，令 g(i)=A[i]−i。同一组内任意两项都满足原条件。 Foundations p20–21补充通用存储方法：小整数值域直接用频率表；大键使用字典。这里只支持分组计数的工具选择，Maximum Alignment 的代数变形仍来自题目指南，不是讲义原例。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 必须证明两个方向都成立。不要把仅必要条件当等价条件；除法要检查分母为零，平方可能引入额外解。特征中的 i 是原位置，不能排序后重新编号再计算。
工作量怎么看？ 计算特征 O(n)，将特征排序并扫描分组 O(n log n)。若另用哈希分组，需要明确期望时间与课程允许条件，不直接宣称最坏 O(n)。
检查理解 / 记下我自己的技巧 条件 xᵢ−xⱼ=2(i−j)，能为每个对象算什么特征？ 清空本题 作答后看解释 移项得 xᵢ−2i=xⱼ−2j，因此取 g(i)=xᵢ−2i；再验证这个等式也能变回原条件。
相关分支：固定一个对象，查找它需要的搭档
02 / 搜索
相关分支：固定一个对象，查找它需要的搭档 看到什么，就想起它？ 如果关系不能直接变成相同标签，尝试固定 i，把 j 需要满足的条件单独解出来。例如 aᵢ+aⱼ=T ⇔ aⱼ=T−aᵢ。
先用生活里的话理解 像凑 10 元：你已经有 3 元，就只需要找 7 元，不用再猜搭档要多少。
做法公式 · Approach 先排好队 → 固定一个数 → 算还差多少 → 快速找差额
差额 = T − h[i]。T 是目标总数；h[i] 是你先选的数；i 是它的位置。n 表示一共有多少个数。
具体例子 · 2026 T3 当前课件 Welcome 的“两只鹅穿风衣”：两只不同鹅的身高之和必须恰好等于 T。先排序，再为每只鹅查找 T−h[i]。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 必须是两只不同的鹅。只有一只身高 5 的鹅，目标 10，不能把它用两遍；一种安全做法是只在当前位置右侧查找。
工作量怎么看？ 排序花 O(n log n)；每只鹅查找花 O(log n)，共 n 次，所以总时间 O(n log n)。查找如何变快，看下一张卡。
检查理解 / 记下我自己的技巧 目标 12，先选了 5。你接下来要找什么？能不能再次使用刚才那一个 5？ 清空本题 作答后看解释 找 12−5=7。不能重复使用同一个对象；对象不同可以具有相同的值。
第 1 周 / 通用方法
利用顺序与单调性排除候选 确定顺序 → 比较一个代表 → 证明一批候选不可能 → 缩小范围
二分、双指针与有序网格搜索共享的思想是安全排除。二分每次约减半；双指针每次移动一个边界。选择哪一种取决于题目允许排除哪些候选，不能仅凭“有序”就套二分。
排好队后，快速找一个数
03 / 搜索
排好队后，快速找一个数 看到什么，就想起它？ 题目已经给出从小到大排好的数，问某个数在不在。
先用生活里的话理解 像在排好页码的书里找第 80 页：翻到第 50 页，就知道前面都不用找了。
做法公式 · Approach 看中间 → 确定哪一半不可能 → 只在另一半继续
A 是这排数；k 是要找的数；m 是当前中间位置。A[m]<k 就去右边；A[m]>k 就去左边；相等就找到。
具体例子 · 2026 T3 当前课件 Foundations PDF p22–24：已排序数组中比较中点，按大小关系排除不可能的一半，直到命中或区间为空。下方数值演示为教学自编例。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 动手试：每次删掉哪一半？ 教学自编数值：[2,4,6,8,10,12,14]。这个小演示不是 PPT 的数值例子。
要找的数 上一步 下一步 重置
别这样套用 必须能保证顺序。不能看到“数组”两个字就用二分；乱序时，中间数小，不代表左边所有数都小。
工作量怎么看？ 候选每次约减半，例如 8→4→2→1。这样的轮数随 log n 增长，因此总时间 O(log n)。log 在这里可理解为“能减半几次”的量级。
检查理解 / 记下我自己的技巧 数组 [2,9,3,7] 中，看见中间的 9 比目标 7 大，能直接丢弃右边吗？ 清空本题 作答后看解释 不能。数组没有排序，7 恰好在右边，直接排除就会漏掉答案。
找最小可行值 / 最大可行值
04 / 搜索
找最小可行值 / 最大可行值 看到什么，就想起它？ 题目问最少或最多，你能判定一个目标是否可行，而且结果只沿一个方向变化。
先用生活里的话理解 像问最少几个座位够全班坐：10 个不够，20 个够，就继续在中间试。先要保证座位越多不会越糟。
做法公式 · Approach 目标 → 判定成本 → 证明单调方向 → 确定范围 → 二分边界
000…111 找第一个1；111…000 找最后一个1。t是目标；k是预算；A有2n−1个数且已排序。两种方向都可用二分，不能混用更新规则。
具体例子 · 2026 T3 当前课件 Foundations 原例 Maximum Median：A=[1,2,2,4,5]、k=3。C(t)=Σ(i=n..2n−1)max(t−A[i],0)。t=4花2次、t=5花4次，因此最大可行中位数4。最大的n个数离目标最近，交换较小被选数为较大未选数不会增加成本，故该和是最低成本。原有“最少座位够用”的生活类比对应另一种方向。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 先证明单调性与判定的充要性。不能仅增加原中间元素后不重排就把它当中位数。k=0直接返回原中位数；非整数答案需另设精度与终止规则。
工作量怎么看？ 一般R个候选、每次判定C时间：O(C·(1+log R))。本题k≥1为O(n log(k+1))；已有序，无需再排序。
检查理解 / 记下我自己的技巧 A=[1,2,2,4,5]、k=3，为什么把第三个数加到5，中位数仍不是5？ 清空本题 作答后看解释 结果重排为[1,2,4,5,5]，中位数是4。要达到5，至少3个数≥5，需要对原来[2,4,5]分别加3、1、0，总4次，超过预算。
证明“删掉这些，绝不会漏答案”
05 / 证明
证明“删掉这些，绝不会漏答案” 看到什么，就想起它？ 算法不停丢掉候选：二分、移指针、排除行列。你要解释这样删为什么安全。
先用生活里的话理解 像找丢失的钥匙：只划掉确定没有钥匙的地方。划掉多少不重要，不能把钥匙所在处划掉。
做法公式 · Approach 开始包含答案 → 每步只删不可能处 → 最后结论可靠
“不变量”是每一步都保持的一句话。这里是：如果答案存在，它仍在保留的候选中。还要解释为什么步骤最终会停止。
具体例子 · 2026 T3 当前课件 Foundations PDF p22–23：在非递减数组中，若A[i]<x，则j<i的位置都有A[j]<x，可以安全排除；反方向同理。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 “因为有序，所以没漏”太跳步。要说清“哪些位置”“为什么都不可能”。展示一条搜索轨迹不能代替一般理由。
工作量怎么看？ 正确性和速度是两件事。证明删得安全之后，另数最多执行多少步。
检查理解 / 记下我自己的技巧 证明每次都不漏解后，还需要解释“为什么会停下来”吗？ 清空本题 作答后看解释 需要。否则一个永远重复同一状态的过程也能“不漏解”，却永远不给答案。
第 1 周 / 通用方法
转换问题实例，复用已有算法 数学限制 → 构造新实例 → 调用已知算法 → 对应解与目标值 → 合计成本
当陌生问题接近熟悉问题，先尝试改造输入，让标准算法直接适用。正确性检查双向对应，最优化还要检查目标值。彩色最短路径是本学期讲义实例。
把局部限制变成删边，再调用 BFS
07 / 归约
把局部限制变成删边，再调用 BFS 看到什么，就想起它？ 无权最短路多了一个能逐条边独立判断的限制。
先用生活里的话理解 先把不能走的路从地图上划掉，再用熟悉的最短路线方法。
做法公式 · Approach E′={(a,b)∈E | color(a)≠color(b)} → H=(V,E′) → BFS
G=(V,E)是原无向无权图；H保留全部顶点，仅保留异色边。BFS返回边数距离。
具体例子 · 2026 T3 当前课件 课件原图：u、c蓝；a、d红；b、e、v绿。删u–c、a–d、b–v。原最短路u–b–v长2但不合法；最短合法路u–a–c–d–v长4。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 只证明新路径合法还不够，必须证明原合法路径没丢。要求“全程某颜色最多一次”等历史限制不能直接照搬；带权最短路不直接用普通BFS。
工作量怎么看？ 邻接表构造O(|V|+|E|)，BFS O(|V|+|E′|)，相加仍O(|V|+|E|)，空间同阶。7点10边删3条后7边，是讲义图的规模。
检查理解 / 记下我自己的技巧 为什么只说“BFS是正确的”不足以证明这里的答案正确？ 清空本题 作答后看解释 还要证明H的路径与G的合法路径双向对应且长度不变，否则BFS可能正确解决了一个与原题不同的问题。
第 1 周 / 通用方法
分解问题与合并答案 定义子问题 → 处理更小规模 → 合并结果 → 检查边界
将大实例转成更小的同类实例，写清答案之间的等价条件、基本情况与规模递减。回文是本学期Foundations的原例。
写等价条件，把问题缩成更小的自己
08 / 递归
写等价条件，把问题缩成更小的自己 看到什么，就想起它？ 去掉一部分后，剩下的问题与原来同型；能写出答案之间的等价关系。
先用生活里的话理解 拆开一层，检查这一层，再把相同问题交给里面更小的一层。
做法公式 · Approach P(l,r) ⇔ s[l]=s[r] 且 P(l+1,r−1)；l≥r 时为真
s是原字符串；l,r是当前两端下标；P表示该区间是否回文。长度每次减2，不能漏掉空串基本情况。
具体例子 · 2026 T3 当前课件 Foundations p45 回文原题；教学自编“radar”：r=r，再看“ada”；a=a，再看“d”；单字符是真。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 递归不自动等于对数时间。每次只少2个字符，有线性层数；复制子串还可能产生二次工作量。
工作量怎么看？ 下标方式T(n)=T(n−2)+O(1)，O(n)时间、O(n)递归栈；自编例radar比较2对。逐层复制子串可达O(n²)。
检查理解 / 记下我自己的技巧 每次递归都调用一次长度n−2的子问题，为什么不是O(log n)层？ 清空本题 作答后看解释 每层减2而不是除2。约n/2层才到基本情况，仍是线性数量。
第 1 周 / 通用方法
正确性论证与工作量分析 小例找漏洞 → 对任意输入论证 → 数操作次数 → 合并各阶段代价
这是每个算法都需要的检查层：反例可以否定一个方法；一般证明才能支持所有合法输入。速度要另行计算，不能用“跑通一个例子”代替证明或复杂度分析。
算法写完，怎样数它要做多少工作？
06 / 复杂度
算法写完，怎样数它要做多少工作？ 看到什么，就想起它？ 题目要求 O(n)、O(log n) 或 O(n log n)，你需要说明每部分花多少工作。
先用生活里的话理解 先擦 10 张桌子，再搬 10 把椅子，是两份工作相加；给 10 张桌子各放 4 张纸，是重复 10 次每次 4 张。
做法公式 · Approach 先后做：加起来 ｜ 每次都做：次数 × 每次工作
n 是输入个数。O(...) 说的是输入变大时工作量的上界量级，不是秒数。常数和较小项在这种比较里可以略去。
具体例子 · 2026 T3 当前课件 Welcome PDF p17–18：鹅题先排序，再为每只鹅做一次二分。Foundations p11–12给出顺序相加与重复相乘规则；p46要求计入构造成本、调用次数和单次成本；p47的Hamiltonian Path枚举说明简单操作重复阶乘次仍然很慢。
还没懂？点这里，一步一步想
上一步 下一步 重置
分步讲解用于理解，不代替对全部合法输入的证明。 别这样套用 有两层循环不自动等于 n²：要数真实执行次数。遍历不同组时，若每个元素只被看一次，所有组加起来仍只看 n 个元素。
工作量怎么看？ 例：先排序再扫描，O(n log n)+O(n)=O(n log n)。这里用大写 O；小写 o 有另一种数学含义。
检查理解 / 记下我自己的技巧 先扫描一遍数组，再扫描一遍数组，是 O(n²) 吗？ 清空本题 作答后看解释 不是。先后两个 O(n) 阶段相加是 O(n)。如果每个元素都重新扫描整个数组，才会产生 n×n 的工作。
没有找到匹配的技巧。换个词，或显示全部 。
TRANSFER / 当前题目的迁移
把技巧带回你正在做的题 下面是作业题的简短联系，来源是你提供的题目 PDF，不是 PPT 原例 。
1.2 · 有序网格 顺序 → 安全排除。
回到网格演示 → 1.3 · 两只鹅 凑目标 → 看两端。
回到双指针演示 → 1.4 · 相同特征归一组 改写条件 → 计算特征 → 找最大组。
回到 alignment 讲解 → 小提醒：如何把技巧写成作业答案？ 先用文字写清具体步骤和停止条件，再解释为什么不会出错，最后数工作量。不能只交“用二分”“用排序”这样的名字。算法演示与短例子帮助理解，不代替一般证明。
来源与范围 页码全部使用 PDF 的实际页序（从 1 开始），不是页脚编号。点击链接可核对原页；本地服务启动后可以打开。页面正文和交互本身可离线阅读。
“具体例子”保留已核对材料的来源；特征分组依据当前题目指南归纳；“教学小例 / 自编数值”是为理解额外添加的例子，已经分开标注。示例省去故事细节，但保留使用条件。
勾选和你写的技巧只保存在当前浏览器，不是作业提交记录。