NOIP复赛复习(十)怎样才能拿到高分?

本文作者吴翼毕业于常州中学,NOI 2009金牌、IOI2010银牌、被保送到清华大学“姚班”,曾获三次ACM/ICPC亚洲区域赛金牌,一次全球总决赛铜牌。

NOIP复赛复习(十)怎样才能拿到高分?-少儿编程网

(图为IOI2010中国国家队队员,右二为吴翼)

摘要

考场策略和程序测试是信息学竞赛中非常重要的环节,很多优秀的选手在很多比赛中总是会在这两个环节上犯下这样和那样的错误,导致得到的分数和实力不成正比,最后留下了无尽的遗憾。本文将探讨一些这两个环节上值得注意的地方,提出一些可行的方法,分享一些经验,以此希望帮助选手们在比赛中发挥水平,减少失误,告别遗憾。

前言

信息学竞赛本身是一个美好的东西,她包含着奋斗、努力、追求、成长、汗水和收获。一个选手从与其接触,到了解,再到热爱,无数的时间与之为伴;同样,信息学也给予了我们太多:给予了友情,老师的关怀,太多的希冀、责任和无数难以忘怀经历。

可是,太多的时候,信息学竞赛总是透着那么多的忧伤,似乎她带来的美轮美奂的精彩总被那些无可奈何的泪水和发自内心的懊悔所掩盖。

遗憾——如此悲情的字眼的不停出现,似乎把本该光鲜的信息学竞赛抹上了灰色。
遗憾,那么伤痛,寻根溯源,笔者希望以此文,让大家发挥水平,让这个词语永远的离大家而去。

一、简介

1、什么是考场策略?

一场信息学竞赛,比赛时间从 3 个小时到5 个小时不等,题目从 3 题到 4 题不等。在这样的一个长时间的过程里,如何分配时间,如何对待手上的题目,用什么方式和顺序对待手上的题目等等一系列的决策问题,我们称之为考场策略。

2、什么是程序测试?

程序测试就是在写完程序后,利用各种方式检验程序正确性的过程。

3、二者有什么关系?

概要的说,考场策略包含了程序测试这一个环节,因而本文中,对于考场策略我们讨论的是一个总揽全局的安排,而程序测试讨论的则是具体的实施方法。

可以说,考场策略的制定在程序测试之前,而程序测试又能影响到考场策略的实施。

二、考场策略

一个完整的测试包括审题,思考,做题,检验这几个环节,我们将分开讨论这几个步骤。

1、审题

【建议1】一场测试应该花至少 30 分钟来审题,并做相关笔录。

1.1重要性
很多同学觉得这花去的时间太多了,大大占用了之后的解题时间。但是无数的事实告诉了我们审题的重要性,无数的遗憾正是由审题开始的。

【实例1】 NOI2008 Day1 party 具体题目略。
事实:
此题是NOI2008 day1的第一道题,也是最容易拿分的题目,此题有50%的小数据,因此使用暴力枚举算法能够至少拿到 50 分。而悲剧也正从这一刻开始了。

注意题目中这样一句话:“输出文件party.out包含两个数,第一个数为最大可能的面具类数,第二个数为最小可能的面具类数。”也就是说,假设输出的两个数为A和B,那么应该满足A>=B。

题目描述清晰。可是,现场江苏省队11人中,仅毛杰明,卞晶、杨晶和汪一宁四人看对这一条件,其他7人均将小的那一个先输出,再将大的那一个输出。因此7人最高分仅30分。其中金斌损失近 70分。

【原因分析】

客观原因:
1、样例中输出的两个数是一样的,并没有体现需要题目描述;
2、以往所有的题目都是先输出小的再输出大的,而这一次比较特殊。

主观原因:
据事后交流,所有人都没有花足够的时间在审题这一环节上,而是花了更多的时间在算法思考和程序设计上。对题目的理解过份依靠直觉和以往经验。


【实例2】APIO2009 convention 具体题目略。
事实:
注意题目中有这样对方案的描述:“首先,将租借给客户数量最多的策略最为候选,将所有的公司按照他们发出请求的顺序编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后选出其中字典序最小的候选策略作为最终的策略。”

这段描述一共有三句话,本届江苏省队11人中有6人(包括笔者)都看清楚了第一句话和最后一句话,但都没有注意到第二句话,因而此题均为0分。

而此题有50%的小数据,即用替代算法也可得到50%的分数。此外,事实证明利用错误的贪心算法也可以得到50分左右的分数。以笔者为例,笔者如果此题加上50分则将得到国际金牌,其遗憾不言而喻。

【原因分析】

客观原因:
1、这道题目描述比较冗长,这一句条件并不是很显眼,并且去掉这个条件仍然是一道复杂度相同的问题;
2、样例和题目举的例子中均未体现这一个条件。

经过交流,所有看错此题选手,均是由于题目描述的冗长,为了节省时间,未能仔细斟酌文字描述,而是直接通过题目的例子来理解题目,因而主观的忽略了这一个条件。

分析一下上述两个例子,可以发现一些共性。

大家的目的都是为了快速的理解题目,都是过多的相信了经验和习惯,都是只关注题目所给样例。可见,发生这种悲剧的原因都属无视了审题这一环节的重要性!

到这里显然笔者已经不用再重申审题环节的重要性了。

不要因为某一次成功的因为经验或者小聪明节省了几分钟的写程序的时间而沾沾自喜,这样的做法如果成为了习惯,那么遗憾将是必然的。

1.2标记法

为了解决这一问题,笔者总结了一些方法,称其为标记法,基本的方式都是用笔在纸制题目上进行标记。

关键字:对于题目中的一些关键字,将其圈出

所谓关键字就是比较级,最高级等形容词,和一些关键的名字。

序号:对于一些定义冗长的描述,每一步的限制都标上序号,从而明确对题目的理解

建议是做到每一个标点后都要做一定的标记,这样避免漏掉一些描述。当然也可以不用每个标点后都写数字,如果两个短句都在说同一个事情,那么可以用一个点,或者一个三角来表示后一个短句的步骤和上一个短句相同。

回顾:不断回顾重点细节

对于一个一下子难以看懂的描述,建议先做一个标记,比如问号,看完后再对这些打问号的地方重新审视,可以写一些对这些地方的理解。

形象和抽象:将形象的问题抽象,对抽象的问题形象

对于一个形象的问题,我们往往需要对其进行抽象,进行数学建模;而对于一个过于抽象的问题(比如CTSC2009 day1 sequence),我们则需要进行形象的思维。

建议将这些经过分析的东西写在题目描述的旁边或者后面。

比如对于上面提到的实例2中的那句被大家忽略的描述,就可以如此标记:(1)首先,将租借给客户(a)数量最多的策略最为候选,将所有的公司按照他们(b)发出请求的顺序编号。(2)对于候选策略,将策略中的每家公司的(c)编号按(d)升序排列。(3)最后选出其中字典序最小的候选策略作为最终的策略。{这里要排两次序,问题的关键是如何处理第二次排序的最优性问题!}

不难发现,如果严格按照上述方法进行标记,是不会漏掉这一个条件的,或许这会浪费一些时间,但是挽回的损失是巨大的。

1.3把握尺度

那是不是把试卷写的越满就越好呢?笔者观点是否定的。

要标记,但是也不是要让所有记号将白色的考卷染成黑色;同样的,考卷也不是草稿纸,笔者认为,过分的标记只会让纸面变得混乱不堪,反而影响阅读,同样也过于形式。

标记法的目的是为了加深对题目的印象,做到一次审题效率最大化,是审题的辅助,并不是一个形式化的东西。

使得自己恰好完全理解,使得自己不会遗漏条件,不会主观臆断。这是使用标记法的原因,也是自己把握的尺度。适当即可,一切是为了向遗憾说再见。

2、思考

【建议2】审题之后,对每一道题目都应该进行较为深入的思考。建议进行20~30分钟左右的思考,同时不可浅尝辄止,读过便罢。

2.1重要性

这里的“思考”并不是指如何分析一道题目或建立数学模型之类,这不是本文讨论范围。

而除此之外,“思考”还能有什么门道呢?答案是肯定的。

【实例3】CTSC2009 day2

CTSC2009day2 有传统题world和garden,以及提交答案题puzzle。

puzzle是经典的N2数码问题。world和garden笔者第一眼都没有想到很直接的做法,而puzzle则应该是手动做一些模拟之后利用A*搜索解答。

于是笔者花了几乎所有的时间做了提交答案题,而几乎没有怎么做另外两道题,最后此题拿到45分——而这确实是一个比较不错的分数。

但是事实上除puzzle之外的两道题,现场都有很多的满分和高分,而puzzle的现场最高分不过是一个70分,绝大多数的人都是20~30左右。

笔者除puzzle外,仅得10分。

笔者用自己惨痛的经历说明了思考的重要性。

很多时候很多简单的题目往往套着复杂的外衣,而复杂的题目则往往有着简单的表象,还有的时候,有一些题需要一些分析才能得到问题的本质,如果贸然跳过,则永远会觉得此题让人一头雾水,进而影响到了考场上策略的安排。

可以说对每道题目都进行一定程度的思考,是考场策略正确实施的重要环节,也是重要保证。

摸清楚题目的脉路,是一切的基础。

对于实例3中的情况,笔者犯的最大的错误就是根据以往的经验,主观的认为CTSC的传统题都是基本不可做的,加之world一题有着非常抽象冗长的描述,再由于N2数码问题过于经典,所以笔者武断的认为这次传统题都不可做,最后犯了严重的策略错误。

显然,如果能够每道题都仔细思考一番,就能发现world一题搜索的本质,也就不会发生如此的遗憾。

2.2冷静的判断

上文说道,思考需要仔细。而何为仔细?是否想到算法就可以了呢?也不是,想到了一个算法并不能直接予以肯定,而是要先否定他,想想有什么漏洞,或者想想是否有更好的方法,莽撞的立刻动手写题往往会浪费更多的时间。

【实例4】NOI2007 day2

NOI2007day2有一道令人记忆深刻的数据结构题necklace,此题标准做法是线段树。而更容易想到的是,对于这种连续区间问题有着超强适应能力的splay。

考场上吴卓杰在思考的过程中很快想到了利用splay解决这个问题,并迅速开始了编码。最终利用3个小时,终于写出了一个350行的正确代码。

但是由于时间的过多使用,导致另外两道题的时间不够用,而这道数据结构题,由于专注于splay,并没有再深入的思考而没有意识到可以使用更加简单和快速的线段树,导致最终此题也因超时的缘故仅仅比朴素算法多了10分。

day2的成绩最终导致吴卓杰和金牌差之毫厘。

试想,如果能在考场上对另外两题多思考一下,进行正确的评估和定位,并对已有的算法多进行审视,怀疑和分析,结果也许就会好的多了。

冷静和深入是思考的要求。

3、做题

这里的做题也并不是说如何写程序,如何实现模型,这些不是本文讨论内容。这里的做题主要讨论的是用什么顺序做题,用什么的心理期望来做题,如何分配时间来做题。

3.1先易后难

现在的题目普遍有比较多的部分分可以拿,而很多的时候即使想出完美算法,实现这些完美算法未必在考试时间内能够完成,那是应该节约时间拿到一些部分分,还是花时间思考和实现完美算法呢?对于难度相当的两道题,是应该先做哪一道呢?这是一个值得琢磨的问题。

【实例5】CTSC2009 day1

CTSC2009day1一共三道题目,分别是传统题trique,sequence,和提交答案题locate。 trique是类似汉诺塔类的最优值问题,sequence是复杂的动态规划(贪心)。trique有20%的分数非常简单,sequence有30%的小数据,locate有一个数据是求带权中位数。

金斌在考试中选择了先做trique,并用很短的时间写了一个暴力程序对自己的程序进行检测,但是发现小问题不断,于是便进行不断的改进,最终思考3个多小时也未能得出正确结论。慌乱之中,随手写了剩下两题的小数据。最终只有trique得到50分,其余两道均0分。

相对于金斌,毛杰明在考试中一开始便写了trique的20%的送分数据,以及sequence的 30%的小数据,并花了较多的时间利用调整做提交答案题locate。最终得分是30+60+30,毛杰明没有一道题的得分进入前十,但是总排名却在前十之列。

CTSC2009是一次非常经典比赛,可以说这次比赛对选手策略的运用提出了很高的要求。从上面不难看出,对于一次考试的题目,绝对不能一开始盯着一道题花大量的时间。对于花很多时间先做难题,如果做不出(如实例5中金斌),则必然对心情是一种极大的打击,非常容易影响考试状态,而即使做出了(实例4中NOI2007day2吴卓杰的表现),也会因为时间上的紧张影响到其他题目的解答。

【建议3】合理安排顺序,遵循4个字:先易后难。这句话说的轻巧,如果分辨题目是难还是易呢?所以说先一步进行一定深度的思考是合理制定考场策略的前提。在进行一定思考之后,应该对不同的题目不同规模和性质的数据进行解题时间的评估。

【建议4】经过合理的预估,对于明确估计能够在半个小时之内编写完毕并且调试成功的题目(或者题目对应的部分数据),应该立刻将其完成。

对于自己并不自信能在半个小时之内写出对付一道题目的部分数据的正确程序,那么样的部分数据就不应该定义为简单了。

写完了简单的,再写有一些初步的算法需要继续思考,或者需要大量编程量的题目。

此时,有人便会提出疑议,会不会因写简单程序而占用了写出得分更多算法的程序能够用时间?

其实这是不会的,原因有二:

第一点,是这里的简单是在充分的自信下定义的。在考试开始的时候,如果能够正确而快速的写出一个能够得分的程序,不但是对自信的提高,也是让自己更好的进入考试状态;

第二点,如果一道题目,最简单直接的拿基础分的程序都需要比较长的时间,那么此题必然是一个比较难的题。通过上面的讨论我们知道,这种比较难的题不宜在一开始做,而应放在后面做。如果开始时间紧张,写暴力程序也是避免出现意外,避免出现最后得较多分的程序未能成功写出而拿不到分的情况。

3.2杜绝模棱两可

很多人又要说,如果对于一种算法,并不能通过题目得知具体的得分情况,该如何处理?

这种情况显然是普遍的,很多人由于嫌恶暴力算法得分不高,不愿意触及,而更愿意相信一些通过灵感的来的算法(比如一些诡异贪心)。实际情况是怎么样的呢?

【实例6】NOI2006

“这次 NOI 我只有两题接近满分。一道是平衡树的题目(90分),一道是提交答案题(92分)。其他的题目我接近0分。有些题目会告诉你百分之多少的测试点的规模是多少,小的规模的程序也许会很容易编,但是只能拿一点分,比如40 分,抓住这点分!只要我能够抓住这 40 分,我就可以进国家集训队了,我就可以拿NOI 金牌了!可是,当时的我,想了一个可以“对付”所有数据的贪心算法(所谓“对付”,就是说可以不超空间和时间地出解),这样得分的几率是很小的,小到远远不到 40%,我就拿了0 分!这次NOI,我能拿这样的 40 分的机会,我错过了 2 个!”  ——摘自陈明骋NOI2006总结

NOI2006江苏没有一个人获得金牌,可以说江苏队取得的成绩与队员的能力完全不成正比,留下的也是无尽的遗憾。此处直接引用原句,从中不难发现深深的遗憾。即使有一个没有明确得分估计的算法,笔者仍然有如下建议。

【建议5】一定要写所有确定的,能够得到一定分数的基本算法。

一个所谓比较“诡异”的算法,如果能取得比较高的分数自然是好事,而如果不能,写一个能够得分的程序,则绝对是一个保险的做法。

4、检验

这是一个往往被忽视的环节,下面说两个真实而悲壮的例子。

【实例7】CTSC2009day2

仍然是CTSC2009 day2,只是这里要说的主角不是笔者。考试内容可以参看实例3。

首先说说曹钦翔,由于吸取了WC2009自己所犯的重大策略失误,曹钦翔在的做题思考的发挥上非常完美。在day1的比赛中,曹钦翔稳定发挥,并将总成绩提高到前十;而在day2中,曹钦翔很快看出world是一道搜索题,并在一个小时内解决world。此后同样在不长的时间里得出了garden 的正确算法,并完成了一个400行的代码,剩下的时间还有一个小时左右。此后曹钦翔将所有的时间放在了最麻烦的提交答案题puzzle上。

与曹钦翔相似,在day1的提交答案题locate上拿到94分高分,并因此总成绩一跃上升为第二的方展鹏,也很快想出了garden的做法,并将最后的所有时间花在了puzzle上。只是很可惜,最后的结果很悲剧。

曹钦翔的得分是100+14+0,方展鹏的得分是0+22+0,曹钦翔的garden写错了一个小的地方,方展鹏则是将文件名打错。最终曹钦翔位列第8,方展鹏位列第10,都遗憾的没有能够进入面试环节——如果那两个错误不发生,他们都将进入面试。

可以看到,在实例7中,曹钦翔和方展鹏虽然在审题、思考和做题环节都非常出色,但是都是由于忽视了检验这一环节,导致未能发现程序中微小的错误,导致最后巨大的遗憾。

【建议6】检查是必须,这是一个必须的步骤,不能主观的回避。

即使实力强如曹钦翔和方展鹏,也会犯如此低级的错误,在重大的比赛中要告别遗憾,必须重视检查这一环节。

每道题目都要检查,以笔者的角度推荐写完立刻检查,因为此时的印象最深刻,效果最好,同时检查完毕后就排出了这倒题目对后面比赛的影响,更容易让人在后面的时间里面集中精力。

同时在最后的半个小时左右的时间里,笔者建议不要再写程序,如例子中曹钦翔和方展鹏,抢这一点时间不过为了争得20分左右的分数,可谓丢了芝麻剪了西瓜。

笔者认为,在最后的时刻抢一些分数会导致非常的紧张,除非之前的检查工作非常细致和到位,推荐最后一定要把所有的题目仔细的静态阅读一遍,顺一遍思路。

试想如果方展鹏和曹钦翔能多检查,悲剧就不会发生了。

5、说明

本文的题目是《谈比赛发挥》,诚然,上述的内容并没有说明如何得高分,如何超水平发挥,如何战胜别人,但是,上文却讲述了一个最基础的东西,只有先保证不输,才能有底气的考虑如何战胜别人。

三、如何测试程序

1、概述

测试程序是非常重要但却经常被忽视的一个环节,很多时候想到了正确算法,但是往往因为小的错误而功亏一篑,扼腕叹息,为时晚矣。

上文中我们已经说到了测试的重要性,而如何高效的测试程序,有一些什么注意的要点?下面我们就要谈谈具体如何测试程序。笔者认为,程序的测试工作分为两个部分:静态查错和制作测试数据。

2、静态查错

这里先引用吴景岳的一段话: “在编程之后不要急着运行调试,而是把自己的程序仔细看看,有什么错误,这也被称作“静态查错”。因为很多错误在运行调试中是很难被发现的,比如常量定义、数组大小、变量名打错......。静态查错还能够发现算法实现过程当中的一些小问题。”

静态查错是测试程序的第一步,也是关键的一步。尤其对一些写了很长时间,代码量又非常大的题目,经过长时间的编码,人非常容易由于注意力的不集中而犯下很多低级的错误。静下心来重新想一遍算法,仔细分析一遍程序,是能够发现很多的问题的,认真的静态查错也能让之后的调试工作减少非常多的工作量。

【建议7】静态查错,最重要的是心静。

心静,即不可以因为刚刚写出一道难且复杂的题目而过份沉浸在成功的喜悦之中。静态查错,应该是把程序当成阅读来对待,认真的分析每一种情况,不能凭主观印象而粗枝大叶的扫几次,这样的查错是没有意义的。

很多OI选手非常依赖调试器,这样不但非常不科学,而且往往很低级的错误需要极长的繁复的过程才能找出。这样在考场非常容易造成急躁的情绪,最后使效率越来越低。

总之,静态查错是一种必备的,不可缺失的能力。

3、制作测试数据

从大体上说,测试数据分为三种,小数据、大数据和极限数据。

详见:NOIP复赛复习(九)如何设计测试数据>>>

除了写脚本,C语言的选手可以使用system()以及sprintf()函数在程序内直接写测试脚本,这样由于脚本和程序同步,更加方便。
#include<iostream>
using namespace std;
const char P[]="sample";
const char T[]="sample2";
chars[100];
int check() {
...//内容省略,根据情况编写即可
}
int main()
{
int test=0;
while(1) {
cout<<">TEST#"<<++test<<endl;
cout<<">Making..."<<endl;
system("./maker");
sprintf(s,"./%s",T);
system(s);
cout<<">Running..."<<endl;
sprintf(s,"./%s",P);
system(s);
cout<<">Judging..."<<endl;
if(check())cout<<" Passed!"<<endl; else {
cout<<"Wrong!"<<endl; while(1);
}
}
}

这段程序的基本框架也是不变的,也可以预先准备。

另外,写这种很自由的程序其实也是一种调剂,比如笔者在这种脚本程序时,总喜欢在自己的程序测试几百组数据正确后在屏幕上输出一个笑脸o(^-^)o 来对自己予以肯定。

测试策略

这里主要是想说明下面的这个问题。

从上面的描述中可以看出,随机数据并利用程序或者脚本对程序进行大规模测试的方法非常的便捷高效,那么是不是就可以忽略手工测试数据的生成呢?

答案肯定是否定的!

【建议 8】制作测试数据时,手动构造和程序构造在允许的情况下都是不可忽略的。

【实例 8】BOI2008 Mafia

BOI2008Mafia这道题是求一组网络最小割的方案,笔者由于疏忽误将所有与源相连的满载边均判断为割集,并输出为了方案。笔者进行了随机数据的测试,并通过了官方数据的所有5 个回馈点(feedback),笔者此时自信满满的提交,结果测试结果是 0 分(由于 BOI 数据采用捆绑测试,而所有回馈数据都是非独立的)。


【实例9】江苏差额选拔2008day3cactus

此题笔者写程序时,由于程序比较复杂,在某处循环少写了一层数组下标,但是静态查错笔者并没有能够发现问题。由于错误很小,笔者才考场上测试了 800 组比较小规模的随机数据都没有发现错误。而提交之后,测试结果是40 分,笔者赛后再次测试了 200组规模大一点的数据,就发生了错误。

从上述两个关于笔者的真实事例中,不难发现几个问题。

1、首先,随机数据非常不稳定,对于很多细小的错误,很多时候,当时运不济的时候并不能随机出很好的数据;

2、其次,可以发现数据规模越大,随机的效果越好,因此对于小数据,笔者强烈建议一定要仔细思考,考虑各种情况支护,手出几个数据,很多的时候,当随机很难构造好的数据的时候(尤其是图论问题,由于图的种类过多,随机的生成的图往往过于“朴素”),手动构造数据将变得更为重要;

3、最后笔者再次提醒,千万不要相信题目所给出的样例和回馈,有的时候,片面的样例和回馈甚至会产生不良的误导。

4、此外,利用制作的测试数据测试完毕后,笔者建议再回顾一遍程序,检查是否将所有注释,或者改变的数组范围和常数等等都标记正常,防止出现文件忘记打开之类的遗憾的错误。

四、实践

有了如上理论,我们来找一次比赛实践一下。我们假设参赛的选手以基本的动态规划,搜索,和例如强连通分支,最短路等基础的图论技巧以及比较熟练的程序实践基础。

应用 NOI2008

Day1:

首先审题,第一道是 party,利用标记的方法发现题目要求先输出大的再输出小的,并加以符号标明。然后是design,审题的时候发现题目有加粗的字体,马上关注,经过思考发现是一棵树。首先发现可以搜索,能够拿到 20 分,但是数据提示标准算法是O(NlogN)级别的。最后一题 employee,题目很清楚,发现有30%的数据规模很小。

开始思考,首先是 party。可以想到,题目与最大公约数和最小公倍数有关,但是没有明确的想法。思考用搜索来解决这个题目,发现似乎可以通过搜索的方法来确定面具种类。发现数据中说明 50%的数据可以用O(NM)的算法解决,于是想到可以暴力枚举答案。深入思考可以发现我们并不需要知道面具具体的种类,而只要知道相对关系即可,于是可以在O(M)的时间内进行答案可行性判断,总的复杂度恰好为O(NM)。

接着转到 design,根据树的性质发现是树形动态规划,但是似乎有难度,而且由于需要枚举孩子的选择情况,只想到 O(N4)复杂度的算法,可以拿 30~40 分左右。继续思考如何优化,但是发现此题思考时间已经半个小时了,立刻停止,迅速转到下一题。

经过深入思考,感觉 employee 可能和网络流有关系,但是自己不会,迅速放弃。此时时间过去一个半小时。

开始决策,觉得 employee 写暴力搜索会比较好写,于是花半个小时写employee 的搜索,经过 10 分钟的测试,发现通过。然后开始写 party 的50%的算法,写程序花了近 40 分钟,手动测试 20 分钟,发现正确。

时间还剩两个小时不到,仔细回顾一下 design 的决策方程,觉得时间不允许自己想出更好的算法了,思考20分钟,考虑周全后开始写程序,写了一个小时,并测试20 分钟后通过。时间还剩半个小时不到,检查各道题目,并最后将employee 加了一个剪枝条件。

测试得分 50+40+30=120 分,比较理想。


Day2:

第一题 trans 发现描述很麻烦,花了比较多的时间看,进行标记,着重看这句话:“从任何物流基站都可将物资运往控制基站”,经过分析,发现控制基站必然在环上。但是并没有发现什么好性质,但看到测试数据的条件列的很清晰,应该可以拿到几个特殊数据的分数。第二题 candy,是数据结构,暴力似乎可以拿30 分左右的分数。最后一题提交答案题 match,题目描述很清晰,但是求期望自己不大会,应该可以利用提供的评分程序match_check 用类似测试自己程序的写 C++脚本程序的方式来帮助自己的随机化程序计算。

开始思考,先看情况最多的 trans。发现目标函数可以用高斯消元法列方程求解,但是似乎复杂度过高,而自己思考一段时间后并没有得到好的方法。通过观察数据发现,test1 规模小可以直接枚举,test3直接解方程即可,由于之前审题发现控制基站在环上,因此test4 和 test5 也可以通过枚举和解方程来解决。总的来说,这道题代码量比较大,但是能拿 40 分的分数。然后是 candy,想了15 分钟没有什么好的想法,决定采用得 30 分的替代算法。最后是 match,想到是提交答案的题目,于是打开数据观察,发现test1 和 test2 可以暴力搜索,test6,8,9 似乎有规律,于是开始分析,但是发现快半个小时了,并没有得到什么好的结论。时间过去一个半小时,开始制定策略。

由于提交答案题的前两个数据的搜索程序最简单,很快写好并开始了搜索。然后考虑到随机化是提交答案题的通用方法而且也比较好写,于是很快写了一个非常暴力的随机比赛排列顺序的随机化程序。此时时间过去 2个多小时。

开始写第一题的高斯消元法,由于高斯消元法本身并不难写,程序的嵌套也只是复制而已。写程序用去 40 分钟左右,手动 10 分钟测试高斯消元函数,测试完毕后写随机程序继续测试高斯消元函数是否正确——检测的方法很简单,把解得的解代回原方程计算即可。

时间还剩不到 2 个小时。开始写candy 的暴力程序,发现比较复杂,但是还是能够调试成功,由于程序比较直接,静态查错并手动测试程序正确性。

时间还剩 1 个小时,最后回顾一下candy 和 trans 两道题目,然后开始查看提交答案题随机化程序生成的解答,最后逐一利用 match_check 检验完毕。考试结束前再次检查文件名数组大小等关键环节,最后提交。测试结果 40+30+60=130。

最终,加上笔试 100 分,总分350 分,获得金牌第 18 名,进入国家集训队。

不难看出,其实水平并不需要超强,只要不犯错误,不留遗憾,一个有一定算法基础和代码能力的选手也能够进入国家集训队——虽然排名不是很高。

总结

说了这么多,还是得说:文中所说的策略也好,方法也好,只能是告别遗憾,而不能迎接惊喜。

所谓遗憾,就是说对于一定的水平,没有能够发挥出来,没有得到这样水平应该得到的肯定,这样的情况才叫遗憾,而如果没有能够想到某种算法,或者别人超常发挥了,而我没有,别人想到了怪异的方法拿了高分,而我没有,其实这不能算遗憾,因为我发挥出了水平,而别人是超水平发挥。

比赛最重要的还是实力,要有一颗平常心,要正确的认识自己,超水平发挥要靠运气,机遇等等许多因素,可遇而不可求——我想休斯顿火箭的球迷肯定赞同我这样说法:你必须要求T-mac 每场比赛拿下两双,但是你绝对不能奢求T-mac 在火箭每次落后的时候都上演 35 秒 13 分的奇迹——事实也是这样:T-mac 只得2 分之后遭到了无数的批评,而当年姚明倒下,T-mac一个人与爵士众将缠斗,最终火箭失败后,T-mac并没有得到太多的责备—— 当然,不会有别人来怪罪我们,只有我们自己的内心会留下深深的遗憾。

考场上要做到正常发挥,不留遗憾,一定要做到专注。

吴沛凡在 NOI2008 就因为过份的考虑升学问题而留下无尽的遗憾,他后来说道:“什么心态会出现浮动?为什么细节会出错?这都是由于对自己的怀疑引起的。因为怀疑自己的实力,所以心不定;因为怀疑自己的能力,所以才对细节不自信。考场上我的想法其实是完全不必要的,而且由于出现在考场上更加影响了我的发挥。”

陈明骋在 NOI2006 后曾留下豪情的感叹:“人家爱考多少考多少,我在进行精彩的个人表演。”是啊,我们都在进行着精彩的个人表演,走到这里,无论成败,不都是要为自己而鼓掌的么?

很多的时候我们因为未来的为止而焦躁,而紧张,而烦忧,不能回避,只能直面。也许,那会产生很多的害怕和胆怯。笔者的一个老师曾对笔者说过:“未来永远是未知的,如果因为未来的未知而恐惧,那么就不断的问自己我到底恐惧什么,问到自己哑口无言的时候,自己就会得到释然。”

再次引用陈明骋的话:“竞争中的人,总会遇到“不能失败”的仗。这时候,责任心会催发你的斗志。我觉得,这比在心理上回避比赛后果的严重性要好。我经常在NOIP 之后的选拔中发挥大失水准,就是因为我一直想靠主观回避比赛后果的严重性来换取心态的轻松。其实,这是不可取的。难道直面世界很困难吗?”是的,难道真的那么困难么? 心态这个东西是如此的复杂,以至于笔者不能再多说些什么了。

笔者执笔此文,就想总结笔者自己和前辈的错误与经验来帮助更多的人,让更多的人引以为戒,在脑子空白的时候,不至于不知所措;让大家多琢磨琢磨这些经验的东西,感悟那些和这些话;让大家在将来的比赛中发挥出水平。希望此文,不再让以后的人们无所适从,不再让以后的人们抱憾,能让以后的人们每次比赛都能发挥水平,能够真正的告别遗憾。

本文链接:NOIP复赛复习(十)怎样才能拿到高分?

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:少儿编程网,谢谢!^^


*文章为作者独立观点,不代表少儿编程网立场
发表评论

坐等沙发
相关文章
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
NOIP少年丨黄子桉:不骄不躁不傲慢不强求
为什么越来越多家长选择信息学竞赛?
为什么越来越多家长选择信息学竞赛?
少儿编程为什么越来越火了?
少儿编程为什么越来越火了?
孩子学完各个阶段的编程课程能够参加哪些比赛?
孩子学完各个阶段的编程课程能够参加哪…
信息学竞赛必经之路–NOIP(内含2018报名方式说明)
信息学竞赛必经之路–NOIP(内含20…
我的孩子从来没有接触过编程,0基础能不能学?
我的孩子从来没有接触过编程,0基础能不…
NOIP2017 作者
NOI官网发布了2017年全国青少年信息学奥林匹克联赛(NOIP2017)的报名通知。NOIP2017将于2017年10月及11月分别举行初赛和复赛,有意向参加比赛的考生,即日起至10月10日可报名。