ARTICLE · 1152070
CSP-J历年复赛真题知道点统计分析
一、历年题目总览（2019-2025）
年份 | T1 | T2 | T3 | T4 |
2019 | 数字游戏 | 公交换乘 | 纪念品 | 加工零件 |
2020 | 优秀的拆分 | 直播获奖 | 表达式 | 方格取数 |
2021 | 分糖果 | 插入排序 | 网络连接 | 小熊的果篮 |
2022 | 乘方 | 解密 | 逻辑表达式 | 上升点列 |
2023 | 小苹果 | 公路 | 一元二次方程 | 旅游巴士 |
2024 | 扑克牌 | 地图探险 | 小木棍 | 接龙 |
2025 | 拼数 | 座位 | 异或和 | 多边形 |
二、高频考点分类及对应题目
1. 模拟与字符串处理
考点 | 对应题目 | 说明 |
字符串遍历计数 | 2019 T1 数字游戏、2024 T1 扑克牌 | 直接遍历，统计字符或标记去重 |
字符串解析与条件判断 | 2021 T3 网络连接 | IP 地址合法性校验，多分支判断 |
字符串过滤与桶计数 | 2025 T1 拼数 | 过滤字母，统计数字出现次数，降序输出 |
二维网格模拟 | 2024 T2 地图探险 | 方向数组、右转、边界与障碍判断 |
链表模拟 | 2021 T4 小熊的果篮 | 双向链表维护前驱后继，删除块头，过滤合并 |
队列模拟 | 2019 T2 公交换乘 | 队列维护优惠票，过期清理，优先最早票 |
栈模拟表达式 | 2020 T3 表达式、2022 T3 逻辑表达式 | 可建树，也可栈直接模拟，短路统计 |
2. 数学与数论
考点 | 对应题目 | 说明 |
奇偶性判断 | 2020 T1 优秀的拆分 | 奇数无解，偶数拆二进制 |
取模与区间分类 | 2021 T1 分糖果 | 比较 L/n 与R/n，取最大余数 |
循环累乘与防溢出 | 2022 T1 乘方 | 特判 a=1，边乘边判断是否超过 1e9 |
递推与对数迭代 | 2023 T1 小苹果 | 每天剩余 m = 2m/3，迭代约 50 次 |
韦达定理与一元二次方程 | 2022 T2 解密 | 推导 p+q = n - e*d + 2，判别式，整数平方根 |
判别式与根式化简 | 2023 T3 一元二次方程 | 分数约分，剥离平方因子，格式化输出 |
子集和与组合计数 | 2025 T4 多边形 | 排序枚举最大值，DP 统计子集和，取模 |
前缀异或 | 2025 T3 异或和 | 区间异或转前缀异或，贪心选不相交区间 |
3. 动态规划（DP）
考点 | 对应题目 | 说明 |
完全背包 | 2019 T3 纪念品 | 两天之间买卖等价完全背包，容量正序遍历 |
消除后效性 DP | 2020 T4 方格取数 | 三维 DP 增加方向维度 / 按列两次扫描 |
曼哈顿距离 DP | 2022 T4 上升点列 | 排序后DP，新增点数 = 曼哈顿 - 1，剩余点数加末尾 |
DP + 特殊标记技巧 | 2024 T4 接龙 | 记录最后接龙人，-1 表示多解，窗口扫描 |
子集和 DP | 2025 T4 多边形 | 枚举最大值，DP 统计子集和，over 记录溢出 |
桶计数 DP | 2020 T2 直播获奖 | 成绩值域小，桶计数，从高到低累加找第 k 大 |
4. 图论
考点 | 对应题目 | 说明 |
奇偶分层 BFS | 2019 T4 加工零件 | 判断是否存在长度 L 的路径，维护最短奇偶距离 |
分层图 Dijkstra | 2023 T4 旅游巴士 | 时间模 k 作为状态，计算等待时间，求最短路 |
有向/无向图建模 | 2019 T4 加工零件、2023 T4 旅游巴士 | 分清方向，边权相等用 BFS，不等用 Dijkstra |
5. 数据结构
考点 | 对应题目 | 说明 |
栈（表达式求值） | 2020 T3 表达式、2022 T3 逻辑表达式 | 后缀建树 / 双栈中缀，也可不建树直接栈模拟 |
队列（FIFO） | 2019 T2 公交换乘 | 优惠票队列，过期弹出，优先最早 |
双向链表 | 2021 T4 小熊的果篮 | 快速删除节点，维护块头，过滤合并 |
哈希表（map） | 2021 T3 网络连接 | 地址到服务机编号映射，去重与查找 |
数组标记（桶） | 2020 T2 直播获奖、2025 T3 异或和 | 值域小，用数组代替map，降低常数 |
优先队列（Dijkstra） | 2023 T4 旅游巴士 | 分层图最短路，优先队列优化 |
6. 贪心
考点 | 对应题目 | 说明 |
前缀最小油价 | 2023 T2 公路 | 维护最低油价，向上取整，剩余油量维护 |
结束最早区间 | 2025 T3 异或和 | 贪心选不相交区间，最大化数量 |
位数优先构造大数 | 2024 T3 小木棍 | 优先用8，按余数分类构造最小数 |
排序枚举最大值 | 2025 T4 多边形 | 排序后枚举最大值，避免重复计数 |
7. 排序与查找
考点 | 对应题目 | 说明 |
稳定排序 | 2021 T2 插入排序 | 值相等按下标排序，维护 pos 数组 |
桶计数排序 | 2020 T2 直播获奖、2025 T1 拼数 | 值域小，计数排序思想 |
二分/整数平方根 | 2022 T2 解密 | 判断完全平方数，避免浮点误差 免浮点误差 |
8. 位运算与二进制
考点 | 对应题目 | 说明 |
二进制拆分 | 2020 T1 优秀的拆分 | 提取二进制中为 1 的位 |
前缀异或 | 2025 T3 异或和 | 区间异或转前缀异或，贪心选区间（非 ，贪心选区间（非DP） |
9. 组合计数
考点 | 对应题目 | 说明 |
子集和计数 | 2025 T4 多边形 | DP 统计子集和，累加贡献，取模 |
方案数统计 | 2025 T4 多边形 | 排序枚举最大值，避免重复计数 |
10. 其他高频技巧
考点 | 对应题目 | 说明 |
向上取整 | 2023 T2 公路、2022 T1 乘方 | (a + b - 1) / b |
多组数据初始化 | 2024 T2 地图探险、2024 T4 接龙 | 每组数据清空数组/标记 |
防溢出 | 2022 T1 乘方、2023 T2 公路、2025 T4 多边形 | 使用 long long，乘法前预判 |
输出格式 | 2023 T3 一元二次方程、2024 T4 接龙 | 严格按题目要求，无空格，多行输出 |
三、知识点融合
题目 | 融合知识点 |
2023 T4 旅游巴士 | 图论 Dijkstra + 分层状态（时间模k） |
2019 T3 纪念品 | DP 完全背包 + 贪心（只取正差价） |
2021 T4 小熊的果篮 | 双向链表 + 队列维护块头 + 过滤合并 |
2024 T4 接龙 | DP + 特殊标记 -1 + 窗口扫描 + 多组初始化 |
2025 T4 多边形 | 排序 + DP 子集和 + 组合计数 + 取模 |
2022 T4 上升点列 | 排序 + DP + 曼哈顿距离转化 + 剩余点数处理 |
2020 T4 方格取数 | DP + 方向状态设计 + 负无穷初始化 |
2021 T3 网络连接 | 字符串解析 + 哈希 map + 多分支条件判断 |
- 模拟与字符串处理：10+ 次
- 数学与数论：8 次
- 数据结构（栈、队列、链表、哈希）：8 次
- 动态规划（DP）：6 次
- 贪心：5 次
- 排序与查找：4 次
- 图论：3 次
- 位运算与二进制：3 次（含前缀异或）
- 组合计数：2 次
- 前缀和/前缀异或：2 次
五、易错点速查清单
- 字符串当整数读入 → 丢前导0；
- 字符'1'与数字1混淆；
- 没有去重，重复统计；
- 大范围暴力循环 → TLE；
- 漏特判：奇数、a=1、等于边界；
- int溢出；
- 分类讨论不全；
- 输出格式：空格、-1、多空格；
- 结果巨大却用整数存 → 溢出；
- 只选部分数字，没有用满所有可用数字；
- 多组数据忘记清空数组/标记；
- 递归处理长字符串/大图 → 栈溢出；
- 边权不等却用 BFS；
- DP 非法状态未赋值负无穷；
- 浮点数sqrt判断完全平方 → 精度错误。