NOIP2024题目知识组成分析报告

本报告基于《全国青少年信息学奥林匹克系列竞赛大纲（2023年修订版）》，对NOIP2024四道题目展开分析，涵盖知识点、难度系数及选手能力要求，最后对题目知识构成进行总体评价。

执笔人：李建、杨耀良、任舍予、赵启阳、韩文弢

2024年度全国青少年信息学奥林匹克联赛(NOIP)于2024年11月30日顺利举行。本次活动一等奖全国基准线为200分，二等奖全国基准线为90分，三等奖全国基准线为40分。本报告将从《全国青少年信息学奥林匹克系列竞赛大纲（2023年修订版）》(NOI大纲)¹。出发，对NOIP2024的全部四道题目进行分析。对每道题目，报告将详细分析题目考察的主要知识点及其难度系数设置，以及题目设计对选手的能力要求等，最后对题目的知识构成做出总体性评价。

NOIP2024的全部4道题目如下:

编辑字符串（edit）
遗失的复制（assign）
树的遍历（traverse）
树上查询（query）

全部题目所涉及的主要知识点统计如下：

表1 NOIP2024题目所涉及的主要知识点

主要知识点的学习难度系数分布统计如下：

图1 知识点难度系数统计直方图

主要知识点的板块分布统计如下：

图2 知识点板块统计图

总体上看，NOIP2024所考察的主要知识点分布较广，在“级别”上不超过提高级，与大纲的建议考察范围一致。其中，在“难度”上以6级知识点最多，在“板块”上则以“算法”知识点为主，综合考察学生多个方面的能力。

1 编辑字符串（T1）

本题有效考察了选手的基础思维能力，正解所考察的主要知识点包括：贪心法。“贪心法”属于“入门级”的“基础算法”，大纲标注学习难度系数为 3。所涉知识点难度不超过大纲规定提高级考试所要求的难度。

1.1 难度设置

本题的部分分所考察的知识点具体包括：

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图1 题目“编辑字符串”的难度设置曲线

1.2 总体评价

本题所考察的知识点的最高难度系数为3级，与大纲关于NOIP题目知识点难度的建议相一致。虽然本题考察知识点难度系数较低，但是获得满分需要选手设计正确的贪心策略，整体来看，本题作为 T1 难度适中。

2 遗失的赋值（T2）

本题总体难度适中，主要考察选手的基本数学与综合能力。正解所考察的主要知识点包括：代数（初中部分）、乘法原理、倍增法。其中，“代数（初中部分）”属于“入门级”的“初等数学”，大纲标注学习难度系数为1；“乘法原理”属于“入门级”的“离散与组合数学”，大纲标注学习难度系数为2 ；“倍增法”属于“入门级”的“基础算法”，大纲标注学习难度系数为4。所涉知识点难度均不超过大纲规定提高级考试所要求的难度。

2.1 难度设置

本题的部分分所考察的知识点具体包括：

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图2 题目“遗失的赋值”的难度设置曲线

2.2 总体评价

本题所考察的知识点的最高难度系数为4级，与大纲关于NOIP题目知识点难度的建议相一致。从知识点难度来看，本题考察的知识点难度系数较低，但是需要选手有一定的数学能力，同时对不同难度的推导设有不同的部分分，具有一定梯度，作为NOIP的第二题难度较合适。

3 树的遍历（T3）

本题是整套题目中的较难题，部分分设置充足，覆盖了很多不同复杂度的不同做法及特殊性质，有良好的区分度。

本题正解所考察的主要知识点包括：乘法原理、排列、树型动态规划、容斥原理。其中，“乘法原理”和“排列”属于“入门级”的“离散与组合数学”，大纲标注学习难度系数分别为为2和4；“树型动态规划”属于“提高级”的“动态规划”，大纲标注学习难度系数为6；“容斥原理”属于“提高级”的“离散与组合数学”，大纲标注学习难度系数为7。所涉知识点难度均不超过大纲规定提高级考试所要求的难度。

3.1 难度设置

本题的部分分所考察的知识点具体包括：

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图3 题目“树的遍历”的难度设置曲线

3.2 总体评价

本题考察了选手对于组合计数问题的各种技巧的综合运用能力，知识点的最高难度系数为7 级，与大纲关于NOIP题目知识点难度的建议相一致，也符合 T3 的应有难度。本题部分分难度设置合理。

4 树上查询（T4）

本题主要考察了选手对基础算法和数据结构的应用能力。本题设置了充足的部分分，覆盖了多种复杂度不同做法，有一定的区分度。

本题正解所考察的主要知识点包括：最近公共祖先、线段树或分治算法、扫描线。其中，“最近公共祖先”属于“提高级”的“图论算法”，大纲标注学习难度系数为6；“线段树”属于“提高级”的“特殊树”，大纲标注学习难度系数为6；“扫描线”属于“提高级”的“算法策略”，大纲标注学习难度系数为7。所涉知识点难度均不超过大纲规定提高级考试所要求的难度。

4.1 难度设置

本题的部分分所考察的知识点具体包括：

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图4 题目“树上查询”的难度设置曲线

4.2 总体评价

本题所考察的知识点的最高难度系数为7级，与大纲关于NOIP题目知识点难度的建议相一致。本题部分分设置较为合理，各水平选手均可以在此题拿到充足的部分分。

注：

¹https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf

CCF

严正声明

NOI为CCF品牌项目，其对外宣传平台仅有三个，分别是：

1.中国计算机学会(CCF)官网