XCPC 补充题单

题单导航

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

笔记

本表保存已经从主综合题单中移出的同模型复盘、实现熟练度、补手感与低成本专项练习。

它们不是长期待办，也不承担新的知识入口。若某题连“补熟练度”的价值都很低、与现有题高度机械重复或过于裸模板，则可以在二次审计后直接删除。

对应专题的学习顺序与知识定位优先参考 XCPC_综合题单；需要更高阶专项时转到 XCPC_进阶题单。

当前共有 106 道补充题；只在需要复盘、板刷或恢复手感时抽取。

Part 1 基础算法

二分答案

• P1824 进击的奶牛 补充：最大化最小值同型复盘
• P4343 [SHOI2015] 自动刷题机 补充：边界与答案二分复盘

前缀和 / 差分 / 扫描

• P1904 天际线 补充：事件扫描与轮廓维护

双指针 / 滑动窗口

• P1381 单词背诵 补充：最短覆盖窗口复盘

Part 2 搜索

基础搜索

• P5440 【XR-2】奇迹 补充：DFS 状态枚举
• P3956 棋盘 补充：网格状态搜索
• P1535 游荡的奶牛 补充：固定步数路径状态

Part 3 动态规划

Part 3.1 基础状态模型

线性 DP / 序列模型

• P1095 守望者的逃离 补充：基础状态与决策
• P1091 合唱队形 补充：双向 LIS
• P1233 木棍加工 补充：排序与 LIS
• P1868 饥饿的奶牛 补充：线性区间选择
• P2285 [HNOI2004] 打鼹鼠 补充：顺序转移与偏序条件

背包 DP

• P1855 榨取kkksc03 补充：二维容量背包
• P2946 [USACO09MAR] Cow Frisbee Team 补充：计数背包
• P1757 通天之分组背包 补充：分组背包
• CF106C Buns 补充：混合背包
• P1537 弹珠 补充：多重背包可行性
• P1174 打砖块 补充：资源分配背包

网格 / 路径 / 多维状态 DP

• P1006 传纸条 补充：双路径同步状态

Part 3.2 结构型 DP

区间 DP

• P1005 矩阵取数游戏 补充：两端取数
• P1063 能量项链 补充：环形区间 DP
• P1040 加分二叉树 补充：区间 DP 与方案恢复
• P1435 [IOI2000] 回文字串 补充：回文区间状态
• P2890 Cheapest Palindrome G 补充：回文修改代价
• CF607B Zuma 补充：区间合并
• CF245H Queries for Number of Palindromes 补充：回文区间统计
• P3147 [USACO16OPEN] 262144 P 补充：区间合并与倍增
• P4342 [IOI1998] Polygon 补充：环形区间与 min/max

树形 DP / 树上背包

• P2585 三色二叉树 补充：树形分类状态
• P2016 [SEERC2000] 战略游戏 补充：树上点覆盖状态
• P4395 [BOI2003] Gem 补充：树上染色状态
• P2015 二叉苹果树 补充：基础树上背包
• P1273 有线电视网 补充：收益型树上背包

换根 DP

• CF1092F Tree with Maximum Cost 补充：距离贡献换根

DAG / 图上 DP

• P2656 采蘑菇 补充：SCC 与 DAG 最优路径

Part 3.3 状态压缩与计数 DP

状态压缩 DP

• P2622 关灯问题 II 补充：基础状态图
• P3694 邦邦的大合唱站队 补充：子集排列 DP
• P2396 yyy loves Maths VII 补充：子集可达与限制
• P1879 [USACO06NOV] Corn Fields G 补充：行状态 DP
• P5005 中国象棋 - 摆上马 补充：棋盘局部状压

概率 / 期望 DP

• P1654 OSU! 补充：连续段期望 DP

数位 DP

• P4999 烦人的数学作业 补充：数位贡献统计

Part 3.4 DP 优化

单调队列优化 DP

• P1714 切蛋糕 补充：前缀信息与窗口最值
• P2627 [USACO11OPEN] Mowing the Lawn G 补充：连续选择限制复盘
• P3572 [POI2011] PTA-Little Bird 补充：多组窗口参数
• P3800 Power 收集 补充：分层窗口 DP
• P3089 [USACO13NOV] Pogo-Cow 补充：有序候选与区间最值

斜率优化 DP

• P5785 [SDOI2012] 任务安排 补充：经典斜率优化复盘
• P4360 [CEOI2004] 锯木厂选址 补充：分段型斜率优化

Part 4 字符串

KMP / 前缀函数

• CF25E Test 补充：字符串重叠关系与 KMP 复盘

Z 函数 / 扩展 KMP

• CF126B Password 补充：前缀、后缀与内部出现关系

AC 自动机

• P3966 [TJOI2013] 单词 补充：fail 关系与模式串包含统计

回文自动机 PAM

• P4287 [SHOI2011] 双倍回文 补充：回文结构关系与 PAM 应用

后缀数组 SA

• P2463 [SDOI2008] Sandy 的卡片 补充：差分与最长公共子串

Part 5 数学

Part 5.1 整数与基础数论

素数 / 筛法基础 / 因数分解

• P2441 角色属性树 补充：gcd 与公共质因子应用

GCD / exGCD / 裴蜀

• P3951 [NOIP2017 提高组] 小凯的疑惑 补充：两数 Frobenius 结论
• P5436 【XR-2】缘分 补充：gcd / lcm 性质分类

欧拉函数 / 欧拉定理

• P2303 [SDOI2012] Longge 的问题 补充：gcd 分类与欧拉函数复盘

Part 5.2 数论求和与高阶筛法

莫比乌斯反演

• P3455 [POI2007] ZAP-Queries 补充：二维 gcd 计数与 Möbius 分块复盘

Part 5.5 组合计数

排列组合 / 基础计数

• P4981 父子 补充：Cayley / Prüfer 结论应用

Catalan / Stirling 等特殊组合数

• P3200 [HNOI2009] 有趣的数列 补充：Catalan 数复盘
• P3978 [TJOI2015] 概率论 补充：Catalan 与组合结构复盘

Burnside / Pólya / 置换群

• P1446 [HNOI2008] Cards 补充：Burnside / Pólya 标准应用

Part 5.1 整数与基础数论

数论杂题 / 因子结构

• P5596 【XR-4】题 补充：因式分解、因子枚举与整除条件

Part 5.6 线性代数

矩阵快速幂 / 线性递推

• P1349 广义斐波那契数列 补充：一般二阶线性递推
• P5337 [TJOI2019] 甲苯先生的字符串 补充：有限状态邻接矩阵幂

Part 6 数据结构

Part 6.1 基础维护结构

单调栈 / 单调队列

• P3467 [POI2008] PLA-Postering 补充：单调栈维护轮廓
• P2866 [USACO06NOV] Bad Hair Day S 补充：基础单调栈计数

并查集

• P3958 [NOIP2017 提高组] 奶酪 补充：几何建图与普通并查集
• P1955 [NOI2015] 程序自动分析 补充：离散化与等价关系维护

堆 / 优先队列

• P2827 [NOIP2016 提高组] 蚯蚓 补充：多队列优化与大规模模拟
• P1801 黑匣子 补充：双堆与顺序统计

树状数组

• P1966 [NOIP2013 提高组] 火柴排队 补充：排名映射后的逆序对
• P1637 三元上升子序列 补充：多层树状数组计数
• P4113 [HEOI2012] 采花 补充：离线出现次数统计
• P3253 [JLOI2013] 删除物品 补充：动态删除后的相对位置统计

栈 / 括号结构复盘

• P1944 最长括号匹配 补充：括号结构的线性处理

Part 6.2 线段树家族

线段树

• P1198 [JSOI2008] 最大数 补充：在线追加与区间最值
• P2574 XOR的艺术 补充：区间翻转与区间统计
• P1558 色板游戏 补充：区间赋值与集合信息

Part 6.3 根号与离线算法

分块 / 根号算法

• P4135 作诗 补充：在线频率统计与预处理分块

莫队

• P3709 大爷的字符串题 补充：普通莫队上的频率信息维护

Part 6.4 可合并与可持久化结构

可并堆 / 左偏树

• P1456 Monkey King 补充：堆顶修改后重新合并

Part 6.5 平衡树与动态序列

平衡树 / 有序集合

• P5338 [TJOI2019] 甲苯先生的滚榜 补充：复合键修改与在线排名

Part 6.6 树上数据结构

树链剖分 / 树上路径数据结构

• P4092 [HEOI2016/TJOI2016] 树 补充：树上标记与最近祖先查询

Part 6.7 高维与专用数据结构

K-D Tree

• P4357 [CQOI2016] K 远点对 补充：远点搜索与 K-D Tree 剪枝
• P2479 [SDOI2010] 捉迷藏 补充：最近 / 最远邻点查询

Part 6.8 数据结构综合（已取消）

• P2161 [SHOI2009] 会场预约 补充：动态区间集合与有序结构维护

Part 7 图论与树论

Part 7.4 生成树

最小生成树及其扩展

• P1194 买礼物 补充：虚拟源点 MST 基础建模
• P2872 [USACO07DEC] Building Roads 补充：预连通与几何 MST

矩阵树定理

• P2144 [FJOI2007] 轮状病毒 补充：特殊图生成树计数与递推

Part 7.1 图遍历与最短路

最短路

• P1522 [USACO2.4] Cow Tours 补充：Floyd、连通块与直径综合

Part 7.2 树论基础

二叉树 / 递归树结构基础

• P1229 遍历问题 补充：遍历序列关系复盘

LCA / 树上差分 / 路径关系

• P3258 [JLOI2014] 松鼠的新家 补充：路径访问次数统计
• P4427 [BJOI2018] 求和 补充：LCA 与静态路径前缀统计
• P3038 [USACO11DEC] Grass Planting G 补充：路径增量维护

Part 7.5 有向图结构

拓扑排序 / DAG

• P1038 [NOIP2003 提高组] 神经网络 补充：拓扑传播与 DAG 状态累积

SCC / 缩点 DAG

• P3627 [APIO2009] 抢掠计划 补充：SCC 缩点与 DAG 最优路径

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

割点 / 点双连通 / 圆方树

• P5058 [ZJOI2004] 嗅探器 补充：指定点对断连与割点判定

Part 7.7 二分图

最大匹配 / 覆盖 / 匹配结构

• P1129 [ZJOI2007] 矩阵游戏 补充：行列完美匹配可行性

Part 7.8 网络流

最小割 / 最大权闭合子图

• P2598 [ZJOI2009] 狼和羊的故事 补充：网格二元标号与最小割

费用流

• P4016 负载平衡问题 补充：环形供需费用流
• P3356 火星探险问题 补充：网格多路径费用流
• P4013 数字梯形问题 补充：多组容量条件下的网格费用流

Part 7.9 树上高级技巧

原 7.9.4 树论综合（已取消）

• P5022 [NOIP2018 提高组] 旅行 补充：DFS 与基环树遍历综合

Part 8 计算几何

Part 8.1 计算几何基础

• P1578 [WC2002] 奶牛浴场 补充：二维空矩形与边界枚举综合