NOI2024题目知识构成分析报告

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

本题是整套题目中较为简单的一道题，预期大多数NOI选手都能得到80分以上。最后 20 分涉及到集合哈希，对于高水平选手也具有一定的区分度。

本题的部分分设置充足，只要选手能够正确实现暴力枚举，就可以获得40分；如果选手能够观察到答案的单调性，用双指针维护，就可以得到60分左右。

本题正解所考察的知识点主要包括队列、集合哈希。其中，“集合哈希”属于“提高级”的“数据结构”，大纲标注学习难度系数为5。所涉知识点难度均不超过大纲规定NOI考试所要求的难度。

1.1 难度设置

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

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

图3 “集合”的难度设置曲线

1.2 总体评价

本题所考察的知识点的最高难度系数为5级，与大纲关于NOI题目知识点难度的建议相一致，也符合D1T1的应有难度。本题的“知识点难度系数—可得分数”曲线较为平缓，说明部分分设置合理。

本题是NOI比赛中的中等难度题目，本题要求选手需要具备一定的模型转化能力和问题洞察能力，能够想到把大规模的问题逐层递归，变为更小规模的子问题进行解决。

当一个元素在某条边上的询问结果表明它较小，则该元素可以被排除。选手可以利用一次询问，将当前未排除的元素两两分成一组，用一次询问同时比较，从而排除掉一半的元素。这是二分的思路。

另一种立即的思路是通过一次询问，将所有未排除的元素放入一个大组，在组内两两比较，直接确定出最大元素。若选手始终采用方法1，则可在20次询问下获得26分。若选手先应用几次方法1，再进行一次方法2询问，则可以在13次询问下获得52分。13次询问这一临界点可以通过计算贪心得到。

更高得分的关键在于发现一个介于上述两种思路之间的策略：选手可以将未排除的元素分成若干个组，每组包含大于两个元素，但不覆盖所有元素。每次递归中分成的组数成为待优化的参数，选手需要探索合适的分组方式，以最小的询问次数达到最佳效果。

本题的考查重点在于选定一条好的递归路径。由于不同递归方式所消耗的询问个数不同，在严苛的询问个数限制下，选手需要使用动态规划直接计算出最优的递归方案，或者凭借数学直觉拟定一种优秀的递归方案。

本题要求选手需要具备一定的模型转化能力和问题洞察能力，能够从问题本身出发设计出合理的状态。事实上，如果选手拥有较强的数学建模能力以及关于无向图独立集方面的知识，不仅可以设计出优秀的DP方案，而且可以根据DP结果证明题目给出的界是严格最优的。

本题正解所考察的知识点主要包括简单背包类型动态规划、用决策单调性对动态规划进行优化。其中决策单调性属于动态规划的常用优化，大纲标注学习难度系数为8，所涉知识点难度均不超过大纲规定NOI考试所要求的难度。

2.1 难度设置

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

² 可以使用图的独立集知识完成有关的严格证明，但这并非解题所必须掌握的知识。在NOI大纲中，“图的独立集”的级别为 NOI 级，编号为 2.3.3.3-5，难度系数为 10。

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

图4 “百万富翁”的难度设置曲线

2.2 总体评价

本题所考察的知识点在大纲中不超过8级，符合大纲对于NOI试题难度的预设。只要选手掌握枚举、二分、贪心等基本算法思想，直接使用这些思想即可得到一个15~52分的做法。如果选手能够想到递归的思路，并且设计出一条优秀的递归路径以后，通过手算或稍劣的DP即可得到78以上的分数。

本题难度较大，要求选手具备对多个知识点的综合掌握和灵活运用能力。本题标准算法的实现细节比较复杂，代码规模在 4KB 左右，因此对选手的代码实现能力要求较高。

本题需要选手首先对题目进行模型转化，推导出充要条件。在得到充要条件以后，使用队列进行维护，得到一个初步的算法。选手想要获得更高的分数，需要利用数据结构对转化后的算法进行维护。

本题正解所考察的知识点主要包括倍增法、并查集。其中，倍增法、并查集均属于提高级数据结构，大纲标注学习难度系数为6。

本题的正确做法很多。如果选手利用其他的数据结构知识，也很容易想出别的正确或复杂度稍劣的做法，例如启发式合并，线段树，树链剖分，在树边上随机设置报警器，或者使用k-d tree对非树边进行维护等等，都可以通过此题，或者获得至少72分的部分分。

综合来看，本题所涉知识点难度均不超过大纲规定NOI级比赛所要求的难度。

3.1 难度设置

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

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

图5 “树的定向”的难度设置曲线

3.2 总体评价

本题所考察的知识点在大纲中不超过9级，符合大纲对于NOI试题难度的预设。本题的部分分难度设置合理。

本题难度较低，主要考察选手对搜索优化的深入理解和灵活应用。本题部分分设置充足，对选手代码实现能力的要求较低，绝大多数选手都能得到80分以上的成绩，但获得满分极为困难。

本题正解考查的知识点主要包括广度优先搜索和搜索的剪枝优化。其中“广度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为5;“搜索的剪枝优化”属于“提高级”的“搜索算法”，大纲标注学习难度系数为 6。所涉知识点难度均不超过大纲规定NOI考试要求的难度。

4.1 难度设置

本题的部分分考查的知识点如下表所示。

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

图6 “分数”的难度设置曲线

4.2 总体评价

本题考查的知识点的最高难度系数为6，与大纲建议的 NOI题目知识点难度相一致。本题考查的最难知识点为搜索的剪枝优化，在大多数选手的掌握范围内，但选手必须对特定问题进行深入分析，才能设计出优秀的剪枝策略和较好的算法。采取不同剪枝策略和不同时间复杂度的搜索算法，可以分别取得 70、85、90、95、100等分数，阶梯设置基本平滑，说明本题的部分分设置比较合理。

本题是属于中等难度，且解法多样。本题主要考察选手对动态规划以及使用数据结构对动态规划进行优化的深入理解和灵活运用能力。本题的部分分设置充足，即使选手并未充分掌握使用数据结构对动态规划进行优化，结合题目所给特殊性质，也应能得到65分左右。

本题正解所考察的知识点主要包括树型动态规划、动态规划的常用优化、线段树。其中“树型动态规划”属于“提高级”的“动态规划”，大纲标注学习难度系数为6；“动态规划的常用优化”属于“提高级”的“动态规划”，大纲标注学习难度系数为8；“线段树”属于“提高级”的“特殊树”，大纲标注学习难度系数为6。除线段树外，本题还有许多使用“树状数组”和“树链剖分”、“映射（map）、多重映射（multimap）”和“离线处理思想”等对树型动态规划进行优化的优秀做法，其中“树状数组”属于“提高级”的“特殊树”，大纲标注学习难度系数为6；“树链剖分”属于“NOI级”的“复杂树”，大纲标注学习难度系数为8；“映射（map）、多重映射（multimap）”属于“提高级”的“STL模板”，大纲标注学习难度系数为5；“离线处理思想”属于“NOI级”的“算法策略”，大纲标注学习难度系数为8。所涉及的知识点难度均不超过大纲规定的NOI考试所要求的难度。

5.1 难度设置

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

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

图7 “登山”的难度设置曲线

5.2 总体评价

本题正解的知识点最高难度系数为8级，与大纲关于NOI题目知识点难度的建议相一致，符合D2T2的应有难度。

本题在部分分设置上有一定坡度，难度设置总体上比较合理，基本符合大纲对于NOI试题难度的预设。本题考察的主要知识点为“树型动态规划”和“动态规划的常用优化”，在此基础上，选手可灵活选用“线段树”、“树状数组”、“映射（map）、多重映射（multimap）”、“离线处理思想”等方式方法完成题目，减少了失分的偶然性。

本题难度较高，绝大部分选手只能获得较低的部分分。本题要求选手掌握若干图论基础知识，并具有较高的综合运用能力，观察并证明性质的能力。同时本题代码规模较大，对选手代码实现能力有较高要求。

本题正解考查的知识点主要包括图论中的深度优先搜索和强连通分量。其中“深度优先搜索”属于“入门级”的“搜索算法”，大纲标注学习难度系数为 5；“强连通分量”属于“提高级”的“图论算法”，大纲标注学习难度系数为7。本题需要观察出图中路径的性质，同时通过对DFS树和强连通分量的复杂操作解决问题。综合来看，所涉知识点难度均不超过大纲规定NOI考试要求的难度。

6.1 难度设置

本题的部分分考查的知识点如下表所示。

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

图8 “树形图”的难度设置曲线

6.2 总体评价

本题考查的知识点的最高难度系数为7，与大纲建议的NOI题目知识点难度相一致。本题考查的最难知识点为强连通分量，也考察了深度优先搜索的拓展运用—DFS树，在大多数选手的掌握范围内。但题目是对选手实力的综合考验，必须对问题进行深入分析，通过部分分逐步发现若干图上的性质，已经要求选手兼具日常积累和洞察力。同时选手需要设计出综合的图论算法，并具备编写复杂算法的代码能力。本题的部分分设置比较合理，能体现选手在此题达到的思维深度。综上所述，本题作为D2T3质量较高。

报告执笔人：

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

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

(https://www.ccf.org.cn/)

2.全国青少年信息学奥林匹克(NOI)官网

(http://www.noi.cn)

3.“中国计算机学会”微信公众号

(ccfvoice)

以上三个平台的NOI相关新闻如需转载，必须事先征得CCF NOI竞赛办公室书面同意，未经书面授权的任何形式的转载都是非法侵权行为，我学会将依法追究相关法律责任。对于机构或组织冒用我学会的商标标识混淆视听以达到欺骗选手及家长进行多次消费的行为，我学会一经发现必当严肃追究，此类行为将受到法律制裁。