00-课程使用说明.md 5.3 KB
课程使用说明：把例题读成一节课
本节目标
读完后，你应能选择适合自己的阅读路线，知道每个折叠区何时展开，并能在不提交每一道课内题的情况下提炼可迁移的算法能力。
前置知识与课前自测
前置只需要 C++ 基础、常见 STL 和基础复杂度分析。先回答：
- 看到 $n=2\times 10^5$，为什么通常要先排除 $O(n^2)$？“常数小”能否挽救它？
- 一份题解说“用 Tarjan”时，你还需要追问哪些正确性和实现问题？
- 如果读懂了代码却说不出算法在什么条件下失效，算不算掌握？
展开自测参考
1. $O(n^2)$ 约为 $4\times 10^{10}$ 次基本操作，远超常规时限；只有证明实际访问量更小，才可改变判断。 2. 至少要问：维护什么状态和不变量、何时入栈/出栈、边的分类、重边与自环、递归深度、复杂度。 3. 不算。能说明适用条件、最小反例和替代方案，才说明掌握的是模型而不是代码形状。两条阅读路线
尝试路线
适合有完整训练时间时：读题后先只看 Hint 1；卡住 15–25 分钟再逐级展开。写完后必须对照 Editorial 的观察链和证明，而不是只检查代码是否相似。
直接学习路线
适合“今天不做这题，但要获得尽可能大收益”时。每道课内题按下面顺序读：
- 约束翻译：先把数据范围变成可接受复杂度候选。
- 模型信号：圈出决定建模的动词、对象和不变量。
- 错误路线：看一个最小反例，明确常见直觉错在哪里。
- Observations：逐条确认每个观察究竟删掉了哪些状态或转移。
- Editorial 与证明：先复述算法，再检查合法性、完备性和终止结论。
- 代码走读：给每个数组写一句语义；模拟一个正常样例和一个边界样例。
- 反事实变化：修改一个条件，判断原算法哪里先失效。
这条路线不要求提交，但要求留下三行复盘：识别信号、核心不变量、最容易写错的一行。
例题在课程中的分工
- 模型建立题：通常为 CodeForces 1600–2000 或等价难度，负责把定义变成算法。
- 组合迁移题：通常为 CodeForces 2000–2500，要求把本节技巧与已有工具组合。
- 灵活性实验室：全课程每 2–3 个大主题安排一道，允许达到 2800+，也允许只与当前主题部分相关；重点是构造、交互、反向思考或异常建模，不作为后续课程的硬前置。
- 课后训练题：用于独立提交。若没有完整 Editorial，就不会冒充正式例题。
正式例题的阅读结构
从本批课程起，正式例题不在正文铺开完整 C++。每题按以下顺序组织：
- Observations：至少说明数据范围排除了什么、朴素路线卡在哪里、哪条新观察真正改变状态数或复杂度。
- Editorial：从对象与关系的建模开始，逐步推出算法；不能用“套模板”替代推导。
- 正确性证明：分别证明每步合法、不会漏解/重复、终止答案达到目标；最优化题还要写出下界或交换论证。
- 复杂度与适用边界：把复杂度代回本题范围，并给出至少一个去掉关键条件后会失效的情形。
- 类 Python 核心伪代码：只保留决定算法结构的状态和转移，隐藏 C++ 容器噪声。
- 参考实现附件：完整 GNU C++17 放在仓库根目录
参考实现/，讲义用链接引用；附件仍参与统一编译和测试。
若只阅读不提交，至少应能在看附件前根据伪代码复述完整数据流。
如何使用 Hint
每级 Hint 必须改变你能做的事：
- Hint 1 只指出模型识别方向；
- Hint 2 给出关键性质，但保留算法组织；
- Hint 3 给出算法骨架；
- Hint 4 才触及实现中的下标、状态或边界。
若相邻两级只是换句话说，应视为文档质量问题。
代码、测试与评测声明
所有参考实现以 GNU C++17 为准。课程中的“已验证”分为三层：
本查看器中的多行展示公式统一使用独占行的双美元符号作为起止定界符。
- 编译验证：通过
-Wall -Wextra，只说明语法、类型和链接成立。 - 本地行为验证：通过来源样例或随机对拍，说明覆盖范围内的行为一致。
- 在线评测：只有确实提交并获得记录时才会声明；本课程默认不虚构此层。
交互题没有普通标准输入输出。课程会提供最小模拟器检查协议、查询次数与答案恢复，但这仍不等价于原平台在线通过。
总结与自检
完成任一章节后，尝试脱离文档回答：
- 这个算法解决的瓶颈是什么？
- 它依赖的关键条件是什么？去掉该条件的最小反例是什么？
- 正确性证明的核心不变量是什么？
- 数据范围为何允许该复杂度？
- 如果明天忘了模板，能否从定义重新推导出主要步骤？
课后训练建议
模型建立题建议独立实现；组合迁移题至少口述完整算法后再看代码；灵活性题先画状态或构造小例，30 分钟没有新观察再展开下一层 Hint。复盘时优先记录“我为何没识别出来”，而不是抄一遍模板。