训练题单

第一章 算法分析与解题方法

本章不追求复杂算法，重点是把题意转换成可执行过程，并根据数据范围、重复工作、整数范围和边界条件判断做法是否成立。

顺序	阶段	题目	主要训练点
1	基础	P1046 [NOIP 2005 普及组] 陶陶摘苹果	明确统计对象，按条件扫描输入
2	基础	P5718 【深基4.例2】找最小值	维护当前最优值与循环不变量
3	基础	P1085 [NOIP 2004 普及组] 不高兴的津津	门槛、并列规则与最早位置
4	基础	P5660 [CSP-J 2019] 数字游戏	从题意提取真正需要统计的信息
5	巩固	P1047 [NOIP 2005 普及组] 校门外的树	用位置状态避免重复扣除，检查端点
6	巩固	P2141 [NOIP 2014 普及组] 珠心算测验	从直接枚举到和值预处理，区分数值与位置
7	巩固	P8813 [CSP-J 2022] 乘方	利用输出上限提前停止，并在乘法前防溢出
8	巩固	P9748 [CSP-J 2023] 小苹果	分析每轮变化量，减少无效逐项模拟
9	巩固	P11227 [CSP-J 2024] 扑克牌	找到决定答案的缺失量，避免枚举构造
10	提高	P7072 [CSP-J 2020] 直播获奖	根据值域选择统计结构，分析在线更新开销
11	提高	P7910 [CSP-J 2021] 插入排序	根据部分有序性质缩小更新范围，区分算法与实现复杂度

第二章 枚举与模拟

训练顺序从确定枚举对象开始，逐步进入网格、字符串、环形位置、有限状态和规则枚举。每道题都应先写清“枚举什么”和“过程状态是什么”。

顺序	阶段	题目	主要训练点
1	基础	P1980 [NOIP 2013 普及组] 计数问题	枚举整数并拆分数位
2	基础	P1179 [NOIP 2010 普及组] 数字统计	重复训练数位枚举，检查数字 0 的处理
3	基础	P1618 三连击（升级版）	利用比例关系减少枚举变量，检查数位集合
4	基础	P1003 [NOIP 2011 提高组] 铺地毯	调整枚举顺序，利用“最后覆盖”规则
5	基础	P1042 [NOIP 2003 普及组] 乒乓球	按输入顺序维护比分与局结束条件
6	巩固	P2670 [NOIP 2015 普及组] 扫雷游戏	网格邻居枚举与边界判断
7	巩固	P1101 单词方阵	枚举起点和固定方向，标记完整匹配结果
8	巩固	P2010 [NOIP 2016 普及组] 回文日期	构造候选后验证日期合法性
9	巩固	P1308 [NOIP 2011 普及组] 统计单词数	字符串规范化与完整单词边界
10	巩固	P1563 [NOIP 2016 提高组] 玩具谜题	环形位置、方向组合与取余
11	巩固	P1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布	同时维护两个周期序列的位置
12	提高	P1518 [USACO 2.4] 两只塔姆沃斯牛	完整状态表示、重复状态与无解终止
13	提高	CF908B New Year and Buggy Bot	枚举未知规则映射，再执行网格模拟
14	提高	P7911 [CSP-J 2021] 网络连接	字符串格式校验、规范表示与状态记录
15	提高	P1095 [NOIP 2007 普及组] 守望者的逃离	同步模拟两种行动结果，分清旧状态与新状态

第三章 排序与结构化比较

本章题目依次覆盖基础排序、去重、计数排序、多关键字比较、字符串排序和动态排名。使用 $sort$ 前，应先用自然语言写出比较规则。

顺序	阶段	题目	主要训练点
1	基础	P1177 【模板】排序	熟悉排序接口，并可用基础排序核对小数据
2	基础	P1059 [NOIP 2006 普及组] 明明的随机数	排序后去重或使用布尔桶
3	基础	P1271 【深基9.例1】选举学生会	小值域计数排序，按频次恢复序列
4	基础	P1093 [NOIP 2007 普及组] 奖学金	三关键字排序与原编号保存
5	巩固	P1104 生日	日期字段比较与稳定次序
6	巩固	P5143 攀爬者	结构体排序后扫描相邻对象
7	巩固	P1068 [NOIP 2009 普及组] 分数线划定	排名规则、同分边界与实际录取人数
8	巩固	P1781 宇宙总统	超长整数的字符串比较与原位置
9	巩固	P1012 [NOIP 1998 提高组] 拼数	用拼接结果定义字符串比较顺序
10	巩固	P14357 [CSP-J 2025] 拼数	新题训练：按字符值域计数并构造最大整数
11	提高	P7072 [CSP-J 2020] 直播获奖	在线排名与小值域频次统计
12	提高	P1923 【深基9.例4】求第 k 小的数	从完整排序过渡到只确定一个排名
13	提高	P7910 [CSP-J 2021] 插入排序	单点修改后的局部有序性与名次维护

第四章 前缀和、差分与离散化

这一章的核心问题是“哪些重复计算可以统一预处理”。做题时应区分点值、区间和、区间增量、覆盖次数以及原坐标距离。

顺序	阶段	题目	主要训练点
1	基础	P8218 【深进1.例1】求区间和	一维前缀和与边界前缀
2	基础	P5638 【CSGRound2】光骓者的荣耀	固定长度区间和与“总量减去最优区间”
3	巩固	P3131 [USACO16JAN] Subsequences Summing to Sevens S	前缀和取模、相同余数与最长区间
4	基础	P2004 领地选择	二维前缀和与固定矩形枚举
5	巩固	P1387 最大正方形	二维区域和判断与边长枚举
6	基础	P2367 语文成绩	一维差分、区间修改与还原
7	巩固	P3397 地毯	二维差分的四角标记
8	巩固	P1047 [NOIP 2005 普及组] 校门外的树	整数闭区间差分与右端点后一位撤销
9	巩固	P1496 火烧赤壁	大坐标离散化与区间并集长度
10	提高	P3406 海底高铁	在相邻位置之间的边上做差分
11	提高	P1083 [NOIP 2012 提高组] 借教室	用差分批量检查操作前缀，二分部分可后做
12	提高	P4552 [Poetize6] IncDec Sequence	把区间操作转换成差分数组上的端点变化

第五章 双指针与区间扫描

本章按“两个端点为什么只向一个方向移动”组织。区间题应先确定闭区间或半开区间，再决定相接、重叠和长度的处理方式。

顺序	阶段	题目	主要训练点
1	基础	P1147 [NOIP 2001 普及组] 连续自然数和	正数序列上的同向双指针
2	基础	P1102 A-B 数对	有序序列中的双边界与重复值计数
3	基础	P1094 [NOIP 2007 普及组] 纪念品分组	首尾双指针，每轮处理最贵物品
4	巩固	P3143 [USACO16OPEN] Diamond Collector S	排序、滑动窗口与两个不相交区间
5	巩固	P1638 逛画展	最短覆盖窗口、频次与种类数
6	基础	P2082 区间覆盖（加强版）	排序后合并区间并计算覆盖长度
7	巩固	P2434 [SDOI2005] 区间	输出最少的不相交合并区间
8	巩固	P1496 火烧赤壁	从离散化角度再次训练区间并集
9	提高	P1904 天际线	把建筑端点视为事件，维护轮廓变化
10	提高	P1886 滑动窗口	固定窗口双指针与单调队列，建议学完第九章后完成
11	提高	P2216 [HAOI2007] 理想的正方形	二维固定窗口最值，综合单调队列

第六章 二分与倍增

前 3 题训练有序数组边界，随后集中练习二分答案。最后两题是倍增的跨章综合题，需要结合树或单调栈。

顺序	阶段	题目	主要训练点
1	基础	P2249 【深基13.例1】查找	查找第一次出现位置与不存在的情况
2	基础	P1102 A-B 数对	使用上下边界统计重复值数量
3	巩固	P1678 烦恼的高考志愿	二分插入位置并比较左右邻居
4	基础	P1873 [COCI 2011/2012] 砍树	最大可行值与线性判定函数
5	基础	P2440 木材加工	二分长度，处理零答案与除法计数
6	巩固	P1824 [USACO05FEB] 进击的奶牛	最大化最小距离与贪心判定
7	巩固	P2678 [NOIP 2015 提高组] 跳石头	最大化最小距离，判定最少移除数量
8	巩固	P1182 数列分段 Section II	最小化最大段和与顺序分段判定
9	巩固	P3853 [TJOI2007] 路标设置	最小化最大间距，推导新增路标数量
10	提高	P1083 [NOIP 2012 提高组] 借教室	二分第一个失败的操作前缀，判定中结合差分
11	巩固	P1577 切绳子	实数或定点二分与输出精度
12	提高	P1024 [NOIP 2001 提高组] 一元三次方程求解	连续函数求根、根区间与精度控制
13	提高	CF448D Multiplication Table	二分隐式乘法表中的第 $k$ 小值，重复值按次数保留
14	提高	P1419 寻找段落	二分最大平均值并转化为前缀和判定，建议学完第九章后完成
15	提高	P3379 【模板】最近公共祖先（LCA）	倍增拼接 $2^k$ 级跳跃，建议学完第十一章后完成
16	提高	P7167 [eJOI 2020] Fountain (Day1)	单调栈确定后继，再用倍增累计跳跃代价

第七章 递推、递归与分治

训练顺序与第七章：递推、递归与分治保持一致：先比较递推与递归，再练递归构造，随后进入归并、逆序对和快速幂，最后复用有序结果。

顺序	阶段	题目	主要训练点
1	基础	P1192 台阶问题	定义状态、初值和递推顺序
2	巩固	P1255 数楼梯	楼梯递推与大整数，建议学完第十三章后补全
3	基础	P1028 [NOIP 2001 普及组] 数的计算	从递归定义推导递推式
4	巩固	P1044 [NOIP 2003 普及组] 栈	按最后一步或分界点分类计数
5	基础	P1010 [NOIP 1998 普及组] 幂次方	递归构造嵌套输出
6	巩固	P1928 外星密码	递归解析嵌套字符串并组合返回结果
7	提高	P3612 [USACO17JAN] Secret Cow Code S	不构造巨大字符串，递归缩小查询位置
8	基础	P1177 【模板】排序	独立实现归并排序并与 $sort$ 对拍
9	巩固	P1908 逆序对	在归并时批量统计跨区间贡献
10	巩固	P1774 最接近神的人	把相邻交换次数转化为逆序对数量
11	基础	P1226 【模板】快速幂	二进制拆分指数与模运算
12	提高	P3390 【模板】矩阵快速幂	补充矩阵乘法后，把快速幂的乘法对象推广为矩阵
13	提高	P1309 [NOIP 2011 普及组] 瑞士轮	证明胜者、败者分别有序，再线性归并

第八章 贪心与简单构造

本章先练习排序后选择，再进入区间贪心、交换论证和从左向右修复约束。每次写出贪心选择后，都应尝试说明为什么局部选择不会破坏最优解。

顺序	阶段	题目	主要训练点
1	基础	P2240 【深基12.例1】部分背包问题	按单位收益排序，允许取部分物品
2	基础	P1208 [USACO1.3] 混合牛奶	按单价排序后依次购买
3	基础	P1223 排队接水	用交换论证确定等待时间的排序规则
4	基础	P1803 凌乱的 yyyy / 线段覆盖	按结束时间选择最多不相交区间
5	巩固	P1094 [NOIP 2007 普及组] 纪念品分组	首尾配对选择与交换论证
6	巩固	P3817 小 A 的糖果	从左向右做满足约束的最小修改
7	巩固	P1056 [NOIP 2008 普及组] 排座椅	统计每条分隔线的收益并选取最大者
8	巩固	P1106 删数问题	删除一个局部下降位置，使高位尽量小
9	巩固	P5019 [NOIP 2018 提高组] 铺设道路	只为相邻高度的正增长付出新代价
10	提高	P4447 [AHOI2018 初中组] 分组	排序后把当前值接到最需要延长的序列
11	提高	P1090 [NOIP 2004 提高组] 合并果子	每次合并最小两项，结合小根堆实现
12	提高	P4995 跳跳！	交替选择两端，构造较大的平方差总和

第九章 栈、队列、堆与常用容器

本章先按操作语义选择普通容器，再练习单调栈和单调队列。后两类结构的关键不是模板，而是说明某个候选为什么可以永久删除。

顺序	阶段	题目	主要训练点
1	基础	P1739 表达式括号匹配	用栈维护尚未匹配的左括号
2	基础	P4387 【深基15.习9】验证栈序列	按入栈次序模拟指定出栈序列
3	基础	P1449 后缀表达式	操作数栈与运算符执行顺序
4	巩固	P1981 [NOIP 2013 普及组] 表达式求值	利用栈或分段处理乘法优先级
5	巩固	P1175 表达式的转换	中缀转后缀与运算符栈
6	基础	P1540 [NOIP 2010 提高组] 机器翻译	按进入顺序淘汰的定长队列
7	巩固	P2058 [NOIP 2016 普及组] 海港	按时间淘汰整批记录并维护频次
8	基础	P3378 【模板】堆	小根堆的插入、查询与删除
9	巩固	P1090 [NOIP 2004 提高组] 合并果子	用优先队列反复取得最小两项
10	基础	P5788 【模板】单调栈	查找右侧第一个更大元素
11	巩固	P2947 [USACO09MAR] Look Up S	最近更高位置与栈内候选顺序
12	巩固	P2866 [USACO06NOV] Bad Hair Day S	统计可见关系，批量结算单调栈贡献
13	基础	P1886 滑动窗口	队首过期、队尾淘汰与窗口最值
14	巩固	P2032 扫描	只维护固定窗口最大值
15	巩固	P1160 队列安排	双向链表插入、删除与失效标记

第十章 搜索与回溯

建议为每道搜索题先写出状态、选择、终止条件和判重方式，再决定使用 DFS 或 BFS。前 5 题集中训练递归枚举，之后进入最短步数、Flood Fill、多源 BFS 和剪枝。

顺序	阶段	题目	主要训练点
1	基础	P1706 全排列问题	按位置选择元素并恢复使用标记
2	基础	P2089 烤鸡	固定分支数的递归枚举与和剪枝
3	基础	P1036 [NOIP 2002 普及组] 选数	组合枚举、起点限制与质数判断
4	巩固	P1219 [USACO 1.5] 八皇后	行、列、对角线状态与回溯恢复
5	巩固	P2036 [COCI 2008/2009] PERKET	子集搜索、空集排除与最优值维护
6	基础	P1605 迷宫	DFS 统计简单路径并恢复访问状态
7	基础	P1443 马的遍历	BFS 分层与最短步数
8	巩固	P1135 奇怪的电梯	一维状态图上的 BFS 与边界
9	基础	P1451 求细胞数量	Flood Fill 与连通块计数
10	巩固	P1596 [USACO10OCT] Lake Counting S	八方向连通块与网格判重
11	巩固	P1162 填涂颜色	从外部灌水区分被包围区域
12	巩固	P1332 血色先锋队	多源 BFS 与最早到达时间
13	提高	P2895 [USACO08FEB] Meteor Shower S	随时间变化的危险区域与无界网格 BFS
14	提高	P1141 01迷宫	预处理连通块答案，复用多次查询结果
15	提高	P3956 [NOIP 2017 普及组] 棋盘	带代价状态搜索、可行性限制与最优性剪枝

第十一章 树与图基础

前 3 题训练图的存储和可达性，随后集中练习二叉树遍历、由遍历序列恢复结构、子树信息和二叉搜索树。最后两题分别连接哈夫曼树与倍增。

顺序	阶段	题目	主要训练点
1	基础	P5318 【深基18.例3】查找文献	邻接表、按编号访问的 DFS 与 BFS
2	巩固	P3916 图的遍历	反向建图与多起点可达性传播
3	巩固	P2853 [USACO06DEC] Cow Picnic S	从多个起点遍历并累计可达次数
4	基础	P4913 【深基16.例3】二叉树深度	根据孩子编号递归计算树高
5	基础	P1305 新二叉树	保存左右孩子并执行先序遍历
6	巩固	P1030 [NOIP 2001 普及组] 求先序排列	根据中序与后序划分左右子树
7	巩固	P1827 [USACO3.4] 美国血统	再次训练由遍历序列恢复结构
8	巩固	P1087 [NOIP 2004 普及组] FBI 树	完全二叉划分、结点分类与后序输出
9	提高	P5018 [NOIP 2018 普及组] 对称二叉树	子树大小、镜像比较与重复子问题
10	提高	P2052 [NOI 2011] 道路修建	用子树大小计算一条边两侧的点数
11	巩固	P5076 【深基16.例7】普通二叉树（简化版）	二叉搜索树的插入、排名、前驱和后继
12	巩固	P1090 [NOIP 2004 提高组] 合并果子	从贪心合并理解哈夫曼树的带权路径长度
13	提高	P3379 【模板】最近公共祖先（LCA）	树上深度、父结点与倍增跳祖先

第十二章 动态规划入门

本章模型较多，因此题量相对更大。建议先完成线性与网格 DP，再集中训练背包，最后处理最长上升子序列、区间 DP 和综合计数。每道题都应先写状态含义，再写转移来源。

顺序	阶段	题目	主要训练点
1	基础	P1216 [USACO1.5] 数字三角形	从上一层相邻状态转移，处理边界
2	基础	P1115 最大子段和	以当前位置结尾的最优值与全局答案
3	巩固	P1280 尼克的任务	按时间位置设计状态并选择计算方向
4	基础	P1002 [NOIP 2002 普及组] 过河卒	网格路径计数、禁用位置与边界初始化
5	巩固	P1004 [NOIP 2000 提高组] 方格取数	两条同步路径与多维状态
6	巩固	P1434 [SHOI 2002] 滑雪	DAG 上的记忆化搜索与最长路径
7	基础	P1048 [NOIP 2005 普及组] 采药	0/1 背包与容量倒序
8	基础	P1060 [NOIP 2006 普及组] 开心的金明	把价值表达式转换成 0/1 背包收益
9	巩固	P1049 [NOIP 2001 普及组] 装箱问题	最大可用容量与剩余空间转换
10	基础	P1616 疯狂的采药	完全背包与容量正序
11	巩固	P1164 小 A 点菜	0/1 背包的方案计数
12	巩固	P1077 [NOIP 2012 普及组] 摆花	有限数量选择与计数型 DP
13	巩固	P1757 通天之分组背包	每组至多选择一件物品
14	提高	P1064 [NOIP 2006 提高组] 金明的预算方案	主件、附件依赖与合法组合枚举
15	巩固	P1091 [NOIP 2004 提高组] 合唱队形	正反两个最长上升状态的合并
16	提高	P1020 [NOIP 1999 提高组] 导弹拦截	最长不上升子序列与最少系统数
17	基础	P1775 石子合并（弱化版）	区间 DP、断点枚举与区间和
18	巩固	P1880 [NOI 1995] 石子合并	环形区间复制、最小值与最大值
19	提高	P2758 编辑距离	二维字符串 DP 与三类末尾操作
20	提高	P14360 [CSP-J 2025] 多边形	新题训练：排序固定最大值，再做背包方案计数

第十三章 数学基础、位运算与高精度

本章跨度最大，建议按“进制与位运算—数论—计数—高精度”的顺序分组完成。高精度题应先在纸上完成一遍竖式，再写数组或字符串实现。

顺序	阶段	题目	主要训练点
1	基础	P1143 进制转换	任意进制读入与目标进制输出
2	巩固	P1017 [NOIP 2000 提高组] 进制转换	负进制表示与非负余数调整
3	基础	P1100 高低位交换	位移、掩码与固定宽度整数
4	基础	P7071 [CSP-J 2020] 优秀的拆分	判断二进制位并按降序输出幂
5	巩固	P1582 倒水	$lowbit$、二进制中 $1$ 的数量与构造
6	提高	P14359 [CSP-J 2025] 异或和	新题训练：前缀异或与不相交区间选择
7	基础	P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题	最大公约数、最小公倍数与因数枚举
8	基础	P1075 [NOIP 2012 普及组] 质因数分解	试除法与最小质因数
9	基础	P3383 【模板】线性筛素数	埃氏筛与线性筛，查询第若干个质数
10	巩固	P1865 A % B Problem	筛法、质数频次前缀和与区间询问
11	基础	P1226 【模板】快速幂	模运算与二进制快速幂
12	巩固	P2822 [NOIP 2016 提高组] 组合数问题	递推组合数，再用二维前缀统计模意义下的零
13	提高	P1313 [NOIP 2011 提高组] 计算系数	二项式系数与组合数递推
14	基础	P1088 [NOIP 2004 普及组] 火星人	排列的字典序与后继排列
15	基础	P1601 A+B Problem（高精）	高精度加法与进位
16	基础	P2142 高精度减法	大小比较、借位与负号
17	巩固	P1303 A*B Problem	高精度乘法与跨位进位
18	巩固	P1480 A/B Problem	高精度除以低精度与余数维护
19	巩固	P1009 [NOIP 1998 普及组] 阶乘之和	高精度乘法与累加的组合实现
20	提高	P1045 [NOIP 2003 普及组] 麦森数	快速幂、高精度截位与格式化输出
21	基础	P1888 三角函数	三角形边排序、分数约分与整数范围