问题求解：每次共2题，每空5分，共计10分。每题全部答对得 5 分，没有部分分。注：答案在文末

在NOIP初赛问题求解中，经常会遇到排列组合问题。这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律。

解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析解答。同时还要注意讲究一些策略和技巧，比如采用分类、分步、捆绑等方法，也可以借助表格、方程等工具，使一些看似复杂的问题迎刃而解。

---

NOIP2011-1. 每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。例如，0000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有______个。

NOIP2011-2. 定义字符串的基本操作为: 删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。字符串“ ABCDEFG ”到字符串“BADECG ”的编辑距离为_______。

NOIP2012-1. 如果平面上任取n 个整点(横纵坐标都是整数) ，其中一定存在两个点，它们连线的中点也是整点，那么n至少是_____。

NOIP2012-2. 在NOI期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么，这一桌共有_____种不同的就坐方案。注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。

NOIP2013-1. 7 个同学围坐一圈，要选2 个不相邻的作为代表，有_____种不同的选法。

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

NOIP2014-1. 把M 个同样的球放到N 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法?(用K 表示)。例如：M = 7，N = 3 时，K = 8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。问:M = 8，N = 5 时，K = _____。

NOIP2014-2. 如图所示，图中每条边上的数字表示该边的长度，则从A 到E 的最短距离是____。

NOIP2015-1. 重新排列 1234 使得每一个数字都不在原来的位置上，一共有_____种排法。

NOIP2015-2. 一棵结点数为 2015 的二叉树最多有_____个叶子结点。

NOIP2016-1. 从一个 4×4 的棋盘(不可旋转)中选取不在同一行也不在同一列上的两个方格，共有______种方法。

NOIP2016-2. 约定二叉树的根节点高度为1。一棵结点数为2016 的二叉树最少有______个叶子结点;一棵结点数为2016 的二叉树最小的高度值是______。

---

NOIP2011-1. 组合计数问题。

C(n,m)=n!/(n-m)!*m!

C(8,0) + C(8,2) + C(8,4) + C(8,6) + C(8,8) = 128

NOIP2011-2.编辑距离问题。

先创建一个8×9（BADECG长度为6，ABCDEFG长度为7，各加2）的表如下：

1、在第一行第一列分别填上两个字符串

2、  在第二行第二列分别填上序列号

3、  从第三行第三列这一格开始计算填充。行列字符相等，则填左上角的数字；行列字符不等，在“左上角数字+1、左方数字+1、上方数字+1”中取最小值填充

4、  取最右下角的值，得编辑距离为3。

NOIP2012-1. 鸽巢原理问题。

同一直线上三个点的坐标：(x1,y1)、(x2,y2)和中点（(x1+x2)/2, (y1+y2)/2）。

如果三个点都是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。
平面上的整点只有四类：(奇数,奇数)，(偶数,偶数)，(奇数,偶数)，(偶数,奇数)，
根据鸽巢原理，在平面上任取五个整点，那么至少有两个整点属于一类，它们连线的中点就必是整点。所以n至少是5。

NOIP2012-2. 圆桌排列问题。

以3人为例，直线排列方案：A(3,3)=3!=6，分别是：123,132,213,231,312,321，如果是圆桌排列，则：123,231,312是重复方案，132,213,321是重复方案，实际有效方案为：3!/3=2。

本题中，大陆选手先排列，则有A(5,5)=5!；港澳选手再排列，共有5!*5!；再排除圆桌重复排列，则有：5!*5!/5=2880

NOIP2013-1. 乘法原理问题。

先选1个同学出来，7种选法；再选第2个同学出来，4种选法。所以，共有7×4÷2=14种选法。注意：去除重复部分（如第1次选a，第2次选b与第1次选b，第2次选a一样）

NOIP2013-2. 方程求解问题。

求解得出S1=0，S2=1，S3=1，S4=1。

NOIP2014-1. 排列组合问题。

设K=f(m,n)为m个球，n个袋子的放法数目，可以分成两类：含有0的方案数，不含有0的方案数。

当m=0，或n=1时，f(m,n)=1；当m<n时，f(m,n)=f(m,m)，当m>n时，则有：

1、含有0的方案数，即有至少一个袋子空着，即相当于 f(m,n)=f(m,n-1)

2、不含有0的方案数，即全部袋子都有球，那么先从m个球中抽取出n个出来，各个袋子分一个，考虑剩下的m-n个球放到n个袋子里的放法，即 f(m,n)=f(m-n,n).

而总的放法数目等于两者的和，即f(m,n)=f(m,n-1)+f(m-n,n)

所以：f(8,5)=f(8,4)+f(3,5)=18

NOIP2014-2. 最短路径问题。

我们可以用倒推的方法，求A到E的最短距离。用k来表示阶段。

k=4，有d4(F,E)来表示F到E的距离。f4(F)=6

k=3，用d3(C,E)、d3(C,F)、d3(D,F)、d3(D,E)来表示有四条路。

f3(C)=min{d3(C,E),d3(C,F)}=min{8,1+6}=7

f3(D)=min{d3(D,F),d3(D,E)}=min{2+6,4}=4

k=2，有f2(B)=min{d2(B,C),d2(B,D)}=min{1+7,7+4}=8；

f2(G)=min{d2(G,C),d2(G,D)}=min{2+7,4+4}=8

k=1，有f1(A)=min{d1(A,B),d1(A,G),d1(A,F)}=min{3+8,4+8,6+6}=11

NOIP2015-1. 错位排列问题。

D_n=n!(1-1/1!+1/2!-1/3!+…)，D₄=24×(1/2-1/6+1/24)=9

NOIP2015-2. 完全二叉树问题。

二叉树的叶子结点（N0） = 度为2的结点数（N2）+1。二叉树叶子节点最多，即度为2的结点数最多，这就是完全二叉树，2015个结点的完全二叉树。

2015 = N0 + N1+ N2，当完全二叉树度为1的结点数N1 = 0时，N0 = 1008。

NOIP2016-1. 乘法原理问题。

第一个方格的选取方法：4*4=16；由于要求不同行不同列，则第二个方格的选取方法：3*3=9

根据乘法原理，且两个方格无前后排序，去除重复，则有16*9/2=72

NOIP2016-2. 完全二叉树问题。

当度为2的结点数(N2)=0时，叶子结点最少。则叶子结点(N0)=度为2的结点数(N2)+1=1；

当为完全二叉树时，二叉树的高度值最小。设二叉树得高度值为i，则共i层的完全二叉树最多有2^i-1个节点。则有：2016<=2^i-1，所以，i>=11，即最小高度值为11。