CSP-OI赛制说明

CSP-J/S 2025（第二轮）广东省认证者须知

CSP-J/S 2025（第二轮）广东省认证考生注意事项

CSP-J复赛题型分布：

第一题：基本语法 数学基础运算

第二题：模拟 枚举 贪心 排序 二分 高精度

第三题：动归 搜索 数论

第四题：动归(进阶) 图论 树

题型解析

第一题：基本语法、数学基础运算。

第一题始终是入门门槛题，核心考察基础代码编写能力（如循环、条件判断）和简单数学应用（如最大公约数、素数判断），不涉及复杂算法，确保多数考生能得分。

第二题：模拟、贪心、排序、枚举、二分、高精度。

第二题是基础算法的集中考查区，模拟是绝对高频考点，常结合字符串、日期等场景；贪心、排序、枚举则是高频辅助算法，有时也会加入二分、高精度等基础算法。

第三题：动归、搜索、数论。

第三题是区分度提升的关键题，动态规划（如线性 DP） 和搜索（DFS/BFS，需剪枝优化） 是绝对主力，数论则多为中等难度应用（如同余定理、组合计数），偶尔会加入字符串复杂处理（如 KMP），但核心不脱离上述三类。

第四题：动归(进阶)、图论、树。

第四题是难度巅峰，聚焦复杂算法与数据结构：动态规划常以二维 DP、状态压缩 DP 形式出现；图论（最短路径、拓扑排序）和树（树形 DP、树的遍历）是高频考点，有时会结合搜索（如树上 DFS），但核心始终围绕上述三类展开。

对应真题清单

第一题：基本语法、数学基础运算

例题 1（2023 CSP-J T1）：乘方

考点：基本语法（循环 / 快速幂实现）、数学运算（指数计算）、边界处理（防止数值溢出）

核心要求：计算，若结果超过 则输出 “-1”，需用合理方式避免溢出。

例题 2（2021 CSP-J T1）：分糖果

考点：数学基础（整除、余数计算）、基本逻辑（条件判断）。

核心要求：计算 n 个小朋友分 m 颗糖果，每人最多分 k 颗时，最少剩几颗，直接用数学公式推导或简单循环实现均可。

---

第二题：模拟、贪心、排序、枚举、二分、高精度

例题 1（2024 CSP-J T2）：地图探险

考点：模拟（场景遍历）、基本语法（字符数组 / 字符串处理、多层循环）。

核心要求：模拟在地图上按规则移动，统计可到达的 “宝藏” 数量，需精准还原题目中的移动与判定逻辑。

例题 2（2023 CSP-J T2）：公路

考点：贪心（局部最优构造全局最优）、排序（预处理数据）。

核心要求：通过排序 + 贪心选择，计算修复公路的最少成本，关键是确定 “优先修复短路段” 的贪心策略。

例题 3（2022 CSP-J T2）：解密

考点：二分查找（有序区间找目标值）、数学运算（乘法与范围判定）。

核心要求：根据给定公式，通过二分法快速找到满足条件的整数，避免暴力枚举超时。

例题 4（2020 CSP-J T2）：直播获奖

考点：排序（动态维护有序序列）、枚举（统计排名）。

核心要求：实时统计直播中选手的排名，需高效维护分数序列并快速计算第 k 名的分数。

---

第三题：动归、搜索、数论

例题 1（2022 CSP-J T3）：逻辑表达式

考点：搜索（深度优先搜索）、表达式求值（递归处理优先级）。

核心要求：用 DFS 遍历逻辑表达式的语法树，计算结果并统计 “短路” 次数，需理解表达式的递归结构。

例题 2（2021 CSP-J T3）：网络连接

考点：模拟（字符串解析）、数论（IP 地址合法性判定）。

核心要求：解析输入的 IP 与端口，判断是否重复连接，需拆分字符串并验证 IP 各段的数值范围。

例题 3（2020 CSP-J T3）：表达式

考点：动态规划（区间 DP）、表达式求值（区间合并）。

核心要求：用区间 DP 计算表达式在不同括号添加方式下的最大值与最小值，需定义状态表示区间的极值。

---

第四题：动归、图论、树

例题 1（2024 CSP-J T4）：接龙

考点：动态规划（线性 DP）、字符串处理（前缀后缀匹配）。

核心要求：通过 DP 统计最长 “接龙” 序列长度，状态需记录当前序列结尾的字符串特征，关键是预处理字符串的匹配关系。

例题 2（2023 CSP-J T4）：二叉树

考点：树（二叉树遍历、树形 DP）。

核心要求：根据二叉树的前序与中序遍历，构建树结构并计算 “最长路径和”，需结合树形 DP 遍历树的每个节点。

例题 3（2022 CSP-J T4）：上升点列

考点：动态规划（二维 DP）、排序（预处理点的顺序）。

核心要求：通过排序 + 二维 DP 计算最多可选择的 “上升点” 数量，状态需记录点的坐标与已选数量，需优化状态减少重复计算。

例题 4（2021 CSP-J T4）：小熊的果篮

考点：模拟（队列 / 链表处理）、树（间接体现树形结构的遍历逻辑）。

核心要求：模拟每次移除 “成熟水果” 的过程，需用队列维护待处理的水果，间接考察类似树的层次遍历思想。