问题求解题(每次2题,每题5分,共计10分。每题全部答对得5分,没有部分分)注:答案在文末

提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。

NOIP2011-1.平面图可以画在平面上,且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边,如图所示。那么,5个顶点的平面图至多有_________条边。

【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

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有_________个不同的独立集。【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn,均为0或1。该系统每次随机生成n个数a1,a2,…,an,均为0或1,请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。

然而,事与愿违。例如,当n=4时,有人窃听了以下5次问答:【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

就破解出了密码s1=_________,s2=_________,s3=_________,s4=_________。

NOIP2013-2. 现有一只青蛙,初始时在n号荷叶上。当它某一时刻在k号荷叶上时,下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上,直至跳到1号荷叶为止。当n=2时,平均一共跳2次;当n=3时,平均一共跳2.5次。则当n=5时,平均一共跳_________次。【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

NOIP2014-1.由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。

NOIP2014-2. 如图所示,图中每条边上的数字表示该边的长度,则从A 到E 的最短距离是_________。【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

NOIP2015-1. 在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数任意一个数整除的数有_________个。

NOIP2015-2. 结点数为 5 的不同形态的二叉树一共有_________种。(结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子,另一种是根结点和右儿子。)

NOIP2016-1. 一个1×8的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果 每个方格只能填涂一种颜色,且不允许两个黑格相邻,共有_________种填涂方案。

NOIP2016-2. 某中学在安排期末考试时发现,有 7个学生要参加 7门课程的考试,下表列 出了哪些学生参加哪些考试(用√表示要参加相应的考试)。 最少要安排_________个不同的考试时间段才能避免冲突?

【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网

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。

【NOIP提高组】初赛历年试题及答案(求解题篇)-少儿编程教育网
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个不同的考试时间段才能避免冲突。