板块八 · 组合与优化
一、板块定位
板块八是整个 GESP 课级体系的收官板块,干两件事:一是补齐大纲最后的工具(计数原理、排列组合、杨辉三角、容斥、倍增、代数几何、最小生成树、最短路、算法优化);二是把前七个板块的所有零件装配起来——孩子在八级要做的事不再是「学一个新算法」,而是「看着数据范围选对算法,再把模板拼出来」(第 23 课图论选型、第 26 课复杂度总表、第 30~31 课综合实战)。学完八级,孩子手里就是一份完整的「算法工具箱 + 选型手册」,无论继续考 CSP-J 还是回学校打基础,路都是通的。
- 适用年龄:12~16 岁(小学 6 年级 ~ 初三),已通过 GESP 七级
- 前置要求:并查集、拓扑排序模板能默写(板块七底线标准);LIS/网格 DP 能独立完成;知道 n=1e5 时 O(n²) 会超时
- 总课时:35 次 × 2 小时 = 70 小时(约 1 个学年,每周 1 次)
- 对应考点:cpp801 ~ cpp808(GESP 八级大纲 8 个考点,全覆盖;第 17 课为图论复习课,衔接 cpp705/cpp706)
- 学完能做什么:能独立解决「把 n 个点用最小代价连起来」「求两点间最短路径」这类图论题;能对 1e9 级别的大数用组合数学+取模计数;能对着数据范围在几秒内定下算法与预计耗时
- 与七级的关系:七级给的三个模板(LIS、并查集、拓扑排序)在八级直接当零件用——Kruskal 的核心就是七级的并查集;七级 BFS 的「边权为 1」限制在八级被 Dijkstra/Floyd 补全
二、课程目标(学完必须达到)
| 维度 | 具体标准 | 验证方式 |
|---|---|---|
| 知识 | 说出 Kruskal 与 Prim 各适合什么图;说出 Dijkstra 为什么不能有负权边;说出 n=1e6/1e5/1e3 分别允许什么复杂度 | 第 33 课模拟考 A 选择判断部分 ≥70 分 |
| 技能 | 能按数据范围选对算法并写出 Kruskal(排序+并查集)、Dijkstra(朴素版)、Floyd 三个模板;能用杨辉三角递推求 C(n,m) 并取模;能写 ST 表的建表与查询 | 第 16、23、24、25、32 课闯关与综合课限时完成 |
| 习惯 | 写图论题先在草稿上画样例图;提交前先算一遍「我的复杂度 × 数据范围」;前缀和下标从 1 开始 | 第 18 课起「代码体检单」持续检查 |
| 心态 | 不怕「长题面」,先读数据范围再读题;知道综合题是「多个小算法拼装」而非「一个新算法」 | 第 30~31 课综合实战观察 |
底线标准:35 课结束时,每个孩子都能不看资料限时默写三个模板并编译运行通过:① Kruskal 最小生成树(边排序 + 并查集判环);② 朴素 Dijkstra(O(n²) 版,含 dis 数组初始化与松弛);③ Floyd(三重循环,k 在最外层)。另需完成一次「给 n 和 m,说出该用哪个算法、复杂度是多少」的口头选型测试(10 题全对,出自第 23 课的选型表)。模板和选型缺一 = 板块八未达标——这两个能力就是八级编程大题的评分点。
三、教学路径(九段式,每段一个台阶)
第一段 分类还是分步(第 1~8 课) → 从「数着数」到「算着数」
加法乘法原理 · 排列组合 · 杨辉三角 · 容斥 · 计数综合两课
↓
第二段 图形会算账(第 9~12 课) → 从「代数」到「几何也能编程」
一元/二元一次方程 · 海伦公式与圆 · 坐标距离 · 鞋带公式
↓
第三段 一次跳一倍(第 13~16 课) → 从「一步步走」到「翻着跳」
倍增快速幂 · ST 表 · LCA 初识 · 倍增综合
↓
第四段 回到图(第 17 课) → 七级的图知识提速复习
存储、遍历、连通块(带权版预告)
↓
第五段 连通要最省(第 18~19 课) → 从「全连通」到「最省连通」
Kruskal · Prim
↓
第六段 走路要最短(第 20~22 课) → 从「点亮路灯」到「全图短路」
Dijkstra · Floyd · 边权为 1 用 BFS 与 Bellman-Ford 简介
↓
第七段 选型与综合(第 23~25 课) → 从「会算法」到「会挑算法」
图论算法对比选型表 · MST+最短路混合 · 分层图与最短路计数
↓
第八段 同样的答案更快(第 26~29 课) → 从「能过」到「稳过」
复杂度总表 · 前缀和与差分 · 数学公式与预处理 · 二分+贪心
↓
第九段 收官(第 30~35 课) → 从「会做」到「考得出、走得远」
综合实战两课 · 全考点闯关 · 模拟考 A/B · 总复习与 CSP-J 衔接
各段教学明细(每段教什么、用哪些例题、孩子最容易错什么)
第一段|分类还是分步(第 1~8 课)
- 教什么:加法乘法原理(1)、排列(2)、组合(3)、杨辉三角(4)、组合恒等式(5)、容斥(6)、计数综合两课(7~8)
- 关键例题:上衣配裤子乘起来;几条路选一条加起来;杨辉三角递推求 C(10,3);插板法
- 孩子最容易错:该乘的加了、该加的乘了;阶乘直接算溢出;有重复元素忘去重
- 段末验收:给 3 道计数题,先口头说「分类还是分步」再列式计算,全对通过
第二段|图形会算账(第 9~12 课)
- 教什么:一元/二元一次方程(9)、三角形与圆(10)、坐标与距离(11)、几何综合(12)
- 关键例题:海伦公式求面积;两点距离判共线;鞋带公式算多边形面积
- 孩子最容易错:不判两边之和大于第三边;π 用 3.14 精度不够;浮点输出位数错
- 段末验收:按「浮点三查」清单(合法性、精度、输出格式)自查通过一道几何综合题
第三段|一次跳一倍(第 13~16 课)
- 教什么:倍增快速幂(13)、ST 表(14)、LCA 初识(15)、倍增综合(16)
- 关键例题:兔子跳格子;ST 表建表与 O(1) 查询;深度对齐跳 LCA
- 孩子最容易错:k 的枚举方向与依赖反了;区间长度 1<<k 没判越界;log 数组算错
- 段末验收:不看书写出 ST 表的建表与查询,并用它求区间最大值
第四段|回到图(第 17 课)
- 教什么:七级图的存储、遍历、连通块八级提速复习,带权图预告
- 关键例题:用七级同一张地图,改带权边重新建模
- 孩子最容易错:带权图仍按无权处理
- 段末验收:口头说清「无权最短用 BFS、带权最短用后面三课的算法」
第五段|连通要最省(第 18~19 课)
- 教什么:Kruskal(18)、Prim(19)
- 关键例题:最短的电线连所有村子;边排序 + 并查集判环;已选集合到其余点的最小距离
- 孩子最容易错:find 没路径压缩超时;忘判图不连通;Prim 距离数组没初始化成无穷大
- 段末验收:不看书写出 Kruskal 模板——底线模板之一
第六段|走路要最短(第 20~22 课)
- 教什么:Dijkstra(20)、Floyd(21)、边权 1 用 BFS 与 Bellman-Ford 简介(22)
- 关键例题:一圈圈点亮路灯;三重循环 k 最外层;负权反例演示 Dijkstra 为什么翻车
- 孩子最容易错:拿 Dijkstra 处理负权;无穷大 1e9 相加溢出;Floyd 把 k 写进最内层
- 段末验收:不看书写出朴素 Dijkstra 与 Floyd——底线模板之二、之三
第七段|选型与综合(第 23~25 课)
- 教什么:图论算法对比选型表(23)、MST+最短路混合(24)、分层图与最短路计数(25)
- 关键例题:「n 和 m 给定,说出该用哪个算法」10 题口头选型测试
- 孩子最容易错:不看数据范围套模板;混合题里把两类算法接错
- 段末验收:选型测试 10 题全对——底线标准组成部分
第八段|同样的答案更快(第 26~29 课)
- 教什么:复杂度总表(26)、前缀和与差分(27)、数学公式与预处理(28)、二分+贪心(29)
- 关键例题:各算法时空复杂度一张总表;区间和 O(1);预处理阶乘代替循环
- 孩子最容易错:优化了时间爆了空间;前缀和下标从 0 越界;只减常数不改复杂度
- 段末验收:给一段代码,说出「数据范围 × 复杂度」能不能过,并给出一条降复杂度改法
第九段|收官(第 30~35 课)
- 第 30、31 课:综合算法实战,每课 3 道完整题(读题 15 分 + 独立做 60 分 + 讲评 45 分)
- 第 32 课:全考点闯关 20 题(cpp801~cpp808)
- 第 33、34 课:模拟考 A/B
- 第 35 课:总复习——八级考点全表 + CSP-J 衔接建议清单
每课的固定节奏(2 小时怎么用)
| 时段 | 内容 | 页面 |
|---|---|---|
| 0~10 分 | 上节回顾 + 今天目标 | 回顾页、目标页 |
| 10~25 分 | 情境导入(穿衣搭配、跳兔子、铺电线、导航) | 情境页 |
| 25~55 分 | 知识讲解(2~4 张卡 + 手算样例) | 知识页 |
| 55~75 分 | 代码演示(老师敲,孩子读,逐行讲为什么) | 演示页 |
| 75~95 分 | 动手练(跟打→填空→改错,三档星级) | 动手页 |
| 95~110 分 | 真题试炼(6 题,做完立刻对答案) | 试炼页 |
| 110~120 分 | 上机挑战 + 小结 + 留作业 | 挑战页、答案页、小结页 |
第 30~31 课综合实战为完整题组训练(每课 3 道完整题:读题 15 分 + 独立做 60 分 + 讲评 45 分),第 33、34 课 A/B 两套模拟考,均按七级同款双卷口径执行。
练习与作业设计
- 动手练(drills):每课 2~3 个,按「跟打 → 填空 → 改错 → 独立」梯度,标星级
- 真题试炼(quiz):固定 6 题(易 2 / 中 2 / 难 2),答案与「为什么」当场可见
- 上机挑战(lab):每课 1 个完整编程题,附完整可运行参考答案与逐行注释
- 课后作业:2~3 项,第 1 项必为编程作业且附参考答案
- 选型口头报告(第 23 课起):每道综合题动笔前先报「题目特征 → 数据范围 → 算法 → 复杂度」四句话,老师点头才开写
- 模板默写专项(第 26 课起):每次综合课开头 10 分钟默写 Kruskal/Dijkstra/Floyd 之一,纳入验收
模拟考与验收安排
| 课次 | 内容 | 口径 |
|---|---|---|
| 第 23 课 | 图论选型闯关 | 选型表 10 题 + 2 道限时题 |
| 第 30~31 课 | 综合实战题组 | 每课 3 道完整题 |
| 第 32 课 | 全考点闯关卷 | 覆盖 cpp801~cpp808 |
| 第 33 课 | 模拟考 A | 6 选择 + 10 判断 + 2 编程 |
| 第 34 课 | 模拟考 B | 换卷覆盖组合与图论薄弱点 |
| 第 35 课 | 总复习 + CSP-J 衔接 | 考点全表带走 |
四、考点对照表
| 考点 | 名称 | 落在哪几课 |
|---|---|---|
| cpp801 | 计数原理:加法与乘法原理 | 1、6 |
| cpp802 | 排列与组合 | 2、3、6 |
| cpp803 | 杨辉三角与组合恒等式 | 4、5 |
| cpp804 | 倍增法 | 13、14、15、16 |
| cpp805 | 代数与平面几何 | 9、10、11、12 |
| cpp806 | 最小生成树:Kruskal 与 Prim | 18、19、23、24 |
| cpp807 | 单源最短路:Dijkstra 与 Floyd | 20、21、22、23、24、25 |
| cpp808 | 复杂度分析与算法优化 | 26、27、28、29 |
五、本板块最难的三个坎(教师用)
- 「选型」这种抽象判断(第 23、26 课):孩子习惯了「这一课教什么就用什么」,综合题要求他自己判断「n=1e5 带权无向图求连通最小代价→Kruskal」。对策:第 23 课把选型表(数据范围 × 题目特征 → 算法)做成随身卡片,之后每道综合题答题前先口头报「我判断这是___问题,数据范围___,所以用___」;第 26 课复杂度总表要求抄一遍带回家贴书桌。选型判断练到条件反射,是八级也是整个课程最想留下的能力。
- Dijkstra 的「贪心正确性」(第 20 课):孩子能照抄松弛代码,但「为什么取最近的点先确定就对」说不清。对策:用「路灯一圈圈点亮」比喻 + 一个 4 点小图让孩子手算松弛全过程,亲眼看到「先确定的点不可能再被更新」。笔试爱考这个概念(负权反例)。
- 几何编程题的浮点细节(第 9~12 课):海伦公式判不成三角形、π 精度不够、保留位数错——错误都不在算法而在细节。对策:第 12 课几何综合课列「浮点三查」清单(合法性、精度、输出格式),闯关题按清单自查后交。
卡点速查表(贴讲台用)
| 现象 | 出现在 | 一句话诊断 | 对策 |
|---|---|---|---|
| 计数题式子乱列 | 第 1~8 课 | 「先问分类还是分步」 | 每题先口头归类再列式 |
| 组合数算出负数/溢出 | 第 4~5 课 | 「别硬算阶乘,一层层推」 | 杨辉递推 + 取模 |
| Kruskal 结果偏大 | 第 18~19 课 | 「环里的边混进来了」 | 并查集判环,find 加压缩 |
| Dijkstra 负权翻车 | 第 20 课 | 「路灯不能往回点」 | 先查边权,负权换方法 |
| Floyd 答案偏大 | 第 21 课 | 「k 是中转站,得放最外面」 | 三重循环 k 在最外层 |
| 综合题没思路 | 第 23 课起 | 「你还没报四句话」 | 特征→范围→算法→复杂度 |
| 前缀和差 1 错位 | 第 27 课 | 「下标从 1 开始,减 l-1」 | 统一 1 基,pre[r]-pre[l-1] |
六、家长沟通要点(最常被问的 4 个问题)
Q1:学完八级是不是就「毕业」了?接下来学什么? 答:GESP 到八级就到顶了(八级相当于 CCF 认定的 CSP-J 入门组水平)。第 35 课总复习会给孩子一份 CSP-J 衔接建议:已掌握的 80% 知识直接复用,需要补的主要是竞赛侧的工程习惯(对拍、文件 IO 熟练度、更多数据结构如线段树)。想继续走竞赛的转 CSP-J 备考,不想竞赛的孩子,这套能力直接支撑初高中信息课和各类编程活动。
Q2:八级还要学几何和方程?这数学课不是学过了吗? 答:数学课学的是「解出来」,编程题考的是「让计算机算出来」——代入消元写成代码、海伦公式写成函数、鞋带公式算多边形面积,考的是「把数学翻译成程序 + 处理浮点精度」。cpp805 每年笔试必考,编程题偶考,四周足够。
Q3:最短路、最小生成树是不是太难了?听说这是大学生学的。 答:算法本身不深——Kruskal 就是「边从短到长排,能用就用,用并查集判环」,孩子七级已经会并查集;Dijkstra 就是「一圈圈点亮路灯」。难的部分(堆优化、负权、差分约束)我们都不涉及。GESP 八级考的就是这两个朴素版本的「读得懂 + 写得出 + 知道什么图不能用」。
Q4:最后这些「优化」课(前缀和、预处理)是不是锦上添花? 答:恰恰相反,cpp808 是八级笔试的重头(复杂度判断年年考),而且「先算数据范围再动手」这个习惯决定孩子以后做任何综合题的下限。第 23、26 两课的选型表和复杂度总表是整个 105 课课程的收官工具,我们要求孩子把它带进考场。
Q5:计数那几课孩子小学奥数学过,会不会浪费时间? 答:奥数讲「列式算出来」,我们讲「让计算机算出来」——杨辉三角递推求 C(n,m) 要开数组、要取模、要防溢出,插板法和容斥也要落成循环。孩子奥数底子好是优势:概念半天就通,省下的时间正好花在「递推+取模」这类编程细节上,这部分恰恰是只学过奥数的孩子最容易翻车的地方。
七、遗留与衔接
- Bellman-Ford、SPFA、堆优化 Dijkstra 在第 22 课只作「简介」(知道存在、知道适用场景),不进模板默写和验收——这些是 CSP-J 阶段的内容。
- ST 表、LCA 在第 14~16 课完成「会建会查」,LCA 的完整实现(跳表细节)作为选学,竞赛向孩子再深入。
- 线段树、树状数组不在 GESP 大纲内,本板块不教;第 35 课总复习的 CSP-J 衔接清单里会明确列出「下一个该学什么」。
- 105 课课程至此收官。验收口径:第 32 课全考点闯关 + 第 33/34 课模拟考 A/B 至少一次 ≥70 分;底线标准三模板(Kruskal、Dijkstra、Floyd)默写通过 + 10 题选型测试全对。全部达标者颁发课程完结评估,并按孩子意愿分流:竞赛线转 CSP-J 备考组,素养线转入综合项目实践(可另约排课)。
写给陪读满八级的家长:这套课程从「敢碰电脑」走到「会选算法」,孩子最值钱的变化不是会背多少模板,而是拿到任何问题先问三句——数据多大、要不要有序、能不能砍一半。这三句的习惯,比八级证书本身耐用得多。
附:修订记录
2026-11-11 · 全部 280 份课件用修正后的生成管线重做了一遍。修的是显示缺陷:此前「中文句子夹英文」的段落,英文部分在 PPTX 里会被整段吞掉——关键字表只剩「类型只装整数」,函数名、题面里的 BFS / queue / sort 同样是空白。代码页不受影响,所以一直没被发现。
本板块涉及:函数名与容器写法恢复显示,课程内容本身无改动。
校验口径:280 份逐课比对「源码里出现的英文标识与 PPTX 可见文字」完全一致,0 缺失;页数仍为每课 22~24 页,结构校验(页数区间、代码行数、真题 6 题配比)全部通过。
旧的课件包已全部被覆盖,请以 新教案 目录里的这一版为准;不要用 2026-11-10 之前导出的包上课。