NOIP提高组初赛历年试题及答案求解题篇.doc

NOIP提高组初赛历年试题及答案求解题篇
问题求解题（每次2题，每题5分，共计10分。每题全部答对得5分，没有部分分）注：答案在文末
提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。
NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如图所示。那么，5个顶点的平面图至多有_________条边。

NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将A移到B之前，变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。
NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q, r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论p, q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r和p∨(q∨r)等价，p∨¬p 和q∨¬q 也等价； 而p∨q 和p∧q不等价。那么，两两不等价的布尔表达式最多有_________个。
NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有_________个不同的独立集。
NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：
就破解出了密码s1=_________，s2=_________，s3=_________，s4=___
NOIP2013-2. 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳_________次。
NOIP2014-1.由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。
NOIP2014-2. 如图所示，图中每条边上的数字表示该边的长度，则从A 到E 的最短距离是_________。
NOIP2015-1. 在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数任意一个数整除的数有_________个。
NOIP2015-2. 结点数为 5 的不同形态的二叉树一共有_________种。(结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子，另一种是根结点和右儿子。)
NOIP2016-1. 一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果 每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。
NOIP2016-2. 某中学在安排期末考试时发现，有 7个学生要参加 7门课程的考试，下表列 出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_________个不同的考试时间段才能避免冲突？

NOIP2011-1. 无向简单图问题
C(4,2)=6；C(5,2)=10。但这是“边仅在顶点上才能相交”的简单连通平面图，可手画该平面图计算边数，也可根据平面图的欧拉公式（v＋f＝e＋2）推得的定理：设G为有v个顶点e条边的简单连通平面图，若v>=3，则e<=3v-6，计算得9。
NOIP2011-2 最长正序列问题
在普及组求解题中，我们介绍了列表求编辑距离的方法。这里我们也可以用更简便的方法——“最长上升子序列”法。原字符串的最长上升子序列为：ACEGI，剩下4个字符移动插入4次即可。
其中，用动态规划的方法来求出最长上升子序列的长度。将第一个字母的值设为1。之后对于每一个字母，都在字符串前面找比它小（在想要成为的字符串中在它前面的）的字母，并从中选出值（n）最大的，将这个字母的值设为n+1。如果找不到就设为1。在以下的表格中，可以看出最大的值为5，即最长上升子序列的长度为5。

NOIP2012-1 逻辑运算问题
三个变量，每个变量可取0,1两种值，共有2^3=8种组合；任意一个变量组合代入表达式，只有0和1两种值。因此两两不等价的表达式最多有2^8=256种。
NOIP2012-2 图的独立集问题
图1的独立集：{∅}{1}{2}{3}{2,3}
图2的独立集：{∅}{1}{2}{3}{4}{5}{1,4}{1,5}{1,4,5}{2,3}{3,4}{3,5}{3,4,5}{4,5}
图3可使用DP求解：设m(i)为以i号点为根结点的总个数；f(i)为选i的总个数；g(i)表示不选i的总个数，则有：m(i)=f(i)+g(i)
f(i)=g(left_child[i])*g(right_child[i])
g(i)=m(left_child[i])*m(right_child[i])
m(17)=f(17)+g(17)=1936+3600=5536
f(17)=g(8)*g(8)=44*44=1936
g(17)=m(8)*m(8)=60*60=3600
m(8)=f(8)+g(8)16+44=60
f(8)=g(1)*g(6)=1*16=16
g(8)=m(1)*m(6)=2*22=44
m(6)=f(6)+g(6)=6+16=22
f(6)=g(1)*g(4)=1*6=6
g(6)=m(1)*m(4)=2*8=16
m(4)=f(4)+g(4)=2+6=8
f(4)=g(1)*g(2)=1*2=2
g(4)=m(1)*m(2)=2*3=6
m(2)=f(2)+g(2)=3
f(2)=g(1)=1
g(2)=m(1)=2
m(1)=2
f(1)=1
g(1)=1
NOIP2013-1 方程求解问题
同普及组求解题，略。
NOIP2013-2 随机概率问题
若n = 2 下一步无非跳到1或跳到2再跳到1
f(2) = [ 1 + ( 1 + f(2) ) ] / 2 ，所以 f(2) = 2
若n = 3 ，则有f(3) = [ 1 + ( 1 + f(2) ) + ( 1 + f(3) ) ] / 3 =5/2……
若n=5，则有f(5) = [ 1 + …… ( 1 + f(5) ) ] / 5=37/12
也可设n个荷叶时的答案为an，则有an=1+(a1+a2+…an)/n，可得：an=(a1+a2+…+an-1+1)/(n-1)，其中a1=0。可以推导出公式：
an=1+1/1+1/2+…+1/(n-1) (n>1)，则a5=37/12
NOIP2014-1 排列组合问题
第一种情况：四位数中有两位数字相同，如：1124、1128、1148、1288、1488、2488，共六种组合，每种有A(4,2)=4×3=12种排列方法，共有12×6=72种。
第二种情况：四位数中没有相同的数字，如1248，只有一种组合，排列方法共有A(4,4)=4×3×2×1=24种。
第三种情况：四位数中各有两个数字相同，如1188，只有一种组合，A(4,2)/2=6种。
所以，共有72+24+6=102种。
NOIP2014-2 最短路径问题
我们可以用倒推的方法，求A到E的最短距离。用k来表示阶段
k=4，有d4(D,E)、d(I,E)来表示有两条路。f4(D)=5;f4(I)=4
k=3，用d3(C,D)、d3(C,I)、d3(H,D)、d3(H,I)来表示有四条路。
f3(C)=min{d3(C,D),d3(C,I)}=min{8+5,9+4}=13
f3(H)=min{d3(H,D),d3(H,I)}=min{3+5,4+4}=8
k=2，有f2(B)=min{d2(B,C),d2(B,H)}=min{1+13,7+8}=14；
其中，d2(B,H)有另一条最短路径BCFH，所以
f2(B)=min{d2(B,C),d2(B,H)}=min{1+13,1+1+2+8}=12；
f2(F)=min{d2(F,C),d2(F,H)}=min{1+13,2+8}=10；
f2(G)=min{d2(G,C),d2(G,H)}=min{2+13,4+8}=12
k=1，有f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}=min{3+12,4+12,6+10}=15
NOIP2015-1. 容斥原理问题
第一步，在全部2015个元素中，分别排除能被4,5,6整除的元素
第二步，加上以上重复排除的元素，即能同时被两个数整除的元素
第三步，再排除第二步中重复加进的元素，即能同时被三个数整除的元素
n-[n/4]-[n/5]-[n/6]+[n/20]+[n/12]+[n/30]-[n/60]=1075
NOIP2015-2 卡特兰数问题
C(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... +C(n-1)C(1)，n>=2
C(5)=42
NOIP2016-1 斐波那契数列问题
n个方格的填涂分为两种情况。
1、  第一个方格为黑色，那么第二个方格一定是白色，所以第一种情况数就是n-2个方格的填涂方案数。
2、  第一个方格为白色，那么第二个方格不定。所以第二种情况数就是n-1个方格的填涂方案数。
所以f(n)=f(n-1)+f(n-2)， 也就是说这是一个斐波那契数列问题。边界条件是：f(1)=2(黑,白)；f(2)=3(黑白,白白,白黑)。则有：
F(n)=F(8)=f(6)+f(7)=55
NOIP2016-2 图的独立集问题
从上表可以看出：
可将每门考试科目标号，并作为图的顶点画图，根据每位学生需要考试的科目，连接顶点与顶点，考三门连三条边，考两门则连一条边。形成该图的至少三个独立集：{1,3,5}{2,7}{4,6}，使所有考试安排不冲突。所以：
考第一门时，可以同时考第三门、第五门（或第七门）
考第二门时，可以同时考第七门（或第五门）
考第四门时，可以同时考第六门
即最少安排3个不同的考试时间段才能避免冲突。