按学习目标选择必读路线
第一遍学习不必把整本笔记从头读到尾。先选一条与自己当前目标相近的路线,完成其中的必读内容和练习,再根据做题时遇到的问题回查。下面的章号与目录一致;例如“五(十二)”表示“第五部分 → (十二)搜索”。
| 路线 | 适合的起点 | 第一轮的目标 | 阅读入口 |
|---|---|---|---|
| 零基础起步 | 还不能独立写出输入、判断和循环 | 把一段简单题意写成能运行的程序 | 先读语言主线,再接 ACM 入门主线 |
| 从 C 转到 C++ | 已经会用 C 写数组、循环和函数 | 用引用、模板与 STL 简化实现 | 先补 C++ 的写法,再按题目学习算法 |
| ACM 入门与比赛练习 | 能独立写基本程序,开始接触算法 | 完成常见入门题,并参加周赛 | 先学基础技巧,再学搜索、DP 与图论 |
| C++ 系统学习 | 希望理解语言、标准库与对象设计 | 能解释类型、对象和资源的使用过程 | 顺序学习第一、第二部分,再用算法检验理解 |
必读是当前路线的学习主线;选读可以接在相关练习之后;回查是在题目用到某个接口或模板时打开。表中的阶段按从上到下的顺序推进,每个阶段先读讲解、手算例子,再独立完成对应练习。
零基础起步:先写出程序,再认识常用工具
| 阶段 | 必读内容 | 本轮可以先放下的内容 | 完成标志 |
|---|---|---|---|
| 输入与计算 | 一(一)至(六):程序结构、类型、转换、运算、判断循环、原生数组 | 位运算进阶、枚举类型的细节 | 独立完成 P1001、P5703、P5710、P1428,能手算每轮循环 |
| 把重复动作写成函数 | 一(七)函数;一(八)引用、值传参与生命周期;一(九)auto 与范围 for | 动态分配、复杂指针、lambda 的递归写法 | 能解释实参与形参,能用引用修改一个变量 |
| 读入文本与组织数据 | 一(十)输入细节;一(十三)输出格式;一(十四)模板入门的类型参数 T;一(十五)STL 的 string、vector、pair、迭代器与 <algorithm> |
文件操作、异常、多文件程序、类型工具及较少使用的容器 | 独立完成 P5733、P1427、P1059,解释排序与去重的步骤 |
| 从题意写出判断 | 三(一)至(六)、(八)(九)(十一):提取信息、条件、循环、等价关系、优先级、向上取整、反例与状态 | 三(七)(十二)(十三)的综合模型 | 能给自己的判断找一个反例,并说明修正原因 |
| 开始算法练习 | 转入下面的 ACM 入门路线,从“基础技巧”开始 | 先不通读面向对象、二叉树长实现和全部二分变式 | 用已学知识独立完成一道枚举题,再按题目需要继续学 |
序言中的竞赛模板先作为提交时的查阅材料。学会函数与头文件以后,再回来解释 solve、测试组数和 EOF 循环;算法学习前理解标准流加速的两行设置即可。
从 C 转到 C++:补齐写法与工具的依赖
| 阶段 | 必读内容 | 选读与回查 | 完成标志 |
|---|---|---|---|
| 认识 C++ 对象的使用过程 | 一(二)(三)的初始化与类型转换;一(七)(八)的引用、const、传参与生命周期 | 用一(一)至(六)的练习检查熟悉的语法 | 能说明拷贝、引用与对象销毁分别发生在哪里 |
| 从类型参数到标准库 | 一(九)auto、lambda;一(十四)模板;一(十五)string、vector、pair、迭代器、algorithm、map、set、stack、queue、priority_queue | list、deque、unordered 容器在相应题目中补读 | 能用一个带注释的小程序演示插入、查找与遍历 |
| 传递动作与组织记录 | 一(十六)std::function;二(一)(三)(四)(八)的对象、构造、const 与比较规则 | 二(五)至(七)的继承、多态、拷贝移动在系统学习时回读 | 能给排序写出明确的比较规则,并解释一次回调 |
| 接上解题方法 | 三的必读小节与下面 ACM 主线;序言的快速 I/O、多组输入与 EOF | 一(十一)的多文件组织、四(一)的 fread 在需要时回查 | 用 C++ 独立完成一道之前会用 C 做的题,再比较实现 |
ACM 入门:沿着题目需要逐步扩展算法
先补齐上一条路线中的常用语言工具。面向对象先读 struct、构造和比较规则;继承、多态、完整资源管理可穿插在后续语言学习中。
| 阶段 | 必读章节与小节 | 第一轮练习 | 后续选读 |
|---|---|---|---|
| 建模与工作量 | 三(一)至(六)、(八)(九)(十一)(十四)(十六);五(一)复杂度;四(三)提交检查 | P5711、P5709、P1085 | 三(十)(十二)(十三)(十五)(十七),用构造、方法比较、事件模拟与对拍扩展推导 |
| 基础技巧 | 五(二)枚举与模拟;五(三)前缀和与差分;五(四)排序;五(五)GCD、素数判断与筛法;五(六)快速幂 | P1554、P8218、P2367、P1908、P1226 | 离散化、线性筛与较大规模数论题 |
| 有序性与局部选择 | 五(九)双指针;五(十)二分搜索的查找、单调判定与整数答案;五(十一)贪心 | P1102、CF 279B、P1182、P1803、P1090 | 三分、实数二分、加油规划;无需先读完全部二分例题 |
| 搜索与重复计算 | 五(十二)递归 → 回溯 → DFS → BFS → 剪枝 → 记忆化 | P1036、P1605、P1443、P1434 | P1219 与新汉诺塔等状态较复杂的搜索题 |
| 从递归转成填表 | 紧接记忆化读五(十三):线性 DP、二维状态、编辑距离、0/1 背包、完全背包、网格 DP | P1115、P1255、P2758、P1048、P2842、P1002 | 优化 LIS、排列转 LCS、P2679 子串状态扩展、多重背包 |
| 把关系建成图 | 五(十四)并查集;五(十五)概念与建图、连通块、二分图、Dijkstra、Floyd、拓扑序、DAG DP、树、Kruskal | P3367、B3643、P1330、P3371、B3647、P1807、P3366 | 五(八)二叉树的完整插入删除实现,用来理解结构维护 |
| 混合题与定时比赛 | 三(十二)(十三)(十五)(十七);后记中的牛客周赛、CF rating 与复盘安排 | 把当前难度附近的题组成一次定时练习 | 按复盘结果补弱项,接入省赛、ICPC/CCPC 或 OI 训练 |
四(一)的 fread 用来处理较大的批量输入;四(二)的大整数四则运算在普通整数已经装不下答案时回查。遇到 P1255 这类精确计数题,再把大整数加法接到 DP 上,学习目标会更具体。
C++ 系统学习:把应用接回类型与对象
| 阶段 | 必读内容 | 配套任务 |
|---|---|---|
| 语言与标准库 | 第一部分按顺序阅读,包括指针、文件、异常、多文件组织、模板、STL 和 std::function | 运行小程序,修改一次输入或调用方式,说明对象和结果的变化 |
| 对象与资源 | 第二部分按顺序阅读,从记录数据到封装、构造、继承、多态、拷贝移动、资源管理与比较规则 | 完成第二部分的四项练习,画出对象与所有者的关系 |
| 用题目组织代码 | 第三部分的建模、方法比较、完整事件模拟与职责划分;第四部分输入和大整数实现 | 把一个程序分成读入、建模、计算和输出,再解释每个部分保存的信息 |
| 用算法加深理解 | 第五部分先读复杂度、排序、搜索、记忆化与 DP,再按应用学习树和图 | 解释递归调用、容器存储和状态转移,回查相应语言机制 |
从一个阶段进入下一个阶段
读完讲解后,合上答案,用小数据走一遍,再独立写出本阶段的一道题。能解释变量、判断、更新顺序和复杂度,就继续下一阶段;若卡在某一步,回到对应小节重做这个步骤。每阶段留下一道已经独立完成的题和一道需要复习的题,下一次学习从这两道题开始。
正文练习旁保留原题链接。后记后的附录给出 GitHub 题解仓库入口,按章节与题号查阅完整推导。先看题解中的“建模与推导”,自己接着实现;仍有困难时再看手算、图解与代码。复习时可以先关闭答案,只看原题重新完成。