椰程信奥 · 教案
set / multiset / pair / map · 教案
一、教学目标
| 维度 | 具体目标 |
|---|
| 知识与技能 | ① 说出 set / multiset / map 的特性与 O(log n) 代价；
② 独立完成"明明的随机数"与"主要成分"；③ 掌握"判存在用 find/count"的铁律。 |
| 过程与方法 | 通过 6 个动画把不可见的容器行为外显化；建立"数组 / map / unordered_map"三问流程。 |
| 情感态度价值观 | 建立代价意识与适度使用新工具的理性；养成防御性编码习惯。 |
二、重点难点
| 类别 | 内容 | 突破方式 |
|---|
| 重点 | set 去重有序、迭代器写法 | 第 4 页动画 + 第 9 页代码走读 |
| 重点 | map 的 [] 陷阱 | 第 6 页动画：size 凭空变大 |
| 难点 | lower_bound / upper_bound 语义 | 第 5 页"插入位置"记忆法 + 单步二分 |
| 难点 | 摩尔投票需二次验证 | 第 10 页两种模式对照 |
三、教学过程
| 环节 | 教师活动 | 学生活动 | 设计意图 |
|---|
| ① 引入 4′ | 三种"下标用不了"的时刻 | 说出困难 | 建立动机 |
| ② set 8′ | 第 4 页动画 + insert 返回值 | 预测落点 | 天性外显 |
| ③ 二分定位 6′ | 第 5 页单步二分 | 报 left/right/mid | 理解 log n |
| ④ map 8′ | 第 6 页动画，重点点 [] 访问 | 观察 size 变化 | 暴露高频 bug |
| ⑤ 代价 3′ | 第 7 页切换规模 | 读比较次数 | 复杂度直觉 |
| ⑥ 例题1 7′ | 第 8–9 页 | 写遍历 | 拿下真题 |
| ⑦ 例题2 9′ | 第 10–11 页两法对照 | 说明为何要再数一遍 | 拓展 O(1) 空间 |
四、当堂检测标准
| 题号 | 正确答案 | 达标说明 |
|---|
| ① | 不算 | 能说出条件是 > N/2，必须严格大于 |
| ② | it != s.end() | 能说出 set 是双向迭代器，不支持 < |
| ③ | long long | 能说出 int 上限约 2.1e9，边界溢出 |
五、板书设计
set：去重 + 升序 insert 返回 pair<it,bool> 迭代器只支持 != / ++ 元素不可改
lower_bound = 第一个 ≥ x ｜ upper_bound = 第一个 > x
map：按 key 升序 判存在用 find / count，绝不用 []
O(log n)：insert / erase / find / count / lower_bound
六、易错预警清单
① mp[key] 会插入不存在的 key —— 判存在必须 find != end() 或 count()；
② set 迭代器不支持 < 和 +n，遍历只能 != + ++；
③ 遍历取值要 *it（map 是 it->first / it->second）；
④ set 元素不可直接修改，要改先 erase 再 insert；
⑤ --s.begin() 未定义，求前驱前必须判 != begin()；
⑥ 主要成分的条件是 > n/2（严格大于），key 用 long long；
⑦ 摩尔投票的候选必须再数一遍验证。