C++ / ACM 自学笔记 · v5.0

按学习目标选择必读路线

第一遍学习不必把整本笔记从头读到尾。先选一条与自己当前目标相近的路线,完成其中的必读内容和练习,再根据做题时遇到的问题回查。下面的章号与目录一致;例如“五(十二)”表示“第五部分 → (十二)搜索”。

路线 适合的起点 第一轮的目标 阅读入口
零基础起步 还不能独立写出输入、判断和循环 把一段简单题意写成能运行的程序 先读语言主线,再接 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 题解仓库入口,按章节与题号查阅完整推导。先看题解中的“建模与推导”,自己接着实现;仍有困难时再看手算、图解与代码。复习时可以先关闭答案,只看原题重新完成。

查阅笔记正文与全部题解 · Ctrl / ⌘ K