深入Noip2010初赛试题和全解.doc

作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办”之类的声音。确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于Noip考核目的的审视和改变所导致的必然结果。因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。这种有意而为之的行为更值得我们去思考。二、试囗题分析（1） 选择题今年选择题没有跳出往年的考察框架，知识点基本都有涉及，下面我们来看一下考察了什么知识点： 计算机历史（1题）与往年基本持平，今年考察了“储存程序”这个可以说是考到烂的知识点，没有什么新意，往年考察也脱离不了图灵、冯诺依曼等人的知识成果。关于今年的题目（单项选择题第六题），很容易排除的是香农（信息论的提出者）和摩尔（著名的摩尔定律），至于查尔斯.巴比奇稍微少见一些，他是差分机和分析机（可以称之为现代计算机的前身）的创造者，也是一个很伟大的科学家。 计算机常识与相关热点（5题）计算机常识往年都有提及，但计算机热点新闻则是最近几年才兴起的题型。相对08年的Web2.0，09年的信息学官网网站，10年则彻彻底底是计算机的热点新闻了，不定项选择题第10题中的A与B选项甚至是9月份刚出现的新闻，这种惊人的热点程度或许反映了CCF更加重视综合素质的考察。今年的题目涉及这个知识点的有单项选择题的第二、四、八和不定项的第六、十题。其中计算机常识题比较难的题是Linux的可执行文件后缀名，实际上这题叙述上的陷阱让人极易选择A、B、C，但是Linux的可执行文件并没有后缀名，所以该题答囗案选D。单项选择题第八题则是硬件组成部分，高速Cache并不是个新鲜的概念，不再详述；不定项选择题的两题都有些难度，其中第六题考察了比较罕见的HTML语法，这个没有捷径可走，只能靠选手平时的知识水平；第十题除了刚才说的惠普研究员自称证明P不等于NP外，还有Microsoft收购McAfee（10年9月）和iPhone4发售（10年），容易搞错的是Windows7发售（09年10月），不少选手弄错了这个时间。这个知识点确实不容易拿分，许多选择题丢分的选手都是因为这一部分丢分。相对应的，这部分的题数正在逐年上涨，今年已占据了1/4的江山，这提醒选手一定要在计算机的综合素质上多下功夫，这些知识其实并不难掌握，只是有没有这个心去掌握罢了。 NOI系列比赛常识题（1题）这个类型的题目号称是妖题之中的妖题，自出现以来稳定保持一年一题的水平，并且考的让人有些摸不着头脑。相对08年考察竞赛环境和09年考察竞赛规则，今年考察了一个更为冷僻的知识点：NOI系列比赛的历史。NOI比赛从1984年开始举办，而IOI比赛在1989年，NOIP比NOI要晚上许多，APIO更是最近才兴起的信息学竞赛。这个知识点基本不可能准备相关知识，只能靠选手的经验和常识来作答，当然CCF的本意可能是让大家多看一下NOI的官方网站（），历年来的这类型题目都是由网站上出现过的内容出的题目。 数学知识题（6题）本类型题目主要由进制转换、前中后缀表达式、原码补码反码、逻辑判断等知识点组成，其中进制转换是每年必考察的一个点，需要高度重视。今年进制转换的题目是单项选择题的第一、五题，其中第五题是道比较易错的题，主要要点是需要判断出7*7=41在哪个进制下成立（12进制），判断出来还需要注意12(12)=14(10)，14*14=196(10)=144(12)，这一连串的转换对选手对进制转换的了解程度提出了很大的挑战，也考察了选手的细心程度，确实是一道不错的题目。前中后缀表达式几乎也是年年考的题目，今年考的是较少出现的前缀表达式，按照定义解答即可。当然如果有兴趣的同学还可以画一棵表达式树，这是秒杀该类题目的通用方法。今年逻辑判断题也很有新意，判断哪个式子恒为真。用枚举法或者构造法都可以，在此就不再详述。非常有意思的是，今年的数学知识题终于出现了一道完全与计算机无关的立体几何题（不定项第8题），并直接导致大量高一高二同学出现了计算的障碍，浪费了时间影响了成绩。我认为这种题目不适宜出现在NOIP的赛场上，高一同学此时应该刚刚接触到几何与函数，高二同学视各地进度不同有些可能还没有接触到立体几何，而这道题目没有立体几何的知识基本是做不出来的，这就失去了考察的意义。一种比较快捷的解法是将三个点做出两个相交向量，然后将选项中给定的点也写成向量形式与两个相交向量分别相乘，两个结果都是0则该向量与三个点确定的平面垂直。总而言之，本届数学题能看出出题者在求新上下了一些功夫（后面的问题求解也说明了这点），相对以前单调的考察方式做出了一些改变，就我个人的看法而言这是一件好事，这对筛选出学的“活”的人才非常有利。 语言常识题（1题）09年消失的类型的题目又回归了，不过考察难度一直在降低，较为冷僻的语言已不再过多涉及，更重视时下热点的概念，如面向对象等。今年考察的是语言的定义，题目并没有太大的难度，高级语言相信许多人都会回答，自然语言则可以通过“望文生义”的方法推测其错误（实际上编程语言都是“人造语言”而非如汉语一般的“自然语言”），有些难度的可能是后面两项，解释语言是指需要用翻译器来运行而不能独立运行的语言，如大家熟知的Visual Basic 5以前的版本；Pascal、C、C+均是编译语言，就是直接可以独立运行的语言。 算法常识题（3题）算法常识题最常见的类型就是排序算法了，这个在信息学竞赛中常用的算法自然也成为了初赛考察的一个重点，因此最近数年都有提及排序算法。今年题目考察了一个叫“原地排序”的概念，放在不定项选择题里确实很有难度，要求选手对常见常用的排序算法都要了解透彻。排序算法中属于原地排序的是：希尔排序、冒泡排序、插入排序、选择排序、快速排序、堆排序。至于后面的拓扑排序与双向链表的删除没有特别之处，在此省略。 数据结构常识题（3题）栈、队列、线性表、二叉树等基本常识是该类题目考察的重点，二叉树几乎是年年都会考，不过涉及的都是基本概念；栈的考察相对灵活，不过只要抓住FILO（先进后出）概念一般都能很好的解答。如不定项选择题第一题，题目的“第一个出栈的是R3”是想告诉我们R2把R1压住了，这说明R2根本不可能最后一个出栈。其他选项都有可能，于是就可做出选择了。又如不定项选择题第五题，这题非常有意思，众所周知前序和后序遍历不能确定一棵树，然而这题通过推算发现左子树的大小竟然是唯一的！方法是，先将根（A）拿出来，然后递归地枚举左子树大小，判断是否符合遍历条件。这也是没见过的一种题型，要求选手对概念掌握较深。总结：依照上图可见，选择题的考察还是很均衡的，题型设计也比较合理。今年题目的一个突出特点是出现了一些新类型的、考的比较“活”的题目，可以看出初赛的“死记硬背”将逐渐失去功效。（2） 问题求解今年的问题求解题可称得上是“十分精彩”！题目难度适中，有一定思考难度而又不显得过难，不过分考察选手的运算能力（这也是今年全卷的特点），被人诟病许久的组合数学题第一次消失，总的来说是一种适应时代发展的改变。下面就来详细说一下问题求解的题目。 LZW算法语文阅读题，读懂题目就能做。不过LZW算法是个很漂亮的算法，是LZ系列算法（WinZip用的算法的组成部分，也是现在几乎所有的压缩软件、压缩算法的基础）的一个改进算法。有兴趣的同学可以自行查阅相关资料。 简单回路这题对于部分参加数学竞赛或者做了一些准备的同学来说应该不算是一道难题，因为有Turan定理的存在：空间内n个点，若点之间的连线条数大于(n2+1)/4（取整），则必定存在一个以这些点为顶点的三角形。当然假如不知道这题也可以做，构造法就是最强大的武器。下面详述如何构造一个符合条件的解：由于7个点非常容易出现奇数圈，因此我们先用六个点画出尽可能多的边：这里共有6+3=9条边，且没有出现奇环；且明显不能再加边，否则就会出现奇环。然后多加一个点向原有点连线。由于不能连接相连的点（这样直接出现了奇环），因此一个可行的方案是：9+3=12条边。这样就构造出了一个可行的方案。考囗试场上并不难想到这个方案，但是难就难在不能确定他是最多的。这就要靠直觉与反复的尝试才能确定了。 队列与“9”这道题也是一道很有意思的题目，详细证明比较繁琐，可以通过余数的性质分情况讨论得出，当然考囗试时最简单的方法就是举反例了。比如8个的情况，可以是8个4，这样怎样都不可能得到9；以此类推。最容易错的应该是错误的得到了答囗案17，一个反例是：8个1,1个10,8个1，这样依次进入队列后不可能得到9。（3）阅读程序写答囗案今年阅读程序题明显偏“水”，当然最值得高兴的就是计算题消失了，此外程序风格有明显改善，易读性非常强，更加考察的是“阅读”程序而不是人手执行程序，只要认真推测几乎都能推测出来程序功能，进而迅速解决题目。下面来看看四题的解析。 求m+1大值程序短小精湛，主要语句也很明显，可以说是送分题。往年这题都是繁琐的计算题，不知道这题会不会让同学们耳目一新。 归并排序严格来说这题不能算是“归并排序”，只能说是归并排序的一部分，合并两个有序数列成一个有序数列。对于平时基本功良好的同学来说，这题也不是什么问题。 求r(n)的值这道题是道很有趣、同时也是比较有难度的题（我认为这道题除去阅读难度而言算是阅读程序最难的一道题目了），要很好地解决这道题，首先我们要明确一个定理：r(n)无论在什么时候调用，其值不变。这样我们就可以反复调用我们之前算过的r(n)的结果。注意到程序有一个判断n=num则exit(n)/return n的过程，很容易就可以知道r(1)r(5)=15。那么对于大于5的数都要经过一个主要的判断过程是检索n-5n-1的r值，如果小于0则赋值51，则r(6)就能很明显看出来是-1了（这点非常关键，有许多同学认为大于5的数都大于0，这是不对的），那么r(7)r(11)就能依次等于15了。而第二个难点是r(12)的计算，r(12)与r(6)面对的处境是一样的（r(7)-r(11)都大于0），所以r(12)也等于-1，那么题目要求的r(16)也就容易得到答囗案了。这题的本质是定义了一个周期为6的函数r(n)，其中当然对于大部分同学来说这道题就到此为止了，但按照出题人的说法，这个程序实际上为了解决经典的取石子问题，具体交给各位思考。 求哈密尔顿回路这题的关键是看懂successful函数的含义。搜索的过程并不难看懂，如果实在看不懂手动模拟一下也能看出来是一个对于rn方案的枚举，successful是判断rn里储存的方案是否是一个合法的哈密尔顿回路。当然这题一个非常非常易错的地方就是搜索的顺序决定了输出的方案必定是所有可行方案的字典序最小的一个，尽管输入数据只有两组方案，但是由于输入数据给定的顺序问题，也有许多同学忽略了这个问题，造成不必要的失分。（4）完善程序完善程序题一向是NOIP初赛的一个难点，然而今年题目确实称不上“难”，然而对于给定题目的理解提出了更高的要求，以往不会做给定题目但会填程序的情况有所减少。下面来看一下两道题目： 过河问题这道题是一道经典问题，搜索也是一个非常典型的算法了。这道题的特点是程序风格非常良好，定义了大量易于读懂的常量，这在往年是不可想象的；同时函数名都很明显地说出了程序的作用，这也是很不错的地方。题目的难度主要在于第一个空，num=2让许多选手阴沟里翻船，其实这个错误大部分的原因还是因为粗心，假如选手用n=2的情况对程序进行验证，这个错误是立马可以发现的。其他填空点大多集中在对递归调用和回溯的考察，会搜索的同学基本都不会出现太多的问题，在此就略过。 烽火传递这道题也可以算是一道经典题目了，用单调队列也可以解决本题，不过题目用了堆的实现方式，也没有问题（就是复杂度上面的区别）。首先我们要理解题目的解决方法：定义Opti为在i处建立烽火台的传递烽火的最小代价，我们可以注意到一个Opti仅和Opti-m-1Opti-1有关，所以这道题实际上是一道动态规划题。那么动态规划方程是 。在写出DP方程后，我们就可以理解为什么题目要用最