“信息学”NOIP竞赛到底有多难？—青少编程

之前写了一篇文章，《

到底，到底“信息学”NOIP竞赛获奖有多容易？—青少编程（18）

》，今天说说“信息学”NOIP竞赛有多难？

之前的文章，有位读者留言，这位读者去年也就是2017年，初二的时候获得了NOIP普及组一等奖，他的留言如下：

对于他的观点我非常认同，所以我写了这篇文章。

关于信息学的背景知识，本文不赘述了，在“有多容易”的文章中提到了一些，不了解的可去参考。

信息学的提高组（相当于高中组）是非常难的，仔细说会涉及很多计算机领域专业名词。这个以后再说。我先说说普及组（相当于初中组）有多难？如果证明了普及组很难，那么也不难推导出“提高组”一定更难了。

关于普及组有多难，先说一个数据。2017年，NOIP普及组全国参赛选手中获得一等奖共1761人，二等奖共2954人，三等奖共2083人，合计6798人。可以说这6798个获奖的小朋友就是国内在编程方面比较厉害的初中生和小学生了。因为，凡是编程还可以的，或是自认为编程还可以的，都会参加这个比赛。

那么，这6798个小朋友当中，满分一共有几个呢？

12个。

对，就12个。

满分是400分。什么概念？过了初赛，参加复赛，复赛是用计算机编程，一共4道编程题目，每道题目100分，4道编程题目全做对是400分。

你大概知道NOIP有多难了吧！全国6000多获奖选手，因为不知道获奖比例，假设获奖比例是4：1，就是全国2万多初中生、小学生牛娃或小牛娃参加一个编程比赛，能全做对的就12个人。

无论是帝都的人大附、实验，还是浙江的学军，还是合肥的168，还是成都的7中(你看，全国的名校我还知道几个！)……这些顶级中学里喜欢或是被强迫学习编程的佼佼者都会参加NOIP竞赛，全国就12个能全做对！

上面是从一个统计数据的角度来解释NOIP的普及组有多难，下面以普及组的初赛为例，从稍微专业的角度解释下NOIP的普及组有多难？如果对编程不太熟的，或者对“烧脑”比较抵触，后面的内容就不建议看了。

为啥只写初赛？因为一般的认知会认为初赛容易些，我解释完初赛有多难，读者就能猜测出复赛有多难！另外，以后有时间我也还能以“复赛有多难？”为题目，另写一篇文章。

信息学NOIP普及组的初赛是笔试，就是做两个小时的卷子。为啥有笔试，我猜是很难组织所有的报名者在同一时间上机编程，所以用笔试先刷一拨！

初赛笔试一共是四项大题，满分100分。我以2017年的题目举例说明。

第一项：单选题

20道，单选题涉及的内容包括：计算机的基础知识、排列和组合、概率、数据结构，还有信息学的基础知识等。

举几个典型的，供专业人士了解：

12. 表达式 a * (b + c) * d 的后缀形式是（ ）。

A. a b c d * + *

B. a b c + * d *

C. a * b c + * d

D. b + c * a * d

这道题是关于前缀、中缀、后缀表达式的，做这类题如果要比较有把握的话，最好把正波兰、逆波兰、横波兰、竖波兰都学一遍！

10. 设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。

A. m – n + 1

B. m - n

C. m + n + 1

D. n – m + 1

这道题涉及了图论的一些基础知识。要知道图啊，连通性啊，树啊，森林之类的。以前还考过二叉树，还考过二叉树的前序、中序、后序遍历！

16. 对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出栈序列。

A. a, b, c, d, e, f, g

B. a, d, c, b, e, g, f

C. a, d, b, c, g, f, e

D. g, f, e, d, c, b, a

这道题涉及到栈。对栈的基本概念比较清楚的话，就不算太难。

19. 一家四口人，至少两个人生日属于同一月份的概率是（ ）（假定每个人生日属于每个月份的概率相同且不同人之间相互独立）。

A. 1/12

B. 1/144

C. 41/96

D. 3/4

这道题涉及到概率。也不知道，初中生里，有多少自学概率和统计的！

A. 43

B. -85

C. -43

D. -84

这道题涉及二进制和补码。补码貌似容易，但原码、反码也要知道吧，为啥搞补码这个东东也要了解一下吧。

15. 十进制小数 13.375 对应的二进制数是（ ）。

A. 1101.011

B. 1011.011

C. 1101.101

D. 1010.01

这道题关于二进制，以及小数的表示方法。如果想做这类题有把握的话，除了定点，浮点的表示方法最好也了解一下。关于浮点小数的表示方法，我在一本教材上看到了一个比较详尽的描述，这个教材是CMU的计算机系本科教材。

这道题不看题面也能做对 ，因为选项A和C的整数部分一样，选项A和B的小数部分一样，所以我选A。人间处处皆学问！

除了这些纯技术类题目，还有些知识类题目，更让人心情灰暗！

比如：

7. NOI 的中文意思是（ ）。

A. 中国信息学联赛

B. 全国青少年信息学奥林匹克竞赛

C. 中国青少年信息学奥林匹克竞赛

D. 中国计算机协会

这基本上就要靠运气了！这涉及到英文翻译，National是翻作“全国“比较好，还是中国的全国就是中国，因此翻译成”中国“比较好。

我最喜欢的题目是下面这道。

20. 以下和计算机领域密切相关的奖项是（ ）。

A. 奥斯卡奖

B. 图灵奖

C. 诺贝尔奖

D. 普利策奖

像我这样社会上的知识比较庞杂的，计算机即使不会也能做对一道。你看，出题者多人性化。

第二项是问题求解，一般是推算两个数学问题。这里不展开了。

第三项阅读程序写结果

会给你四段程序，然后给你输入，问你程序运行后输出是什么？就是本来让计算机做的事情，让你在考场上模拟计算机做一遍。

具体的题目就不说了，第一道是关于字符串处理的，用到string 和字符数组、字符与对应整数的转换等概念（不知为啥，一提到字符串，我老想起烤串）。第二道是递归的，你要在草稿纸上，模拟递归的执行，深度大约是3层，每一层又有几个循环。第三道还可以，要人工模拟循环的执行。第四道非常难，那个程序在电脑上运行都需要5、6分钟，让你人工推算出最后的运行结果。

第四项是完善程序

就是给你两段程序，中间有几个空，告诉你这段程序的目的是什么，然后让你补齐程序。

第一个程序是快速幂，全称是快速幂取模。如下：

1.（快速幂）请完善下面的程序，该程序使用分治法求xpmod m 的值。（第一空 2 分，其余 3 分）

输入：三个不超过 10000 的正整数 x，p，m。

输出：xpmod m 的值。

快速幂有一个专门的算法，这类算法很多，基本上属于你如果学过，就有可能会，如果你以前没了解过，如果你在考场上能自己推导出来，那就是非常令人佩服了！

第二道题如下：

2.（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。（第一、二空 2.5 分，其余 3 分）

输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过10的6次方的正整数，表示每条绳子的长度，第三行是一个不超过10的8次方的正整数 m。

输出：绳段的最大长度，若无法切割，输出 Failed。

第二题用二分法来解。二分法是个看上去很容易，但是在使用中有各种变化形式的算法。在最近几次竞赛中反复出现，之前出现的形式还相对简单，最近出现的变化形式不太容易做出来。

好了，信息学普及组初赛的难度介绍完了，估计你一头雾水，Me two， Me three！

我们可以尝试从另外一个角度来理解普及组初赛的难度。比如说，国内排名前10之外的计算机系的本科生，如果在没有提前准备的情况下，让他们做这份试卷，我估摸着，如果一个系的学生都来做的话，那么如果平均分能达到50分，就说明这个学校的计算机系培养的学生还不错！这只是我一家之言啊，基本不准确！

好了，NOIP竞赛有多难，从普及组初赛的角度，我也介绍了。写过有多容易了，也写过有多难了，我准备下一篇写《为啥说，NOIP信息学说难也难，说容易也容易？》，到底咋写，我也还没想好，非常有挑战性！