CSP-J/S2024第二轮提高级题目知识构成分析报告
本报告基于《全国青少年信息学奥林匹克系列竞赛大纲（2023 年修订版）》，对CSP-S2024四道题目展开分析，涵盖知识点、难度系数及选手能力要求，最后对题目知识构成进行总体评价。
执笔人：张炜其、汪星明、杨耀良、任舍予、赵启阳、韩文弢
2024年度CCF非专业级软件能力认证(CSP-J/S)第二轮提高级于2024年10月26日顺利举行。本次活动一等全国认证基准线为165分，二等全国认证基准线为105分，三等全国认证基准线为60分。本报告将从《全国青少年信息学奥林匹克系列竞赛大纲（2023年修订版）》(NOI大纲)1出发，对CSP-S2024的全部四道题目进行分析。对每道题目，报告将详细分析题目考察的主要知识点及其难度系数设置，以及题目设计对选手的能力要求等，最后对题目的知识构成做出总体性评价。
CSP-S2024的全部4道题目如下:
- 决斗（duel）
- 超速检测（detect）
- 染色（color）
- 擂台游戏（arena）
全部题目所涉及的主要知识点统计如下：
主要知识点的学习难度系数分布统计如下：
图1 知识点难度系数统计直方图
主要知识点的板块分布统计如下：
图2 知识点板块统计图
总体上看，CSP-S2024所考察的主要知识点分布较广，难度集中在1到5级，与大纲的建议考察范围一致。其中，在“难度”上以3级到5级知识点最多，1、2级次之，6、8级最少；在“板块”上以“算法”为主，各个板块均有涉及，可以看出本次比赛综合考察了学生多个方面的能力，其中着重考察学生的思维能力。
1 决斗（duel）
本题的难度较为简单，预期大部分选手可以拿到75-100分。
本题解法较多，主要考察选手的思维。所考察的知识点主要包括基础算法中的贪心法，二分法，STL模版中的排序sort，搜索算法中的深度优先搜索等。“贪心法”属于“入门级”的“基础算法”，大纲标注学习难度系数为3；“sort“属于”入门级”的“STL，大纲标注学习难度系数为3；“深度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为5。所涉及知识点难度均不超过大纲规定提高级考试所要求的难度。
1.1难度设置
本题的部分分所考察的知识点具体包括：
1.2总体评价
本题所考察的知识点的最高难度系数为6级，与大纲关于竞赛题目的命题建议相符。所涉及的知识点均不超过提高级知识点，部分分考擦难度具有一定梯度，可用不同程度的搜索算法取得。满分做法需要学生具有一定的思维能力，但相对容易想到。作为提高组的第一题较为合适。
2 超速检测（detect）
本题的难度相对简单，预期绝大部分选手至少可以拿到20-60分，部分同学可以获得60-100分。
本题考察的能力较为综合，主要考察选手的对于题面的理解能力和思维能力，编码能力。所考察的知识点主要包括代数能力，基础算法中的贪心法，二分法，STL模版中的排序sort，搜索算法中的深度优先搜索等。“代数”属于“提高级”的“初等数学”，大纲表述学习难度系数为5；“贪心法”属于“入门级”的“基础算法”，大纲标注学习难度系数为3；“二分法”属于“入门级”的“基础算法”，大纲标注学习难度系数为4；“sort“属于”入门级”的“STL，大纲标注学习难度系数为3；“深度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为5。所涉及知识点难度均不超过大纲规定提高级考试所要求的难度。
2.1难度设置
本题的部分分所考察的知识点具体包括：
2.2总体评价
本题所考察的知识点的最高难度系数为5级，与大纲关于竞赛题目的命题建议相符。所涉及的知识点均不超过提高级知识点，题目对于选手的数学和理解题目的能力有所要求。部分分的考察难度具有一定梯度，其中20分可用搜索算法取得。20-80分可以用不同程度的贪心方法获得，其中特殊性质AB的做法较为容易想到。满分的贪心方法需要学生具有一定的思维能力，虽然证明相对复杂，但是属于经典的贪心模型。有经验的选手应该很容易想到。作为提高组的第二题较为合适。
3 染色（color）
本题的难度适中，预期大部分选手至少可以拿到20-50分，部分同学可以获得50-100分。
本题考察的能力较为综合，主要考察选手的思维和建模能力。所考察的知识点主要包括动态规划的基本思路，动态规划的常见优化，搜索算法中的深度优先搜索等。“动态规划的基本思路”属于“入门级”的“算法”，大纲表述学习难度系数为4；“动态规划的常见优化”属于“提高级”的“算法”，大纲标注学习难度系数为8；“深度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为5。所涉及知识点难度均不超过大纲规定提高级考试所要求的难度。
3.1难度设置
本题的部分分所考察的知识点具体包括：
3.2总体评价
本题所考察的知识点的最高难度系数为8级，虽然标注难度较高，但实际可行的优化方法属于动态规划优化中非常简单的类型。与大纲关于竞赛题目的命题建议相符。所涉及的知识点均不超过提高级知识点，题目对于选手的建模能力有所要求，部分分的考察难度具有一定梯度，其中20分可用搜索算法取得。20-80分可以用不同复杂度的动态规划方法获得，并且部分数据点的设计可以有效引导选手思考和优化动态规划的方法。满分的动态规划方法选手想到后实现难度并不大。
4 擂台游戏（arena）
本题的难度较高，预期大部分选手至少可以拿到0-12分，部分同学可以获得12-40分。少部分选手可以取得40~100分。
本题考察的能力较为综合，主要考察选手对题目的理解能力、建模能力和编码能力。所涉及的知识点主要包括完全二叉树，递推，线段树，贪心法，搜索算法中的深度优先搜索等。“完全二叉树”属于“入门级”的“数据结构”，大纲表述学习难度系数为4；“递推“属于“入门级”的“基础算法”， 大纲标注学习难度系数为3；“贪心法”属于“入门级”的“基础算法”，大纲标注学习难度系数为3；“深度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为5。所涉及知识点难度均不超过大纲规定提高级考试所要求的难度。
4.1难度设置
本题的部分分所考察的知识点具体包括：
4.2总体评价
本题所考察的知识点的最高难度系数为5级，并不算高，涉及的知识点和难度与大纲关于竞赛题目的命题建议相符，知识点均不超过提高级知识点。题目主要考察学生对于题目的理解与模型的构建，具有较大的思维难度，且实现过程中有许多细节需要处理，整体较难。考虑到作为比赛的最后一题，由于时间的限制，选手们的得分情况可能会较低。
题目对于选手的建模能力和编码能力有所要求，部分分的考察难度具有一定梯度，其中12分可用搜索算法取得。12~40分需要选手发现一定的贪心性质，40~100分需要选手使用不同程度的优化的方法来获得，本质上属于在完全二叉树上的递推统计贡献，考虑到实现的细节较多，考试时间有限，能够实现满分做法的选手应该属于少数。
注：
https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf
CCF
严正声明
NOI为CCF品牌项目，其对外宣传平台仅有三个，分别是：
1.中国计算机学会(CCF)官网
(https://www.ccf.org.cn/)
2.全国青少年信息学奥林匹克(NOI)官网
(http://www.noi.cn)
3.“中国计算机学会”微信公众号
(ccfvoice)
以上三个平台的NOI相关新闻如需转载，必须事先征得CCF NOI竞赛办公室书面同意，未经书面授权的任何形式的转载都是非法侵权行为，我学会将依法追究相关法律责任。对于机构或组织冒用我学会的商标标识混淆视听以达到欺骗选手及家长进行多次消费的行为，我学会一经发现必当严肃追究，此类行为将受到法律制裁。