虚树神骸虚无主义(虚树)

NOI 2023 题目知识构成分析报告

NOI 2023 共包括两试 6 道题目。其中，

l 第一试题目依次为：方格染色（color）、桂花树（tree）、深搜（dfs）；

l 第二试题目依次为：贸易（trade）、字符串（string）、合并书本（book）。

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

NOI 2023 题目所涉及的主要知识点

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

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

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

知识点板块统计直方图

总体上看，NOI 2023 所考察的主要知识点分布较广，在“级别”上以“提高级”知识点最多，在“难度”上以 6 级知识点最多，而在“板块”上则以“算法”知识点最多。主要知识点的学习难度系数，范围为从 2 到 10，与大纲的建议考察范围基本一致，而在“虚树”知识点上（大纲中学习难度系数为 10）略超出了建议范围。

以下为每道题的知识构成详细分析。

本题是整套题目中的简单题，预期绝大多数NOI选手都能得到 95 分或者 100 分。最后 5 分涉及到离散化和少量的细节处理。本题的部分分设置充足，即便选手未掌握扫描线和线段树，也应能得到 65 分左右。

本题正解所考察的知识点主要包括离散化、线段树。其中，“离散化”属于“提高级”的“算法策略”，大纲标注学习难度系数为6；“线段树”属于“提高级”的“特殊树”，大纲标注学习难度系数为6。所涉知识点难度均不超过大纲规定NOI考试所要求的难度。

此外，本题需要将“线段树”应用于扫描线，而“扫描线”知识暂未包含在现版本大纲内。建议在大纲修订时将“扫描线”知识点增加到“提高级”的“算法策略”部分，难度系数有待确定。

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

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

方格染色的难度设置曲线

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

本题是NOI比赛中的中等难度题目，其代码实现难度较低，但对动态规划状态设计的要求较高。本题要求选手需要具备一定的模型转化能力和问题洞察能力，能够从问题本身出发设计出合理的状态。

本题正解所考察的知识点主要包括状态压缩动态规划、复杂动态规划模型的构建。其中状态压缩动态规划属于提高级动态规划，大纲标注学习难度系数为7，复杂动态规划模型的构建属于NOI级动态规划，大纲标注学习难度系数为9，本题需要观察出复杂的树上结构，将状态压缩动态规划应用在此模型上，属于状态压缩动态规划的高级应用，综合本题难度为9，所涉知识点难度均不超过大纲规定NOI考试所要求的难度。

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

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

桂花树的难度设置曲线

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

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

本题正解所考察的知识点主要包括容斥原理、复杂动态规划模型的优化。其中，容斥原理属于提高级组合数学，大纲标注学习难度系数为7，复杂动态规划模型的优化属于NOI级，大纲标注学习难度系数为9。本题需要分析DFS树的性质，将容斥原理应用在树型动态规划上，并使用线段树作为数据结构来优化动态规划的模型。综合来看，本题所涉知识点难度均不超过大纲规定NOI级比赛所要求的难度。

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

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

“深搜”的难度设置曲线

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

本题难度较低，且解法多样。本题主要考察选手对树形动态规划或者最短路方法的深入理解和灵活运用能力。本题部分分设置较为充足，对选手代码实现能力的要求较低。

本题正解所考察的知识点主要包括最短路径（Dijkstra）、组合。其中“最短路”属于“提高级”的“图论算法”，词条为“单源最短路：Bellman-Ford、Dijkstra、SPFA 等算法”，大纲标注学习难度系数为6；“组合”（不直接求每项，而是分类到每个节点上）属于“入门级”的“离散与组合数学”，大纲标注学习难度系数为4。除了正解以外，本题部分分上较多选手采用了涉及“虚树”的其他解法，该知识点属于“NOI级”中的“复杂树”，大纲标注学习难度系数为10。

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

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

“贸易”的难度设置曲线

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

本题在部分分设置上有一定坡度，难度设置总体上比较合理，基本符合大纲对于NOI试题难度的预设。在一些部分分上，有相当数量的选手采用了知识点学习难度系数最高为10级的解法，这种解法虽然也较为自然，但对正解的启发性比较有限。

本题是属于中档难度，主要用于区分集训队与非集训队选手。本题要求选手掌握基本的字符串知识，并具备灵活使用数据结构进行计数问题优化的能力。

本题正解所考察的知识点主要包括后缀数组、Manacher 算法、二维数点（常见实现技巧为：扫描线、树状数组）。其中，“后缀数组”属于“NOI级”的“字符串算法”，大纲标注学习难度系数为 8；“Manacher 算法”属于“NOI级”的“字符串算法”，大纲标注学习难度系数为 8；“树状数组”属于“提高级”的“特殊树”，大纲标注学习难度系数为 6 。所涉及的知识点难度均不超过大纲规定的NOI考试所要求的难度。

此外，本题的“二维数点”需要通过“扫描线”来实现，“扫描线”暂未列入现版本的NOI大纲内。建议在大纲修订时将“扫描线”知识点增加到“提高级”的“算法策略”部分，难度系数有待确定。

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

其中“后缀数组”可以使用“二分法”与“字符串哈希函数构造”来替代，能够通过部分分测试点10-12，15-16，得到分值20； 再结合“Manacher 算法”可以通过部分分测试点 19-21，得到分值 32。

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

“字符串”的难度设置曲线

本题所考察的知识点最高难度系数为 8 级，与大纲关于 NOI 题目知识点难度的建议相同，大致符合 D2T2的难度定位。本题的“知识点难度系数—可得分数”曲线比较平缓，说明部分分设置较为合理，并且实际上每档部分分均存在对应的优秀做法。

本题存在一些具有创新性的做法，能够有效启发选手在字符串方面的能力，是一道很好的字符串题目。

本题的难度很大，预期绝大部分选手只能获得较低的部分分。本题要求选手能够根据搜索方式优化动态规划状态的设计，同时需要具备较强的代码实现能力。

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

此外，本题部分分也可以不进行搜索，使用状态压缩动态规划和简单一维动态规划两个知识点通过，这两个知识点大纲标注学习难度系数分别为 7,4，同样不超过大纲规定 NOI 考试所要求的难度。

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

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

“合并书本”的难度设置曲线

本题所考察的知识点的最高难度系数为6级（或部分分做法 7 级），与大纲关于NOI题目知识点难度的建议相一致。

本题虽然最高知识难度系数低于其他题目，但是其要求的思维难度很高，是一道知识考察非常灵活的题目。本题所考察的最难知识点——搜索的剪枝优化，在大多数选手的掌握范围内，但选手必须深入地理解搜索剪枝的本质，并对特定问题进行深入分析，才能设计出优秀的剪枝策略和较好的算法。采取不同剪枝策略和不同时间复杂度的搜索算法，可以分别取得 10、65、80、90、100 等分数，阶梯设置基本平滑，说明本题的部分分设置比较合理。

报告执笔人：

什么是虚数：它在我们日常生活中扮演着什么角色？

文艺复兴时期的数学家首先提出了虚数的概念。

在丹·布朗（Dan Brown）2003年的超级畅销悬疑惊悚小说《达芬奇密码》中，书中的主人公罗伯特·兰登（Robert Langdon）和密码学家索菲·奈芙（Sophie Neveu）之间有一点巧妙地应答，她在书中表达了对“信仰中包含奇迹般的事件”的宗教信徒的价值的怀疑。她冷笑道：“看来他们的真实是假的。”

兰登笑着说：“这些想法就像数学密码学家相信虚数‘i’能帮助他们破解密码一样。”

对于我们这些不懂数学的人来说，兰登的笑话有点令人费解。当他说一个数是虚数时，他到底在说什么？这怎么可能呢？

然而事实证明，虚数基本上是一个数，平方后会得到负数。确实是数学中的一种东西，最早是在15世纪和16世纪被发现的，用来解决某些令人困惑的方程。虽然最初被认为是一种室内把戏，但在此后的几个世纪里，它们被视为一种以复杂的方式将世界概念化的工具。如今，它们在从电子工程到量子力学等领域都很有用。

新墨西哥州独立研究机构圣达菲研究所的物理学家克里斯托弗·摩尔（Cristopher Moore）解释说：“我们发明虚数的原因和我们发明负数的原因是一样的。”他在2011年与斯蒂芬·默滕斯(Stephan Mertens)合著了《计算的本质》一书。

摩尔继续说：“从普通的算术开始，二减七等于几？如果你从没听说过负数，那就说不通了，就可能回答不上。你不能有-5个苹果，对吧？但是可以这样想，你可以欠我5个苹果，或者5美元。一旦人们开始做会计和簿记，我们就需要这个概念。”类似地，今天我们都很熟悉这样的想法：如果我们开大额支票去买东西，但没有足够的钱来支付，我们的银行账户就会出现负余额。

摩尔说：“另一种看待负数的方法，这稍后会派上用场，是想象在城市附近散步。如果你从我们的目的地向相反的方向拐错了弯。比方说，向南走了5个街区，而你本来应该向北走，你就可以把它想象成向北走了5个负的街区。”

摩尔表示：“通过发明负数，它可以扩展你的数学世界，使你能够谈论以前很难的事情。”

虚数和复数，也就是包含虚数成分的数字，是这种创造性思维的另一个例子。正如摩尔解释的那样：“如果我问你，9的平方根是多少？这很简单，对吧？答案是3。尽管它也可以是- 3，因为两个负数相乘得到的结果是正的。”

但是-1的平方根是多少？有没有一个数，乘上它自己，得到-1 ？摩尔说：“在某种程度上，没有这样的数字。”

但文艺复兴时期的数学家想出了一个聪明的方法来解决这个问题。摩尔继续说：“在我们发明负数之前，没有2-7这样的式子。所以也许我们应该发明一个等于-1的平方根的数字，我们给它起个名字：i。”

一旦他们想出了虚数的概念，数学家们就会发现他们可以用它做一些很酷的事情。记住一个正数乘以一个负数等于一个负数，但是两个负数相乘等于一个正数。但是当你开始用i乘以7，然后再乘以i会发生什么？因为i乘以i是-1，答案是-7。但如果你用7乘以i乘以i乘以i乘以i，突然得到正7。摩尔指出：“它们相互抵消了。”

现在想想，你取一个虚数，多次代入方程，最后得到一个你在现实中经常用到的实数。

美国宾夕法尼亚州立大学的教授和数学系主任马克·列维（Mark Levi）解释道：“直到几百年后的19世纪初，数学家们才发现了另一种理解虚数的方法，即把虚数看作平面上的点。”他是2012年出版的《为什么猫能站稳脚：以及76个其他物理悖论和谜题》一书的作者。

列维说：“当我们把数字想象成直线上的点，然后加上第二个维度时，那个平面上的点就是虚数。”

他解释道：“想象一条数轴，当你考虑一个负数时，直线上距离正数是180度。两个负数相乘，把它们的角相加，180度加上180度，就得到360度。这就是为什么它是有意义的存在。”

但是你不能把-1的平方根放在X轴上，这是行不通的。但是，如果你创建了一个垂直于X的Y轴，你就有地方放它了。

当你考虑虚数时，Y轴是有用的，因为你不能把根号-1放在X轴上。

虽然虚数似乎只是一群数字，使人眼花缭乱，但它们实际上是非常有用的，对于世界上某些重要的现代技术发达的计算而言，如计算飞机机翼的气流，从阻力或找出流失能量结合在一个电力系统振荡。小说虚构人物的罗伯特·兰登提到它们也用于密码学时，他可不是在逗我们。

在洛斯阿拉莫斯国家实验室从事量子计算算法研究的物理学家罗兰多·索马(Rolando Somma)解释说：“带虚分量的复数在理论物理中也很有用。”

索马说：“由于它们与三角函数的关系，它们在描述，例如，周期函数时很有用。这些是波动方程的解，所以我们用复数来描述各种波，比如电磁波。因此，和数学一样，物理中的复杂微积分是简化计算的极其有用的工具。”

复数在量子力学中也有作用，量子力学是一种在原子和亚原子粒子尺度上描述自然行为的理论。

索马表示：“在量子力学中，‘i’明确地出现在Schrödinger的方程中。因此，复数似乎在量子力学中扮演着更基本的角色，而不仅仅是一个有用的计算工具。”

他继续说：“量子系统的状态可以用它的波函数来描述。作为薛定谔方程的解，这个波函数是某些状态的叠加，叠加中出现的数字是复杂的。例如，量子物理中的干涉现象可以很容易地用复数来描述。”