NOIP2016提高组初赛解析.pdfVIP

一、单项选择题 1.这题不是zz 都能选对。 2.不难看出按键的顺序是五个一循环，于是可以求出共有多少个循环，进而求出按了多少次 CapsLock，最后就可以得出答案。 3.异或就是按位运算，相同取1，不同取0，知道了这个就很容易得出答案。 4.把二进制数0.1先转成十进制，再转成八进制。 5.以第一个数为基准，依次比较后面的N-1个数即可。 6.画出中缀表达式的树型图，求其后序遍历即可。 7.把每一个叶子结点和只有一个孩子的结点算一下就行。 8.根据公式(8-1)*8/2 得到28 条边，然后增加一个节点使其成为非连通图。 9.计算机硬件知识（说实话考试的时候并不会，但是看到一堆选B 的就蒙了B 结果蒙对了）。 10.手动模拟就行。 11.也是手动模拟，注意形如(1,2,4)和(4,2,1)算同一种方法。 12.就是找图中没有与Jacob连线的人。 13.手动模拟。 14.即使不会使用主定理，也可以列举一些特殊数值，并根据 O() 记号的含义得出答案。 15.第一个空表示第k个数就是峰顶，第二个空表示峰顶在[k+1,n]，第三个空表示峰顶在 [1,k-1]，理解程序就不难做对。 二、不定项选择题 1.计算机基础知识。 2.即使你不知道网络接入通讯设备是什么也可以做出来，毕竟光驱、鼠标、显卡和网络从名 字上看都没有半毛钱关系。 3.太简单不解释，做错的回去再学几年去吧。 4.看懂图就行，这题完全是模拟，把四个选项都模拟一下就行。 5.不解释。如果你选了U盘，那你不如把直接你教练带去帮你得了。 三、问题求解 1.很简单的斐波那契数列。考试的时候我就是把1*1到1*5 的方格都模拟一下，规律就不难 找到了。考试结束后我思考了一下，设f[n]表示1*n 的满足条件的方格的数量，则当前格只 有两个选择：涂白或图黑。第i个格子只和第i-1个格子有关系，所以如果第n个格子涂白， 那么第n-1个格子怎么涂都行，如果第n个格子涂黑，那么第n-1个格子只能涂白，但是第 n-2 个格子可以任意涂，所以f[n] f[n-1]+f[n-2]。 2.手动模拟。 四、阅读程序写结果 1.就是倒着输出，但是逗号引发了一场血案。 2.判断冒号前的字母是否在字符串中出现，大小写要区分。逗号依然在逃，再次引发血案。 3.别人说是最大回文子序列，我也不知道怎么推的，不过递归模拟下就行，顶多10 分钟就 能做出来了。 4.求树的重心。 五、完善程序 1. (1)会快排的人都知道。 (2)模仿上面的previous 的写法就行。 (3)也是模仿上面的shorter 写，但是顺序要调一下。 (4)可以看出shorter就是与矮的人的身高差，higher就是与高的人的身高差，然后根据题目 就可以看出来了。 (5)还是模仿上面的next 写。 2.自己上网找SPFA，会了就不难，如果不熟悉SPFA 也能写出来几个空。 对于考生来说，一些基础的数学和贪心还是要知道的，比如选择题第13 题和问题求解第一 题。但是普及组里常考的计算机基础知识在提高组试卷里出场率并不高，啃初赛书的用处并 不太大。对于看程序写结果，只能竖起中指。前两题完全考察细心，第三题直接看懂程序并 不容易，不过运输量并不大，大概也就11*11/2 左右，手算完全可以出结果。第四题程序量 和运算量都大幅提升，单纯的模拟几乎没有前途，但是看懂程序后可以秒出结果。对于完善 程序，这也是对患有STL依赖症的同学的警告，快排都打不出来情何以堪！写着写着就发 现，这些空大都具有对称美，照着前一句修改就行。SPFA 这几年算有些冷了 （对我来说）， 因为最简单的最短路就是Floyd，要么就用Dijkstra，SPFA 几乎不用，可是考试突然考到 了，只能临时思考了。 总的来说这次的卷子比上次略难，但是还算合理。 不过要吐槽有些题目 （有些是网友吐槽）。 比如不定项第4 题，先不说这供水系统猎奇的装置图和高度差评的果树造型和高光，就单 在信息学奥赛题目里，完全不知道这鬼东西是考个什么算法思想。这种题目的确看不出什么 算法，不过有些送分题也是好的。 单选第12 题就更搞笑了，Lucia 明明和Jacob 是好友，还不给人家看照片，无聊吗这，再 说哪个社交网站没有访问权限设置啊，实在因垂死听。还有小学生都会把最后输出的逗号去 掉，难道老师不会吗 （老师：我就是坑你们的啊）？关键是如果看这种代码习惯了 （老是在 最后加个逗号），复赛是要丢分的啊。 完善程序第一题交♂朋友，小矮个儿没人权，STL打多了快排会忘。 C++版试题完善程序第一题这么输出： 然而Pascal版这么输出： C++的那个endl