CSP真题系列(5)-NOIP2016初赛 普及组 提高组真题解析及答案参考！
摘要
NOIP2016初赛提高组真题及答案
一、单选
1、D
蒙也是能蒙对的
2、A
注意，它问的是输出的第81个字符，不是按的，所以选B的童鞋好好读题=w=
依旧看做6个一组，81 div 6=13；易知奇数组是大写，偶数组是小写，所以显然是大写=w=；
然后再关注输出的是哪个字母，输出的看做5个一组，81 mod 5=1；所以是A
于是回来说的时候还有一种蒙题大法：
你看看，四个选项，只有A和D是a的大小写，所以不是A就是D，再看看，ABC都是大写，所以不可能正确答案是小写，所以一定是A
3、B
送分题
4、B
送分的进制转换=w=，如果你做了前几年的题，你会发现有一道类似题，只是让转成16进制，所以那些看都不看就选A的.....自罚吧=。=
5、B
这个随便推推就行了，D是出不来的（至少也是nlogn)
6、B
前些年考过前缀表达式于是几年来了个后缀表达式=。=，其实同理推推也能蒙对，因为后缀表达式与前缀表达式类似，只是运算符位于操作数之后，个人建议系统的学习一下，不仅是为了初赛也是为了复赛=。=
大力推荐一篇博文：antineutrino博主写过一篇叫做《前缀、中缀、后缀表达式》的文章
7、B
8、B
注意它说的是非联通，所以选C的童鞋..=.=；完全图的边数是n*（n-1)/2;所以n=8；所以非联通，至少9个点
9、B
2^32B=4G
10.D
这题错的你后面还怎么做=。=
11、B
好吧，我做这题的时候脑残没多想，直接选的C,之前能选对全是间歇性机智症犯了=。=
各种可能的放置情况如下：
（7，0，0），
（6，1，0），
（5，2，0），（5，1，1），
（4，3，0），（4，2，1），
（3，3，1），（3，2，2），共8种；
蒙题大法：你看啊，ACD不是7的倍数就是7是指数，只有B和7的倍数没有那么直接的关系，出题人肯定不会闲的给你出一个显然是不对的选项，所以一定选B 0rz
12、A
就看Jacob和哪个相连，就绝对不能让他看见照片，就是不管怎么传都不能连上他们，然后恭喜你，心机成功了=。=
13、C
水过就好
14、C
其实我并不是很会算，所以就“代数试”，带个4、8什么的，算一下看看哪个选项对就行了=。=，要注意递推式中T前面的2，因为没有记忆化，所以要算2次，所以考场上我手滑就选B了=。=
15、A
这题不会的最后一道大题可以洗洗睡了
二、
1、ABC
考试的时候我就只知道AB肯定对，于是C就没有选，走出考场的时候听他们一说就感觉心里拔凉拔凉的，这就是教科书版的擦肩而过QAQ
GPRS（General Packet Radio Service）是通用分组无线服务技术的简称，它是GSM移动电话用户可用的一种移动数据业务，属于第二代移动通信中的数据传输技术 ——来自百度百科
2、A
3、AB
最近排序年年考，所以一定要注意=。=
4、A
这题画风不对啊=。=，不过是送分的我都欢迎=w=
5、ABD
=。=
三
1、55
这其实就是一个Fibonacci
第一种做法你可以从1*1的开始列举，然后横着开始列1*2……，如果上一位最后是0那就两种情况，是1的话就只有0一种情况，所以一般列到1*4或1*5的就能发现Fibonacci了
第二种就是动态规划，反正我不知道怎么弄，但是据说写出递推式来以后就会发现就是Fibonacci
然后就是注意全涂白也是一种染色方案，眼见一位位大神就跪在了54
2、3
随便推推吧，根据第一个人你会发现最少也得分三次，然后我就拽着通用技术往下看，发现3个还真就满足了
四
1、6,5,4,3,2,1， （倒序输出，逗号走丢的快用8分赎回来）
2、YES，NO，YES， （就是看冒号前面的字符串的字符有没有按照顺序在冒号后面的字符串中出现，关键是程序的理解，当然要是生推也是可以的，
逗号走丢的快用8分赎回来）
3、5（每年一道的递归题)
4、2 5（考试的时候没仔细看weight的运算，鬼知道我怎么写出来个2 6 ，那些写5 2 的童鞋....）
五、完善程序
1.
(1)会快排的人都知道。
(2)模仿上面的previous的写法就行。
(3)也是模仿上面的shorter写，但是顺序要调一下。
(4)可以看出shorter就是与矮的人的身高差，higher就是与高的人的身高差，然后根据题目就可以看出来了。
(5)还是模仿上面的next写。
2.自己上网找SPFA，会了就不难，如果不熟悉SPFA也能写出来几个空。
NOIP2016初赛普及组真题及答案