XCPC 综合题单

XCPC 综合题单

题单导航

主综合题单：XCPC_综合题单　·　进阶题单：XCPC_进阶题单　·　补充题单：XCPC_补充题单

笔记

以 StudyingFather「一个动态更新的洛谷综合题单」3.0.2 为经典题库底稿，并按当前 XCPC 学习体系重新筛选、迁移与交叉挂载。

本表只承担知识导航与主动选题：只保留足以建立、检验和扩展一个知识节点的最小有效训练集。高价值但偏深、偏专项的题进入 XCPC_进阶题单；同模型复盘、补手感与低成本熟练题进入 XCPC_补充题单。

原题单：https://studyingfather.com/archives/841

原仓库：https://github.com/SFOI-Team/luogu-problem-list

原项目采用 CC BY-SA 4.0 与 Star And Thank Author License。本版保留来源与署名；公开传播或继续演绎时请遵守原项目许可。

使用规则

  • 主线：值得主动建设到理解、实现与迁移层；优先沿题目顺序推进。
  • 进阶主线：基础主线稳定后再系统学习；代表更高复杂度或更强迁移价值。
  • 地图保留：知道用途、触发线索和模板入口即可，不自动生成近期待办。
  • 模板题默认保留：即使与应用题模型重合，仍承担标准实现恢复与检查职责。
  • 允许一题多归属，但必须有不同知识责任：第二归属用于表达真实交叉关系，不用于机械重复。
  • 原子专题通常保留约 4～6 个核心训练节点，但不机械限额：专题过短可以完整保留，模型差异明显时可以自然扩展。

训练标记

  • 模板：标准实现与实现边界检查。
  • 衔接：模板之后的第一层，适合进入专题。
  • 主练：代表模型，优先完整思考。
  • 挑战：完成前置后再做，用于迁移与综合。
  • 复盘：跨专题回看，不作为新知识入口。
  • 地图：保留知识锚点，不要求主动刷。

三表分工：综合题单决定“现在学什么”；进阶题单保存“以后值得专项回收什么”；补充题单保存“需要熟练度或手感时还能刷什么”。

当前主表共有 683 个题目条目、680 个不同题目；少量条目重复仅用于表达稳定的知识交叉关系。

Part 1 基础算法

Part 1.1 模拟 / 实现｜主线

重点训练复杂规则下的状态一致性、信息组织与边界处理。

Part 1.2 二分答案｜主线

重点训练单调性识别、答案域处理与不同判定结构。

Part 1.3 分治｜主线

保留几种不同形态的递归拆分、规模压缩与跨区处理。

Part 1.4 贪心｜主线

重点训练局部选择、排序依据、交换证明与约束下决策。

Part 1.5 构造｜主线

重点训练从必要条件、不变量与目标性质反推整体结构。

Part 1.6 高精度｜地图保留

XCPC 中优先使用 boost::multiprecision::cpp_int，仅保留工具入口。

Part 1.7 前缀和 / 差分 / 离散化｜主线

重点训练信息重表示、区间统计、范围影响与结构降维。

Part 1.8 双指针 / 滑动窗口｜主线

重点训练端点单调移动、窗口信息维护与局部结果组合。

Part 1.9 三分 / 单峰函数｜地图保留

重点训练单峰 / 单谷结构的连续域搜索，并保留从裸模板到复合凸函数判定的最小训练集。

Part 2 搜索

Part 2.1 基础搜索｜主线

Part 2.1.1 深度优先搜索｜主线

重点训练状态枚举、回溯恢复，以及递归搜索中的状态组织。

Part 2.1.2 广度优先搜索｜主线

重点训练最短层次扩展、状态建模，以及多个搜索结果之间的组合。

Part 2.1.3 记忆化搜索｜主线

重点理解搜索状态的重复子问题，以及缓存状态结果带来的复杂度下降。

Part 2.1.4 搜索剪枝与状态搜索｜主线

重点训练搜索顺序、等效状态排除、可行性剪枝与复杂状态表示。

Part 2.2 Meet-in-the-Middle｜主线

重点训练把指数搜索拆成两个较小状态空间，并设计两侧结果的匹配方式。

Part 2.3 启发式搜索｜地图保留

仅保留能够建立估价函数与搜索边界概念的代表题，不作为当前主动训练主线。

Part 2.3.1 A*｜地图保留

Part 2.3.2 IDA*｜地图保留

Part 2.4 DLX｜地图保留

仅保留精确覆盖模型与 Dancing Links 实现入口，高阶应用进入专题题库。

Part 3 动态规划

本 Part 按“状态模型 → 结构型 DP → 状态压缩与计数 → 优化型 DP → 高阶与综合”组织。基础题保留但折叠；同一道题允许因知识交叉在其它 Part 再出现。

Part 3.1 基础状态模型｜主线

Part 3.1.1 线性 DP / 序列模型｜主线

重点训练沿线性顺序组织状态、压缩前驱信息，以及从题意中提取可递推结构。

Part 3.1.2 序列匹配 / 字符串 DP｜主线

重点训练两个序列之间的匹配关系、保序选择，以及由匹配状态扩展出的计数与恢复。

Part 3.1.3 背包 DP｜主线

重点训练容量、收益与选择限制之间的状态建模，并保留几类具有独立建模价值的背包变形。

Part 3.1.4 网格 / 路径 / 多维状态 DP｜主线

重点训练路径型状态、多过程同步，以及从多个变量中选择真正需要进入状态的维度。

Part 3.2 结构型 DP｜主线

Part 3.2.1 区间 DP｜主线

重点训练按区间结构拆分子问题，并覆盖划分、扩展、合并、文法与区间贡献等不同状态形态。

Part 3.2.2 树形 DP / 树上背包｜主线

重点训练树结构上的局部状态合并，并保留普通树形 DP 与树上背包两条主要训练链。

普通树形 DP

树上背包

Part 3.2.3 换根 DP｜主线

重点训练先固定根求局部信息，再沿边转移整树答案，并逐步扩展到带权与多层状态。

Part 3.2.4 DAG / 图上 DP / 拓扑递推｜主线

重点训练把图结构压缩成可递推顺序，并在 DAG、最短路结构或有向边序上组织状态传播。

Part 3.3 状态压缩与计数 DP｜主线

Part 3.3.1 状态压缩 DP｜主线

重点训练识别真正影响未来的有限信息，并用子集、局部窗口或多值状态压缩原问题。

子集状态 / 状态图

行状态 / 局部轮廓

Part 3.3.2 SOS DP / 子集和 DP｜主线

重点训练子集与超集之间的信息聚合，并掌握 SOS 转移在计数与最值问题中的应用。

Part 3.3.3 计数 DP｜主线

重点训练把排列、划分与选择过程转化为可递推的计数状态，并处理结构限制与重复计数。

Part 3.3.4 概率 / 期望 DP｜进阶主线

重点训练随机过程中的状态递推，并区分直接线性期望与真正需要状态转移的期望模型。

Part 3.3.5 数位 DP｜主线

重点训练上界约束下的逐位状态设计，并覆盖限制计数、数位贡献与更复杂的跨位统计。

Part 3.4 DP 优化｜进阶主线

Part 3.4.1 单调队列优化 DP｜主线

重点训练从朴素转移中识别连续候选区间，并用单调队列维护窗口内的最优决策。

Part 3.4.2 斜率优化 DP｜主线

重点训练把二次型或分段型转移整理成直线最值，并逐步扩展到动态凸包与复杂事件顺序。

Part 3.4.3 决策单调性 / 分治优化 DP｜进阶主线

重点训练最优决策位置的单调结构，并掌握分治优化、决策区间维护与相关代价结构。

Part 3.4.4 数据结构优化 DP｜进阶主线

重点训练把 DP 的历史决策集合交给数据结构维护，并覆盖值域、区间、偏序与离线分治等不同形态。

Part 3.5 高阶 DP 与综合｜地图保留

Part 3.5.1 动态 DP｜地图保留

重点建立动态维护树形 DP 状态的基本框架，并保留强制状态与复杂修改两类代表应用。

Part 3.5.2 插头 DP / 连通性状态压缩｜地图保留

重点建立轮廓连通状态的表示方式，并从模板逐步迁移到带额外局部信息的复杂网格模型。

Part 3.5.3 DP 综合 / 交叉｜进阶主线

只保留真正需要多种技术协同完成、且不适合归入单一 DP 模型的小规模综合题。

Part 4 字符串

Part 4.1 字符串匹配与前缀结构｜主线

Part 4.1.1 字符串哈希｜主线

重点建立字符串映射、子串比较与哈希维护的基本视角，并保留一题结构化应用。

Part 4.1.2 KMP / 前缀函数｜主线

重点训练前缀函数、border、周期、fail 链统计，以及在线匹配中的状态维护。

Part 4.1.3 Z 函数 / 扩展 KMP｜地图保留

重点建立 Z / exKMP 的标准实现，并通过 border 统计理解其与前缀结构的联系。

Part 4.2 Trie 与多模式匹配｜主线

Part 4.2.1 Trie｜主线

重点训练前缀树上的插入查询、前缀关系、结构遍历，以及把字符串限制转成树上约束。

Part 4.2.2 AC 自动机｜主线

重点训练 fail 指针、fail 树、自动机状态图，以及 AC 自动机与 DP、数据结构的典型结合。

Part 4.3 回文结构｜主线

Part 4.3.1 Manacher｜主线

重点训练线性维护回文半径，并将回文信息用于计数与多个回文结构的组合。

Part 4.3.2 回文自动机 PAM｜地图保留

重点建立回文节点、fail 关系与出现次数语义，并保留一题高阶状态迁移。

Part 4.4 后缀结构｜进阶主线

Part 4.4.1 后缀数组 SA｜地图保留

重点建立 SA、rank、height 与 LCP 的基本结构，并保留重复子串、循环串和贡献统计三类代表应用。

Part 4.4.2 后缀自动机 SAM｜地图保留

重点建立 SAM 状态、endpos 与子串计数语义，并保留第 k 小与出现次数统计两类核心应用。

Part 5 数学

Part 5.1 整数与基础数论｜主线

Part 5.1.1 位运算 / 二进制技巧｜主线

重点训练二进制表示、异或性质与基础按位思维，不把 bitset 优化和高阶综合题混入基础导航。

Part 5.1.2 素数 / 筛法基础 / 因数分解｜主线

重点训练基础质因数分解、素数筛法及其建模应用，并保留大整数分解模板入口。

Part 5.1.3 GCD / exGCD / 裴蜀｜主线

重点训练 gcd 结构、约数计数与裴蜀定理，并保留标准与高性能实现入口。

Part 5.1.4 乘法逆元 / 线性同余｜主线

重点训练模意义除法、线性同余建模与批量逆元，并完整保留各类标准模板入口。

Part 5.1.5 中国剩余定理 CRT｜主线

重点训练同余方程组的合并、一般模数处理与从题意构造同余约束。

Part 5.1.6 欧拉函数 / 欧拉定理｜主线

重点训练欧拉函数的计数意义、gcd 计数与大指数降幂，并保留递归降幂的代表应用。

Part 5.1.7 高次同余 / BSGS / 二次剩余｜进阶主线

重点训练离散对数、二次剩余以及从递推或幂同余关系中抽取可求解结构。

Part 5.2 数论求和与高阶筛法｜进阶主线

Part 5.2.1 整除分块 / 数论求和基础｜主线

重点训练按商值分段处理求和，并把整除分块嵌入 gcd 与算术函数求和模型。

Part 5.2.2 莫比乌斯反演｜进阶主线

重点训练把 gcd 条件转成约数关系，并逐步扩展到二维计数、卷积结构与复杂数论求和。

Part 5.2.3 数论函数前缀和 / 高阶筛法｜进阶主线

重点保留高阶筛法的标准模板，并训练数论函数前缀和与整除分块的综合应用。

Part 5.3 博弈论｜主线

Part 5.3.1 经典博弈｜主线

重点训练 Nim、必胜策略构造与几类经典特殊博弈，建立从异或判定到结构分析的基本框架。

Part 5.3.2 Sprague–Grundy｜主线

重点训练 mex、子游戏分解与 SG 异或，并从递推计算逐步进入区间和结构化博弈建模。

Part 5.4 概率与期望｜主线

重点训练概率模型、期望线性性、条件概率、贡献法与期望方程；纯概率 DP 继续由 Part 3 负责。

Part 5.5 组合计数｜主线

Part 5.5.1 排列组合 / 基础计数｜主线

重点训练组合数、补集、位置选择与 Prüfer 序列，并保留一题局部限制下的直接计数。

Part 5.5.2 Catalan / Stirling 等特殊组合数｜进阶主线

重点建立 Catalan 与两类 Stirling 数的基本结构，并保留行列快速求法与树上距离幂的代表应用。

Part 5.5.3 容斥原理｜主线

重点训练从“至少 / 恰好 / 禁止”条件之间转换，并逐步扩展到多类限制与生成结构计数。

Part 5.5.4 组合恒等式 / 综合计数｜进阶主线

重点训练错排、隔板、Stirling 展开与排列结构计数，处理不能归入单一组合模型的综合题。

Part 5.5.5 Burnside / Pólya / 置换群｜地图保留

重点建立群作用下的等价类计数，并从 Pólya 模板扩展到有限对称群与无标号图计数。

Part 5.6 线性代数｜主线

Part 5.6.1 矩阵快速幂 / 线性递推｜主线

重点训练把固定线性转移写成矩阵，并从数列递推逐步扩展到有限状态、辅助状态与自动机转移。

Part 5.6.2 高斯消元 / 行列式｜主线

重点训练线性方程组、Gauss-Jordan、行列式与 GF(2) 消元，并保留几何和概率建模中的代表应用。

Part 5.6.3 线性基 / 异或空间｜主线

重点训练 GF(2) 向量空间、线性独立与异或最值，并扩展到带权选择、图上环空间和树上路径。

Part 5.7 多项式 / FFT / NTT / FPS｜进阶主线

Part 5.7.1 基础卷积｜主线

重点训练快速卷积的标准实现，并从裸多项式乘法扩展到普通卷积与循环相关建模。

Part 5.7.2 FPS 核心操作｜模板主线

保留形式幂级数核心操作的完整模板链，作为后续推导与综合题的实现索引。

Part 5.7.3 插值 / 多点求值｜主线

重点训练从点值恢复多项式、批量求值与快速插值，并保留一题幂和多项式的实际建模应用。

Part 5.7.4 高级变换与模板｜地图保留

保留高级卷积、分治 FFT 与若干特殊多项式变换模板，作为未来专项学习和实现查询入口。

Part 5.7.5 多项式综合应用｜挑战

保留能够体现多种多项式工具协同工作的代表题，不再把所有高阶综合题堆入主导航。

Part 5.8 其他数学工具｜地图保留

Part 5.8.1 线性规划｜地图保留

仅保留一个真正以线性规划为核心的竞赛入口；可自然转化为费用流的题目主归图论。

Part 5.8.2 自适应 Simpson｜地图保留

保留两道数值积分模板与一题实际应用，用于快速恢复自适应 Simpson 的实现和使用边界。

Part 6 数据结构

Part 6.1 基础维护结构｜主线

Part 6.1.1 单调栈 / 单调队列｜主线

重点训练单调结构维护最近关系、窗口最值与二维矩形，并保留一题复杂条件向最大矩形模型的转化。

Part 6.1.2 并查集｜主线

重点训练集合合并、关系维护与离线连通，并扩展到带权、扩展域、逆序操作和几何连通。

Part 6.1.3 堆 / 优先队列｜主线

重点训练动态最值、多路候选与可撤销贪心，并保留 Huffman、动态邻接和区间候选拆分等代表模型。

Part 6.1.4 ST 表 / RMQ｜主线

静态 RMQ 本身只保留标准模板与一题真正需要 RMQ 参与分类判断的综合应用。

Part 6.1.5 树状数组｜主线

重点训练前缀统计、值域计数、离线扫描与 DFS 序，并扩展到二维维护和计数与权值和联合查询。

Part 6.2 线段树家族｜主线

Part 6.2.1 线段树｜主线

重点训练节点信息设计、懒标记作用与复杂区间信息合并，不再为每一种基础 lazy tag 单独保留同型题。

Part 6.2.2 扫描线与线段树｜主线

重点训练几何事件离散化后的区间覆盖维护，并覆盖面积并、周长与加权窗口三类典型模型。

Part 6.2.3 高级线段树 / 特殊区间信息｜进阶主线

重点训练非标准区间修改、稳定性剪枝与特殊节点信息设计，关注“为什么能剪”和“信息怎样闭合”。

Part 6.2.4 李超线段树 / 直线维护｜进阶主线

重点训练直线集合上的最值查询，并从在线插线扩展到带时间维的动态加入与删除。

Part 6.2.5 线段树分裂 / 合并｜进阶主线

重点训练动态权值结构的 split / merge，并通过树上统计理解线段树合并的实际应用。

Part 6.3 根号与离线算法｜进阶主线

Part 6.3.1 分块 / 根号算法｜进阶主线

重点训练序列分块、参数根号分治、块内跳转与不可合并信息维护，并保留动态顺序统计作为高阶出口。

Part 6.3.2 莫队｜进阶主线

按普通、带修改、回滚、树上与二次离线逐步扩展，保留能体现不同状态维护边界的代表题。

Part 6.3.3 CDQ 分治｜进阶主线

重点训练偏序计数、时间维事件与 CDQ 优化 DP，并以高维偏序作为技术上限入口。

Part 6.3.4 整体二分 / 并行二分｜进阶主线

重点训练共享答案值域下的批量判定，并扩展到区间修改和复杂权值判定。

Part 6.3.5 时间线段树 / 可撤销数据结构｜进阶主线

重点训练将边或操作挂到有效时间区间，并用 rollback 数据结构维护递归过程中的动态状态。

Part 6.4 可合并与可持久化结构｜进阶主线

Part 6.4.1 可并堆 / 左偏树｜地图保留

重点训练可并堆的 merge / pop，并通过树上合并、懒标记与中位数结构理解它在复杂模型中的使用方式。

Part 6.4.2 主席树 / 区间顺序统计｜进阶主线

重点训练历史版本上的值域统计，并从静态区间第 k 小扩展到树路径、时间版本、动态顺序统计与复杂值域判定。

Part 6.4.3 其他可持久化结构｜进阶主线

保留不同基础结构的持久化模板，作为“版本化数据结构”这一通用技术的实现索引。

Part 6.5 平衡树与动态序列｜进阶主线

Part 6.5.1 平衡树 / 有序集合｜进阶主线

重点训练按权值维护有序集合、顺序统计与前驱后继，并扩展到全局偏移和多集合信息联动。

Part 6.5.2 动态序列 / 可分裂平衡树｜进阶主线

重点训练按位置 split / merge、动态插删与区间懒标记，并扩展到大型隐式序列上的稀疏动态操作。

Part 6.6 树上数据结构｜进阶主线

Part 6.6.1 树链剖分 / 树上路径数据结构｜主线

重点训练路径拆分后的区间维护，并保留真正增加路径方向、重链变化或特殊状态设计的代表题。

Part 6.6.2 Small-to-Large / 集合启发式合并｜进阶主线

重点训练集合对象本身的小并大，并通过树上分层集合维护理解其与 DSU on Tree 的区别。

Part 6.6.3 树上启发式合并 / DSU on Tree｜进阶主线

重点训练保留重儿子贡献的子树统计框架，并扩展到深度分层、频率分布与异或状态。

重点训练动态森林上的 link / cut 与路径信息，并保留虚子树和 preferred path 语义两类深化应用。

Part 6.7 高维与专用数据结构｜地图保留

Part 6.7.1 树套树｜地图保留

只保留真正体现多层数据结构嵌套价值的代表题，避免把所有动态顺序统计都重复挂入本节。

Part 6.7.2 01-Trie / XOR 维护｜进阶主线

重点训练按位贪心、持久化版本与树上路径差分，并扩展到前若干大异或候选的整体维护。

Part 6.7.3 特殊整数数据结构｜地图保留

仅作为知识地图锚点，保留 word-RAM 模型下亚对数整数集合结构的标准入口。

Part 6.7.4 K-D Tree｜地图保留

重点训练二维点集的包围盒剪枝，从矩形统计扩展到最近、最远与半平面查询。

Part 6.7.5 珂朵莉树 ODT｜地图保留

只保留一个能够完整体现 split、区间推平与随机数据假设的 ODT 锚点。

  • P5350 序列 地图：ODT 的 split、区间赋值与复杂段操作

Part 7 图论与树论

Part 7.1 图遍历与最短路｜主线

Part 7.1.1 图的存储与遍历｜主线

保留图论最低入口，训练邻接表、DFS / BFS 与反图上的可达信息传播。

Part 7.1.2 最短路｜主线

按模板性质、状态建图与复杂路径约束展开，保留真正增加最短路状态或结构变量的代表题。

Part 7.1.3 0-1 BFS｜主线

边权只有 0/1 时用双端队列维护最短路，并扩展到网格建图、代价重定义和二分判定。

Part 7.1.4 同余最短路｜主线

把整数状态按模数压成有限余数类，在余数图上求最小可达值，再统计原问题中的可达整数。

Part 7.1.5 最短路结构与特殊路径模型｜进阶主线

收纳仍以最短路结构或优化建图为核心、但不适合继续放入普通模板链的特殊模型。

Part 7.1.6 差分约束｜主线

重点训练不等式与差值关系向约束图的转化，并扩展到严格关系、二维条件与复杂判定。

Part 7.2 树论基础｜主线

Part 7.2.1 二叉树 / 递归树结构基础｜地图保留

保留树遍历恢复、结构比较与表达式树等代表模型，基础递归实现不再大量重复挂题。

Part 7.2.2 树的直径 / 中心 / 核｜主线

从树直径出发，训练动态直径、路径收益与沿直径寻找中心或核心区域的结构分析。

Part 7.2.3 树的重心 / 距离和最优点｜主线

重点训练树重心及删除后的结构变化，并扩展到多中心下的树上距离和最优化。

Part 7.2.4 树上贡献统计｜主线

保留点对局部贡献与删边后两侧规模统计两类代表模型。

Part 7.2.5 LCA / 树上差分 / 路径关系｜主线

围绕静态祖先关系、路径差分与路径几何关系展开；在线路径数据结构仍由 Part 6 负责。

Part 7.3 函数图与倍增跳转｜主线

Part 7.3.1 函数图 / 基环结构｜主线

先识别每点唯一后继形成的基环内向树结构，再处理入环前长度、环长与整体可达范围。

Part 7.3.2 倍增 / 二进制跳转｜主线

重点训练二进制拆分后的快速跳转，并扩展到树上资源分配、可达关系与环形区间覆盖。

Part 7.4 生成树｜主线

Part 7.4.1 最小生成树及其扩展｜主线

重点训练 MST 基础性质、瓶颈路、约束生成树与次优结构，并保留能够代表不同约束类型的变式。

Part 7.4.2 Kruskal 重构树 / 权值阈值连通｜进阶主线

重点训练把 Kruskal 的合并历史树化，并利用祖先与子树表达权值阈值下的连通块结构。

Part 7.4.3 矩阵树定理｜地图保留

保留 Matrix-Tree 的标准模板与典型加权 / 分层计数应用；行列式实现交叉参考 [[XCPC_综合题单#Part 5.6.2 高斯消元 / 行列式｜主线|5.6.2 高斯消元 / 行列式]]。

Part 7.5 有向图结构｜主线

Part 7.5.1 拓扑排序 / DAG 结构 / 传递闭包｜主线

保留拓扑序、可达关系与 DAG 结构本身；复杂 DAG DP 仍由 Part 3 负责。

Part 7.5.2 强连通分量 / 缩点 DAG｜主线

从 SCC 模板出发，训练源汇结构、缩点后的链与路径，以及优化建图后的强连通分析。

Part 7.5.3 2-SAT｜主线

重点训练二选一约束向蕴含图转化，并扩展到特殊状态枚举与复杂时序逻辑关系。

Part 7.6 无向图连通与欧拉结构｜主线

Part 7.6.1 桥 / 边双连通 / 桥树｜主线

沿 low-link 的边侧结构展开，从桥与边双模板过渡到桥树上的直径与补边问题。

Part 7.6.2 割点 / 点双连通 / 圆方树｜主线

从割点与点双模板出发，进一步训练点双结构计数和圆方树上的贡献与动态维护。

Part 7.6.3 欧拉路径 / 欧拉回路｜主线

保留标准欧拉路径构造、字典序控制与欧拉图进一步分解三类代表问题。

Part 7.6.4 离线动态连通性｜进阶主线

图论语义以这里为主；时间线段树与 rollback 技术入口仍由 Part 6.3.5 负责。

Part 7.7 二分图｜主线

Part 7.7.1 二染色与冲突图｜主线

从直接二染色过渡到自行构造冲突图，并扩展到多颜色集合之间的二分性判定。

Part 7.7.2 最大匹配 / 覆盖 / 匹配结构｜主线

从最大匹配模板出发，训练方案恢复、路径覆盖、König 定理与最大匹配的结构性质。

Part 7.7.3 带权匹配 / KM / 指派问题｜地图保留

单独保留最大权完美匹配模板与 assignment 标准模型；另参考 7.8.3 费用流。

Part 7.8 网络流｜主线

Part 7.8.1 最大流｜主线

从 Dinic 标准实现出发，训练拆点、配额、时间扩展与路径覆盖式容量网络。

Part 7.8.2 最小割 / 最大权闭合子图｜主线

重点训练边割、点割、二元选择、独立集、闭合子图与平面图对偶等稳定最小割模型。

Part 7.8.3 费用流｜主线

从标准供需网络出发，训练时间链、次序代价、多路径收益、额外流量付费与优化建图。

Part 7.8.4 上下界网络流｜进阶主线

先区分可行流、最大流与最小流三个标准问题，再训练带费用下界与路径覆盖式建模。

Part 7.9 树上高级技巧｜进阶主线

Part 7.9.1 点分治 / 点分树｜进阶主线

从静态点分治的路径统计出发，扩展到长度区间、复杂贡献与动态点分树。

Part 7.9.2 动态关键点 / 极小连通子树维护｜进阶主线

利用 DFS 序环维护动态关键点集合，并把相邻点距离和转成极小连通子树的边权和。

Part 7.9.3 虚树｜进阶主线

从虚树构造入口出发，训练多关键点压缩、贡献统计，并扩展到圆方树与多路径并结构。

Part 8 计算几何

Part 8.1 计算几何基础｜主线

用少量基础题保持叉积、距离、共线与基本位置关系的实现手感；更完整的几何原语由模板与笔记承担。

Part 8.2 凸性结构｜进阶主线

Part 8.2.1 凸包｜主线

重点训练二维凸包构造，并扩展到几何对象转化与凸多边形之间的代数关系。

Part 8.2.2 旋转卡壳｜进阶主线

重点训练凸包上的对踵点维护，从直径问题扩展到多支撑方向的最小包围矩形。

Part 8.2.3 半平面交｜地图保留

重点训练线性几何约束向半平面的转化，并从模板构造扩展到可行域面积与区域关系。

Part 9 跨专题工具

Part 9.1 0/1 分数规划｜地图保留

重点训练将分数目标参数化为判定问题，并观察不同模型中 DP、图算法与匹配如何充当 check。

  • P4377 [USACO18OPEN] Talent Show 衔接：分数规划与背包判定
  • P3199 [HNOI2009] 最小圈 主练：分数规划与负环 / 图判定；交叉：[[XCPC_综合题单#Part 7.1.5 最短路结构与特殊路径模型｜进阶主线|7.1.5 最小环 / 图判定]]
  • P3705 [SDOI2017] 新生舞会 主练：分数规划与二分图匹配 / 费用流；交叉：[[XCPC_综合题单#Part 7.7.3 带权匹配 / KM / 指派问题｜地图保留|7.7.3 带权匹配]]
  • P4322 [JSOI2016] 最佳团体 挑战：分数规划与树形背包；交叉：[[XCPC_综合题单#Part 3.2.2 树形 DP / 树上背包｜主线|3.2.2 树上背包]]

Part 9.2 Bitset / 字级并行优化｜主线

作为跨专题优化工具，训练将布尔状态或集合按机器字打包，并用于可达性、消元、字符串与值域关系维护。

Part 9.3 交互题｜地图保留

保留不同交互协议与信息获取模型的代表题，用于建立询问预算、在线决策与恢复隐藏结构的基本认知。

专题结构索引

为便于回看，下面只列当前主表已经显式整理出的稳定训练链：

  • 基础与搜索：模拟、二分、分治、贪心、双指针，以及 DFS / BFS、Meet-in-the-Middle、启发式搜索与 DLX；
  • 动态规划：线性 / 背包 / 区间 / 树形 / DAG / 状压 / 计数与概率，以及单调队列、斜率、决策单调性、数据结构优化与动态 DP；
  • 字符串：KMP / Z、Trie → AC、Manacher → PAM，以及 SA / SAM 两条后缀结构链；
  • 数学：基础数论、数论求和、博弈、概率期望、组合计数、线性代数、线性基与多项式；
  • 数据结构：基础维护结构、线段树家族、根号与离线算法、可持久化结构、平衡树、树上数据结构与高维专用结构；
  • 图论与树论：最短路 / 0-1 BFS / 同余最短路 / 差分约束、树论基础、函数图 / 倍增、MST / Kruskal 重构树 / Matrix-Tree、有向图结构、桥 / 边双 / 点双 / 圆方树 / 欧拉、离线动态连通、二分图 / KM、最大流 / 最小割 / 费用流 / 上下界流、点分治 / 点分树与虚树；
  • 计算几何：基础几何、凸包、旋转卡壳与半平面交；
  • 跨专题工具：0/1 分数规划、Bitset / 字级并行优化与交互题。

组织原则：正文统一按“Part → 专题族 → 子模型 → 训练题”组织。主表优先最小有效训练集；高阶专项移入 XCPC_进阶题单，重复模型与熟练度题移入 XCPC_补充题单。同题只有在第二位置承担独立知识责任时才重复挂载。

使用建议

  1. 进入一个新专题时，先沿主表完成模板 / 衔接 / 主练，确认能够无标签识别、独立实现并解释边界。
  2. 主线稳定后，如果需要继续拔高，再从 XCPC_进阶题单 回收该专题的高质量专项题；不要求一次清空。
  3. 需要恢复实现手感、集中板刷或补某一模型熟练度时，再从 XCPC_补充题单 抽题；补充题不构成长期待办。
  4. 真正判断是否掌握，仍看无标签识别、独立实现、变式迁移和比赛调用，而不是题目勾选数量。

参考与许可

本题库建设过程中参考了 StudyingFather「一个动态更新的洛谷综合题单」、洛谷官方题单及个人训练题单，并进行了重新分类、补充与交叉挂载。

StudyingFather 原项目采用 CC BY-SA 4.0 与 The Star And Thank Author License；如公开传播本衍生整理，请保留必要署名并遵守原项目许可要求。