“信息学”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信息学说难也难,说容易也容易?》,到底咋写,我也还没想好,非常有挑战性!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181004B0AZXX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券