一、动态规划与递推类
动态规划是六级最核心的考点之一。
这一类题目通常不会直接告诉学生“这是 DP”，而是通过游戏、得分、划分、选择等背景，考察学生是否能抽象出状态和转移。
1. 基础递推与计数 DP
这类题目适合放在六级 DP 入门阶段，用来训练学生对“状态”和“转移”的基本理解。
P10376 [GESP202403 六级] 游戏
这类题的典型特征是：
每一步有若干种操作方式，问最终有多少种操作序列。
教学重点：
明确 的含义； 找到从哪些状态可以转移到当前状态； 注意边界条件； 注意取模。
这类题非常适合帮助学生从“递推”过渡到“动态规划”。
2. 路径选择型 DP
P10108 [GESP202312 六级] 闯关游戏 P15800 [GESP202603 六级] 选数
这类题通常给出一条线性结构，每个位置都有分数或代价，同时存在跳跃、间隔、限制等条件。
教学重点：
表示到达某个位置或处理到某个位置时的最优答案； 每个位置可以选择“取”或“不取”； 注意跳跃关系和合法位置； 最终答案可能不一定在最后一个位置。
这类题是六级中非常典型的 DP 模型，建议重点训练。
3. 分组与划分类 DP
P13015 [GESP202506 六级] 学习小组 P14075 [GESP202509 六级] 划分字符串
这类题的共同点是： 把一个整体划分成若干段或若干组，每一段、每一组有独立贡献，要求总价值最大或最小。
教学重点：
表示前 个元素处理完后的最优结果； 枚举最后一段或最后一组； 每一段是否合法需要快速判断； 注意时间复杂度不能退化成暴力枚举所有区间。
这类题比基础 DP 更进一步，能够训练学生“从最后一步思考”的能力。
4. 字符串 DP
P10721 [GESP202406 六级] 计算得分 P14075 [GESP202509 六级] 划分字符串
六级中的字符串题一般不考 KMP、Trie、后缀数组这类复杂字符串算法，而是更偏向：
字符串分段； 模式识别； 前缀状态； 动态规划。
教学重点：
把字符串看作一段线性序列； 识别局部合法结构； 用 DP 处理“前缀最优”； 避免暴力枚举所有子串。
这类题很适合放在 DP 专题后半部分讲。
二、背包问题与变形背包
背包是六级中非常重要的基础模型。 六级的背包题不仅考普通 01 背包，还会考“至少达到目标”“完全背包”“换维度背包”等变形。
1. 01 背包
B3873 [GESP202309 六级] 小杨买饮料
这是一道典型的 01 背包变形题。
题目本质是： 每种物品最多选择一次，要求在满足某个条件的前提下，使总代价最小。
教学重点：
每个物品只能选一次； 容量达到目标即可，不一定刚好等于目标； 超过目标的容量可以压缩到目标值； 需要倒序枚举容量。
这题适合作为六级背包入门题。
2. 完全背包
P11246 [GESP202409 六级] 小杨和整数拆分
这类题的特点是： 某些物品或数值可以重复使用，要求凑出目标值的最优方案。
教学重点：
物品可以重复选择； 完全背包要正序枚举； 通常表示凑出 的最优值； 注意初始化。
这题适合帮助学生区分 01 背包和完全背包。
3. 换维度背包
P14920 [GESP202512 六级] 道具商店
这类题的难点在于： 题目中某个限制很大，不能直接作为背包容量。
例如金币数量可能非常大，如果按金币作为容量，会超出复杂度限制。 此时需要换一个较小的维度来做 DP。
教学重点：
观察数据范围； 判断哪个维度可以作为 DP 数组下标； 将“最大收益”转化为“达到某收益的最小代价”； 最后再反向寻找答案。
这类题非常适合训练学生的数据范围分析能力。
三、树结构与树上问题
树是六级中的重点内容之一。 从历年真题来看，六级对树的考察已经不只是“会存树、会 DFS”，而是开始涉及祖先关系、树上状态传递、树形 DP、二叉树性质等内容。
1. 二叉树编号与基础操作
P11375 [GESP202412 六级] 树上游走
这类题主要考察完全二叉树的编号规律。
教学重点：
节点 的左儿子是 ； 节点 的右儿子是 ； 节点 的父亲是 ； 注意数据范围，需要使用 long long。
这类题适合作为树结构专题的入门题。
2. 树上祖先关系
P10109 [GESP202312 六级] 工作沟通
这类题把现实中的上下级关系抽象成一棵有根树。 问题本质往往是寻找公共祖先。
教学重点：
管理关系等价于树上的祖先关系； 多个节点的共同管理者就是公共祖先； 数据范围较小时可以用朴素方法解决； 重点是理解树上“向上走”的过程。
这题适合放在 LCA 正式学习之前，作为祖先关系的铺垫题。
3. 树上状态传递
P10722 [GESP202406 六级] 二叉树
这类题通常给出对子树的操作，要求最后得到每个节点的状态。
教学重点：
子树操作不一定要逐个节点修改； 操作次数只关心奇偶时，可以用异或或取模； DFS 时把祖先状态传递给子节点； 本质是树上的差分思想。
这类题非常适合讲“树上操作不能暴力做”的思想。
4. 树的二分图性质
P11962 [GESP202503 六级] 树上漫步
树天然是一张二分图。 从某个点出发，走偶数步后能到达的点，与它在同一个颜色集合中。
教学重点：
对树进行黑白染色； 两点距离的奇偶性由染色决定； 统计每种颜色的点数； 每个点的答案与自身颜色有关。
这是一道非常好的“树 + 图论性质”入门题。
5. 树上遍历与路径代价
P14076 [GESP202509 六级] 货物运输
这类题通常与“遍历整棵树”有关。
教学重点：
如果要求从根出发并回到根，每条边通常要走两次； 如果最后不需要回到根，可以节省一条根到终点的路径； 为了使总代价最小，应让节省的路径尽可能长； 本质是树上 DFS 与最长根路径的结合。
这类题能很好地训练学生从“边的贡献”角度分析树。
6. 树形 DP 与树上覆盖
P14919 [GESP202512 六级] 路径覆盖
这类题已经进入六级中偏难的树形 DP 范围。
教学重点：
每个子树可以独立考虑； 选择当前节点可能一次性覆盖多条路径； 不选当前节点时，需要在儿子子树中分别解决； 状态转移通常来自“选当前点”与“不选当前点”的比较。
这题适合放在树形 DP 入门之后讲。
7. 二叉树性质综合判断
P15801 [GESP202603 六级] 完全二叉树
这类题综合性较强，需要学生同时维护多个树上信息。
教学重点：
子树大小； 子树高度； 是否为满二叉树； 是否为完全二叉树； 左右子树信息如何合并。
这题适合作为六级树专题的压轴题。
四、排序、统计与贪心
六级中的排序题不只是考会不会排序，而是常常和统计、贪心、交换论证结合在一起。
1. 归并排序统计
B3874 [GESP202309 六级] 小杨的握手问题
这类题表面是模拟过程，实际上考察的是统计前面有多少数满足某种大小关系。
教学重点：
暴力枚举会超时； 可以转化为顺序对或逆序对统计； 用归并排序统计贡献； 也可以用树状数组，但六级阶段更推荐先掌握归并排序做法。
这题是排序专题中非常重要的一题。
2. 排序贪心与交换论证
P11376 [GESP202412 六级] 运送物资
这类题往往需要先把代价公式化简，再发现排序规则。
教学重点：
不要急着模拟； 先写出每个对象的贡献； 去掉与选择无关的常数； 根据关键系数排序； 用交换论证证明贪心正确性。
这类题偏难，但非常适合训练学生的建模能力。
3. 分类统计与可行性判断
P11247 [GESP202409 六级] 算法学习
这类题不一定是标准 DP，也不一定是标准贪心，而是要求学生通过分类统计判断方案是否可行。
教学重点：
按类别统计数量； 先满足每一类的最低要求； 再判断整体排列是否满足限制； 注意“最多的一类是否过多”这类经典可行性条件。
这类题很适合训练学生的综合分析能力。
五、线性序列与最大子段类问题
P11963 [GESP202503 六级] 环线
这类题通常与最大子段和、环形序列、前缀和有关。
教学重点：
先理解普通最大子段和； 再处理环形结构； 环形问题常见做法是断环成链； 注意全负数等特殊情况。
这类题适合作为 DP 与前缀和之间的过渡题。
六、数学建模与数论思想
六级中也会出现一些代码不一定很长，但思维要求较高的题目。 这类题的关键不是套模板，而是发现题目背后的数学结构。
1. 因数关系建树
P13016 [GESP202506 六级] 最大因数
这题的核心在于理解：
一个数的最大真因数，等于这个数除以它的最小质因数。
因此题目可以转化为： 不断除以最小质因数，形成一条向上的路径。
教学重点：
最大真因数与最小质因数的关系； 因数分解； 把数字关系抽象成树； 在树上求两个点的距离。
这是一道非常典型的“数学性质 + 树模型”综合题。
2. 小规模搜索与排列枚举
P10377 [GESP202403 六级] 好斗的牛
这类题的数据范围通常很小，例如 不大。 看到这种数据范围时，应优先考虑搜索、枚举、状态压缩等方法。
教学重点：
不要被题面背景吓住； 先看关键数据范围； 小规模问题可以枚举排列； 枚举后再计算对应方案是否合法或代价最小。
这类题适合训练学生的数据范围敏感度。
按难度梯度整理
如果用于日常训练，不建议直接按照考试时间顺序刷题。更合理的方式是按照能力梯度分层训练。
第一梯度：六级基础题
适合刚进入六级的学生。
这一阶段的目标是：
让学生会从题目中提取状态、转移、父子关系和基础模型。
第二梯度：六级核心题
适合学生已经掌握基础 DP、树和排序后训练。
这一阶段是六级备考的重点。
这些题目覆盖了六级最常见的算法模型。
第三梯度：六级提高题
适合用来训练综合建模能力。
这一阶段的题目不一定模板明显，需要学生主动分析数据范围和题目结构。
第四梯度：六级压轴题
适合放在专题学习之后作为综合训练。
这些题目对建模能力、证明能力和代码实现能力都有一定要求，适合作为六级冲刺题。
