1、NOIP 提高组初赛历年试题及答案求解题篇问题求解题（每次 2 题，每题 5 分，共计 10 分。每题全部答对得 5 分，没有部分分）注：答案在文末提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。NOIP2011-1平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4 个顶点的平面图至少有 6 条边，如图所示。那么， 5 个顶点的平面图至多有_ 条边。NOIP2011-2定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将 A 移到 B 之前，变字符串“ABC” 。如果要将字符串“DACHE
2、BGIF”变成“ABCDEFGHI”最少需要_次操作。NOIP2012-1. 本题中，我们约定布尔表达式只能包含 p,q, r 三个布尔变量，以及“与”（）、“或” （）、“非”（）三种布尔运算。如果无论 p, q,r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p q)r 和 p(qr)等价，pp 和 qq 也等价； 而 pq 和 pq 不等价。那么，两两不等价的布尔表达式最多有_ 个。NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（ 1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的
3、独立集。那么，图 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 号荷叶上。当它某
4、一时刻在 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 的不同形态的二叉树一共
5、有 _种。(结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子，另一种是根结点和右儿子。)NOIP2016-1. 一个 18 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果 每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_种填涂方案。NOIP2016-2. 某中学在安排期末考试时发现，有 7 个学生要参加 7 门课程的考试，下表列 出了哪些学生参加哪些考试（用表示要参加相应的考试）。 最少要安排_ 个不同的考试时间段才能避免冲突？NOIP2011-1. 无向简单图问题C(4,2)=6；C(5,2)=10。但这是“边仅在顶点上才能相交”的简单连通平面图，可手画该平面图计算
6、边数，也可根据平面图的欧拉公式（vfe 2）推得的定理：设 G 为有 v 个顶点 e 条边的简单连通平面图，若 v=3，则 e1)，则 a5=37/12NOIP2014-1 排列组合问题第一种情况：四位数中有两位数字相同，如：1124、1128、1148、1288、1488、2488 ，共六种组合，每种有 A(4,2)=43=12 种排列方法，共有 126=72 种。第二种情况：四位数中没有相同的数字，如 1248，只有一种组合，排列方法共有 A(4,4)=4321=24 种。第三种情况：四位数中各有两个数字相同，如 1188，只有一种组合，A(4,2)/2=6 种。所以，共有 72+24+6
7、=102 种。NOIP2014-2 最短路径问题我们可以用倒推的方法，求 A 到 E 的最短距离。用 k 来表示阶段。k=4，有 d4(D,E)、d(I,E)来表示有两条路。f4(D)=5;f4(I)=4k=3，用 d3(C,D)、d3(C,I)、d3(H,D)、d3(H,I) 来表示有四条路。f3(C)=mind3(C,D),d3(C,I)=min8+5,9+4=13f3(H)=mind3(H,D),d3(H,I)=min3+5,4+4=8k=2，有 f2(B)=mind2(B,C),d2(B,H)=min1+13,7+8=14；其中，d2(B,H)有另一条最短路径 BCFH，所以f2(B)
8、=mind2(B,C),d2(B,H)=min1+13,1+1+2+8=12；f2(F)=mind2(F,C),d2(F,H)=min1+13,2+8=10；f2(G)=mind2(G,C),d2(G,H)=min2+13,4+8=12k=1，有 f1(A)=mind1(A,B),d1(A,G),d1(A,F)=min3+12,4+12,6+10=15NOIP2015-1. 容斥原理问题第一步，在全部 2015 个元素中，分别排除能被 4,5,6 整除的元素第二步，加上以上重复排除的元素，即能同时被两个数整除的元素第三步，再排除第二步中重复加进的元素，即能同时被三个数整除的元素n-n/4-n/
9、5-n/6+n/20+n/12+n/30-n/60=1075NOIP2015-2 卡特兰数问题C(n) = C(1)*C(n-1) + C(2)*C(n-2) + . +C(n-1)C(1)，n=2C(5)=42NOIP2016-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)=55NOIP2016-2 图的独立集问题从上表可以看出：可将每门考试科目标号，并作为图的顶点画图，根据每位学生需要考试的科目，连接顶点与顶点，考三门连三条边，考两门则连一条边。形成该图的至少三个独立集：1,3,52,74,6，使所有考试安排不冲突。所以：考第一门时，可以同时考第三门、第五门（或第七门）考第二门时，可以同时考第七门（或第五门）考第四门时，可以同时考第六门即最少安排 3 个不同的考试时间段才能避免冲突。
