这门课程训练四种转化：把阈值变成分层，把要求变成坏事件，把路径变成分界两侧的统计量，把区间中的出现变成空隙中的缺席。每次转化都要保留原来的计数对象，并说明哪些信息足以确定后续贡献。 课程包含四章讲义、四道配套练习和一场独立的四题验收挑战赛。适合已经学过并查集、基础动态规划、树遍历、前缀和与模运算的 NOIP 选手。后三章需要能够自行推导组合系数和树上状态；遇到不熟悉的工具，可以先完成本章的小例与直接算法，再阅读优化部分。 ## 四章的学习顺序 1. **阈值分层与可行结构。** 从一条路径何时首次连通出发，为每对端点分配唯一的合并时刻，再把点对权值写成集合摘要的乘积。练习：<a href="https://dtoj.team/p/3730" target="_blank" rel="noopener noreferrer">分级通行</a>。 2. **坏事件与加权计数。** 先定义完整方案，再对缺少指定颜色的坏事件作容斥；通过首位分类处理环的闭合边，区分位置选择与款式选择。练习：<a href="https://dtoj.team/p/3731" target="_blank" rel="noopener noreferrer">环席配色</a>。 3. **树上分界与距离矩。** 以最近公共祖先为路径归属，把距离平方展开为三类可合并统计量；用不相交集合的顺序合并避免重复计算。练习：<a href="https://dtoj.team/p/3732" target="_blank" rel="noopener noreferrer">异色测距</a>。 4. **互补计数与空隙贡献。** 固定颜色后统计不含它的区间，用相邻出现位置之间的空隙分割对象；展开端点系数，用三个前缀矩计算整段贡献。练习：<a href="https://dtoj.team/p/3729" target="_blank" rel="noopener noreferrer">彩条账目</a>。 章节可以独立阅读。建议按顺序完成，因为后一章会使用前面建立的求和与归属方法。每章可安排一次阅读推导、一次编码与反例复查；练习后应能脱离参考实现，重新写出统计量的含义和更新式。 ## 每章需要交出的内容 > 在写程序前，写出一次贡献对应的原始对象、它归属的事件或分界、计算该贡献所需的摘要。随后证明每个对象被计算一次，并给出一个会击败直觉做法的合法小例。 程序通过以后，重新检查证明中使用的条件。例如：阈值能否从小到大加入、相等权值是否会改变归属、环上首尾是否相邻、两个子树集合是否已经互不相交、颜色空隙是否包含数组的首尾。 讲义中的自测题可以只写推导，也可以把小规模枚举器作为核对工具。枚举时直接列出原始对象，不照抄优化算法的状态转移。教师材料另含自测答案与逐题完整解答。 ## 四题验收挑战 <a href="https://dtoj.team/contest/6ad7c21f4b02f9940436bc28" target="_blank" rel="noopener noreferrer">进入“NOIP｜结构观察与贡献拆分”验收挑战赛</a>。 本场四题共 $400$ 分，个人作答时间为 $4.5$ 小时，采用 OI 计分。四道题各有独立的模型，满分目标覆盖结构证明、反向计数、树上路径和序列统计。配套练习通过后，再安排一段连续的时间独立完成挑战；不要先阅读教师解答。 开场可以先读完四题，分别写出能立即完成的直接算法与需要进一步证明的结论。提交部分分时，也应核对输入输出文件名、数值范围和题面承诺的特殊性质。赛后保留第一次作答的程序与推导，再记录实际漏掉的条件，避免把后来读懂的解法误当作当场已经掌握。 课程报名口令与比赛邀请码由管理入口提供。讲义与练习在课程中阅读，验收赛通过上述独立入口参加。

四章十二道训练题，围绕贡献拆分、唯一归属、补集与容斥、分组与顺序因子展开。请从“讲义”阅读学习指南、下载学生讲义，并使用资料导航进入分章练习和独立验收挑战赛。课程练习采用标准输入输出；验收挑战赛另有四道题，个人时长 4.5 小时，报名与开放时间以比赛页面为准。

用八道题学习四种综合推导：交换得到最优解的规范形，高位比较决定约束是否保留，图结构同时处理多个起点，以及把全局贡献落实到边界事件。每章包含两道练习、连续推导、反例、完整教学程序和附答案的纸上自测。 课程面向已掌握提高级常用算法、准备 NOIP 综合题的选手。学习前应熟悉排序、二分、并查集、最小生成树、树的 DFS 序、倍增、基础动态规划与组合数。已有[NOIP｜问题转化与解题建模](/training/6ad44809352c311ce5ae487c)与[NOIP｜从部分分到满分](/training/6ad44809352c311ce5ae487d)可用于补充建模及部分分训练，本课不要求先通关这些课程。 ## 学习顺序 | 章节 | 推导主线 | 必修练习 | 加强练习 | | --- | --- | --- | --- | | 一 | 最优解的规范形：先证明候选完整，再优化枚举 | [分组校准](https://dtoj.team/p/3487) | [回环合奏](https://dtoj.team/p/3494) | | 二 | 高位与稀疏状态：省略哪些信息，保留哪些约束 | [码册编排](https://dtoj.team/p/3491) | [协同频段](https://dtoj.team/p/3493) | | 三 | 图上的结构约束：合并门槛与根的禁止区域 | [山路补给](https://dtoj.team/p/3488) | [入场巡路](https://dtoj.team/p/3492) | | 四 | 全局贡献的局部计量：边界权重与第二次跨界 | [途中留记](https://dtoj.team/p/3489) | [封存支路](https://dtoj.team/p/3490) | “必修”表示建议先完成的建模训练，“加强”表示同章中需要进一步推导的任务。两类均计入课程练习。每章可以拆成两次学习：第一次读到关键状态或候选结构，独立补证明；第二次完成实现、边界与反例分析。不要把看完参考程序作为已经掌握的依据。 ## 讲义怎样使用 四章各有一份独立讲义，完整讲义保留相同内容与代码。先读定义与题意差异，在纸上写出候选或状态的确切含义，然后再看转移与证明。每章末尾的自测答案可以检查空集、空前后缀、重复标识、起点门槛和边界计费等细节。 代码采用 C++14，并保留各题要求的文件输入输出。课堂本地运行时应准备对应的 `.in` 文件，结果写入相应 `.out` 文件；直接把样例送进标准输入不会绕过程序中的文件重定向。题面是每道练习的数据范围、输入输出与评分约定的依据。 ## 线性代数前置手册 参加配套挑战前，请阅读完整讲义末尾的《线性方程、行列式与有向树计数》，完成其中的方程组与行列式自测。手册讲解二元线性方程、秩与自由变量、模素数消元，以及固定根、边朝根的有向矩阵树定理。四章八道课程练习保持原有安排；手册补充挑战所需的通用工具，不提供挑战题的条件转换与解法。 ## 限时验收挑战 完成四章后，可以进入[配套验收挑战赛](https://dtoj.team/contest/6ad7b29719a08f65d2c44447)。挑战为四道编程题，个人时长 4.5 小时，每题 100 分。课程练习用于学习和推导，挑战题用于在限时条件下重新选择模型与实现方法。 建议先完整读完四题，分别记录可证明的部分分与满分方向，再分配实现时间。参加前先检查文件名、整数类型与输出格式；比赛中每取得一个可运行方案，就用样例和自己构造的边界核对。挑战赛的题目与讲义练习独立，不在课程讲义中提供其解法。

针对冲刺后的常见薄弱点，补齐字符串规则、基础树遍历与统计、二维前缀差分、滑动窗口和质数约数。共12题；先按自己的薄弱点选练，再完整复盘。

从逐字符扫描到完整语法解析，依次练习输入边界、词法状态、嵌套结构与可撤销指令。共12题，配完整讲义、题解与课程题解PDF。

共12题，以两题复习衔接十道模型辨识与综合练习。先写完整暴力、状态含义与反例，再组合枚举、排序、前缀统计和简单动态规划；最后两题独立完成推导与程序。配独立长讲义、完整题解与课程题解PDF。

从相邻合并与木棍切割出发，练习如何用最后一次分割、第一刀和端点动作拆开区间。全课10题依次训练区间摘要、等待费用、有限结果状态与独立判模，并配有完整推导和参考实现。

围绕物品层与容量含义推导0/1、完全与简单分组选择，练习精确资源、最优计数、恢复方案与前后缀分解。共14题，配完整讲义、题解与课程题解PDF。

30道考前复练题，分为模拟与序列、枚举与基础数论、排序贪心与判定、搜索与图模型、动态规划、综合建模六个阶段，每阶段5题。附限时练习建议、分级复盘重点、完整题解与C++参考实现。阶段不设强制解锁，先独立完成，再查看题解并订正。

从操作和约束推导模型，练习保留对象、反向阈值、状态支配与独立建模。四道加强题，适合完成递推与状态、线性与序列后选学。

从现有 CSP-S、NOIP 模拟训练中精选 30 道题，按六个阶段复练：信息提取、判定窗口、图树建模、数据维护、动态规划和综合选练。每章 5 题，附具体复盘重点与完整题解、C++ 参考实现；各阶段均可直接进入。建议先独立限时尝试，再看题解并重新实现。

12道新增训练，从正确暴力出发，依次处理重复计算、状态裁剪、单调推进与摊还、批量计算与时空交换。各题保留可验证的部分分路径。