NOIP2002-2005解题报告
NOIP讲义
一、NOIP2002
题一：均分纸牌（NOIPG1）
【问题描述】
有N堆纸牌，编号分别为1, 2, ..., N-1。每堆上有若干张，但纸牌总数必为N的倍数，可以在任一堆上取若干张，s然后移动。
移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的对上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上的纸牌数都是一样多。
输入：文件名： G1.In
第一行，为一个整数N(1<=N<=100)
第二行，为N个整数A1， A2，…AN（N堆纸牌初始数， 1<=Ai<=10000，中间用空格分开）
输出: 文件名：G2.Out
只有一行，所有堆均达到相等时的最少移动次数。
输入输出样例
G1.In
4
9 8 17 6
G2.Out
3
【问题分析】
本题实际上给我们N个数A1，A2，A3，……，A N（A1＋A2＋A3＋……＋A N是N的倍数），要求我们利用一个简单的移动规则，即对于一个A I和A I＋1（1≤I≤N－1），可以从A I中移X至A I＋1（即A I=A I－X且A I＋1=A I＋1＋X）（－A I＋1≤X≤A I），使最后A1=A2=A3=……=A N；
首先，通过A1，A2，A3，……，A N我们很容易想到先求出A1~A N的平均值___A，然
后从左至右，若A I≠___A，则使A I＋1=A I＋1＋A I－___A ，A I=___A。例如试题给我们的例点A1=9 A2=8 A3=17 A4=6，我们先计算出___A=10，然后通过以下3步即可得出A1=A2=A3=A4①因A1≠___A，使A2=A2＋A1－___A=7，A1=___A=10（10 7 17 6）②因A2≠___A，使A3=A3＋A2－___A=14，
A2=___A=10（10 10 14 6）③因A3≠___A，使A4=A4＋A3－___A=10 A3=___A=10（10 10 10 10，A1=A2=A3=A4）。但是，这种贪心方法有时会出现与实际不合的情况，例如N=3，A1=1，A2=2，A3=27此时，我们的步骤为，计算___A=（1＋2＋27）/3=10，①因A1≠___A，使A2=A2＋A1－___A=1＋2－10=－7，A1=___A=10，②因A2≠___A，使A3=A3＋A2－___A=10，A4=___A=10，但
是，我们发现：①中，第二堆牌中有负数张，这是不可能的。是不是这种贪心方法有错误呢？我们再来考虑，对于上面的情况，我们可以①从A3拿17至A2，（1，19，10）②从A2拿9至A1（10，10，10），通过观察，我们发现，用贪心法和后一种正确的方法所移动的牌是一样的，即都从A3移17至A2，从A2移9至A1。是不是对于所有的数
据都会符合呢？答案是肯定的，事实上，从A1考虑，若A1>___A，则不管怎样，它必须将A1－___A给A2，若A1<___A，则不管怎样，它必须从A2得到AX=___A－A1，若A2≥AX，则可直接从A2中取AX给A1，否则，相当于对A2~A N进行调整，使A2=___A＋AX，A3=A4=……
=A N=___A，这样就相当于一个递归的过程，事实上，A I和A I＋1最后都最多进行一次传递，所以，我们最初的贪心是正确的。
题二字串变换（NOIPG2）
【问题描述】
已知有两个字串A$，B$及一组字串变换的规则(至多六个规则) ：
A1$——>B1$
A2$——>B2$
规则的含义为：在A$中的子串A1$可以变换为B1$，A2$可以变换为B2$……。对于给定的A$，B$以及变换规则，求出从A$变换到B$所需的最少步数。
输入：文件名： G2.In
第1行，为两个字串A$ B$(用空格分开)
第2行以后的每行为两个字串A1$ B1$(用空格分开)，表示一种变换规则所有字符串长度的上限为20。
输出：文件名：G2.Out
只有1行，若在10步以内有解，输出最少步数，否则输出”No ANSWER!”。
输入输出样例：
G2.In
abcd xyz
abc xu
ud y
y yz
G2.Out
3
【问题分析】
本题给了我们两个字符串A$、B$和最多六条变换规则，要求我们用这组变换规则，将A$变为B$。
因为本题不具有最优子结构性质，且状态较难描述，所以动态规划、贪心等算法都无法使用，只好考虑搜索。
用深搜还是广搜呢？若用广搜，因最多有6条变换规则，每个字串长度为20，故每个字串最多有6*20=120种变换方法，如果变10次，则最多有12010>1020，这显然无法存储，因此我们只好考虑深搜。
用这样毫无剪枝的搜索效率是不高的，可以加入两条剪枝，来提高效率。
剪枝一：当前得到的串的长度加上规则中增长最长的与所剩步数的积（即最多还能增长的长度）还小于目标串长则可减掉。当前得到的串长度减去规则中减长最长的与所剩步数的积（即最多能减长的长度）还大于目标串长则可减掉。
剪枝二：可以给扩展串定一个开始位置，开始位置定为上次扩展的时候与之匹配的位置，从这个位置开始找能变换的，开始位置前面的不作变换。
如当前串为abcdabcefg，有规则abc efg，则当前如果把第一个abc变换成efg，则将扩展出来的节点开始位置定为第1位，如果当前是把第2个abc变换成efg，则把扩展出来的节点开始位置定为第5位，因为如果下次再把第1个abc变换成efg的话就会和先变换第1个再变换第2个重复，可以剪枝。
这道题加入这两条剪枝后速度会快很多。
题三：自由落体（NOIPG3）
【问题描述】
在高为H的天花板上有N个小球，体积不计，位置分别为0, 1, 2, …, N-1。在地面上有一个小车（长为L，高为K，距原点距离为S1）。已知小球下落距离
V前进。
小车与所有小球同时开始运动，当小球距小车的距离<＝0.00001时，即认为小球被小车接受（小球落到地面后不能被接受）
请你计算出小车能接受到多少个小球。
数据范围：1<=H，S1，V，L，K，N<=100000
输入：文件名： G3.In
只有1行，为6个数H，S1，V，L，K，N
（1<= H，S1，V，L，K，N<=100000,中间用空格分开）
输出：文件名：G4.In
只有1行，为小车能接受到的小球个数。
输入输出样例：
G3.In
5.0 9.0 5.0 2.0 1.8 5
G3.Out
1
【问题分析】
如上图：题中给了我们N个小球和一辆小车，小球的位置分别为0，1，2，……，N－1，距地面H，体积不计，小车宽L，高K。小车和小球都从0时刻开始运动，小球做自由落体运动，小车从S1开始以速度V向O做匀速直线运动，当小球与小车的距离≤10-5时，任为小球被小车接受，问给出H，S1，V，L，K，N后，有多少个小球被小车接受。
因为小球是按顺序排列的，且开始下落的时间、高度，下落时的加速度都是相同的，若且d I表示小车到达第I个小球所在位置时第I个小球所下落的距离，t I表示小车到达小球I所在位置的时间，由d=1/2*g*t2得：d I=1/2*g*t I2，d I+1=1/2*g*t I+12，d I+2=1/2*g*t I+22，因小车的方向不变，如果小车经过第I个、第I+1个和第I+2个小球，那么t I≥t I+1≥t I+2≥0，则d I≥d I+1≥d I+2，若小车能接住第I个和第I+2个小球，则它必能接住第I+1个小球。同理，若小球能接住第I个小球和第I+K（K≥0）个小球，则它必能接住第I+1至第K-1个小球。据此，我们只须求出小车能接住的第一个小球的时间和小车能接住的最后一个小球的时间即可求出小车能接住多少个小球。
对于找第一个和最后一个接住的球，直接计算可能会出现误差，所以不防用二分法。即对于一个小球I，若小车到I时小球已落地，则第一个接住和最后一个被接住的必在小球I的右边，若小车离开位置I时小球I还在空中，则第一个和最后一个被接住的必在小球I的左边，否则，第一个被接住的小球是I或在I的右边，最后一个被接住的小球是I或在I的左边。
题四：矩形覆盖（NOIPG4）
在平面上右N个点，每个点用一对整数坐标表示。这些点可以用K个矩形全部覆盖，矩形的边平行于坐标轴。当N个点的坐标和K给出后，怎样才能使得覆盖所有点的K个矩形的面积之和为最小呢。约定：
覆盖一个点的矩形面积为0；
覆盖平行于坐标轴的直线上点的矩形面积也为0；
各个矩形必须完全分开（边线与顶点也都不能重合）。
输入：文件名：G4.In
第一行，为2个整数N K（1<=N<=50, 1<=K<=4，用空格分开）。
攻击第2～N＋1行，每行为2个整数X, Y, 为平面上1个点的坐标（0 <= X, Y <= 500，中间用空格分开）。
输出：文件名： G4.Out
只有1行，为一个整数，即满足条件的最小的矩形面积之和。
输入输出样例：
G4.In
4 2
1 1
2 2
3 6
07
G4.Out
4
【问题分析】
本题给了我们平面上的n个点（n≤50），每个点用一对整数坐标表示，要求我们用k个矩形（1≤k≤4）将这些点全部覆盖，矩形的边平行于坐标轴。并且：覆盖一个点的矩形面积为0；
覆盖平行于坐标轴直线上点的矩形面积也为0。
各个矩形必须完全分开（边线与顶点也都不能重合）。
本题是此次竞赛中一道比较难的题目，因其是对平面上的点进行操作，若用搜索做，状态难以描述；用贪心做，不太可行……用动态规划做，也不能保证全对，但是，较之其他方法，动态规划也还能算得上“矮子里的高子”，因此，这道题目只好用动态规划来解决。
假设：符合题目要求的矩形压缩到坐标轴后（即在坐标轴上的射影）在X轴不相交或在Y轴不相交。例如例点可如将矩形压缩成如下形式：
其中，绿色表示S1的射影，蓝色表示S2的射影。虽然我们不能保证所有的情况都能满足，但是大部分情况它都能找出最优解。这样，以X坐标或Y坐标为状态，我们就可以很快写出动态转移方程了：
以X坐标为状态：F[I, J] = F[I – 1, K] + Cost1[K + 1, J]; 其中Cost1[A, B]表示按X 坐标排序后从PA到PB的矩形的面积。
以Y坐标为状态：F[I, J] = F[I – 1, K] + Cost2[K + 1, J]; 其中Cost2[A, B]表示按Y 坐标排序后从PA到PB的矩形的面积。
二、NOIP2003
题一：神经网络（Network ）
【问题描述】
人工神经网络（Artificial Neural Network ）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。
在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经 元之间至多有一条边相连，下图是一个神经元的例子：
神经元〔编号为1）
图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态， Ui 是阈值，可视为神经元的一个内在参数。
神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神 经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元 输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。
兰兰规定，C i 服从公式：（其中n 是网络中所有神经元的数目）
∑∈-=
E )i ,j (i
j ji i U C W C
公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒
它会向其他神经元传送信号，信号的强度为Ci。
如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。
现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网
络输出层的状态。
【输入格式】
输入文件第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。
【输出格式】
输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状
态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由
小到大顺序输出！
若输出层的神经元最后状态均为0，则输出NULL。
【输入样例】
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1
【输出样例】
3 1
4 1
5 1
【问题分析】
理解问题的第一步就是认真“读题”。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一些性质，可以发现如下特点：1．图中所有的节点都有一个确定的等级，我们记作Level(i)
2．图中所有的边都是有向的，并且从Level值为i-1的节点指向Level值为i的节点
我们不妨将其抽象为“阶段图”。
更一般地，我们可以发现所有的阶段图都是有向无环的，这样我们可以通过拓扑排序来得到期望的处理节点的顺序。
[问题关键]
确定处理节点的顺序。
[可行算法]
由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的，因此就可以设计出一个基于宽度优先搜索（即BFS）的算法：
1．初始时将所有输入层的节点放入队列；
2．取出队列中的一个元素，不重复地扩展并处理该节点所发出的边的目标节点；
3．如果队列非空，则转向2；
4．输出输出层中所有满足条件的节点。
但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点，因此需要在算法进行的过程当中额外地考虑一些边界情况的数据（这个过程即便是真实数据没有这样出也是要有的），下面给出的更一般的算法可能会更好的跳过这些边界情况。
1．对原图中所有的节点进行一次拓扑排序；
2．按照拓扑顺序处理每一个节点；
3．输出输出层中所有满足条件的节点。
[时间效率]
线性的, 已是理论下界。
题二2：侦探推理（Logic）
【问题描述】
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！
【输入格式】
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，
每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。
往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
【输出格式】
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是
罪犯，则输出Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出Impossible。
【输入样例】
3 1 5
MIKE
CHARLES
KATE
MIKE:I am guilty.
MIKE:Today is Sunday.
CHARLES:MIKE is guilty．
KATE:I am guilty.
KATE:How are you??
【输出样例】
MIKE
【问题分析】
解决问题的关键是：如何判断每句话的真伪。
可行算法：
这道题的关键点是“如何能够快速正确实现出来”，事实上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行“字符串处理”这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。
推荐的算法分为两步：
1．预处理每个人的每一句话，并把它们分类处理；
2．枚举罪犯和当前星期几，找出所有可能发生的情况。
下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述可以发现语句可分为三类：1．指明i是否是罪犯的语句；
2．指明今天是星期d的语句；
3．没有意义的语句(不符合格式要求)。
我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。
对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。
1．没说任何一句有意义的话；
2．只说真话；
3．只说假话；
4．既说真话也说假话。
需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。
最后，如果对于罪犯i存在一个d使得当前情况是可能的，我们就说i就是可能的罪犯。
时间效率：
O(MP|Day|) （其中Day={Sunday，Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}）
算法优化：
上面的算法对于比赛而言在时间效率上是完全可以接受的，但是对一道值得研究的问题，我们是否需要对算法进一步的优化呢？答案是肯定的，因为对于任何一个问题，只要当前算法的复杂度并未匹配理论的下限，就有再继续研究的价值。要么当前的复杂度下限可以向上更加精确地估计一些，要么当前的算法可以进一步地优化。下面我们就来看一个比较容易想到的优化。
我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期d的总人数，于是改
进后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有的话，再用
O(|Day|)的时间枚举星期几。这样，改进后算法的复杂度就是O(m(p+|Day|))。
那么我们可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。
题目3：加分二叉树（Tree）
【问题描述】
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空
子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。
【输出格式】
第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2
4 5
【问题分析】
题目描述的是一棵树，而这棵树的中序遍历是1，2，…，n ，我们把这样的树称作二分检索树（或排序二叉树），这样我们就由此想到了一个动态规划的经典模型最优二分检索树，描述如下：
给出按照它们的主值排序的待检索的元素1，2，…，n ，以及它们被检索的频率f[1]，f[2]，…，f[n]，要求你构造一个二分检索树，使得∑=n
i i depth i f 1)(][最
小，这里面depth(i)表示i 节点在树中的深度。
在动态规划解决这个问题时，我们通过把问题转换，最终得到了e[i,j]=min{i ≤t ≤j | w[i,j]+e[i,t-1]+e[t+1,j]}的转移方程（这里面状态i,j 表示中序遍历为i..j 的子树，w[i,j]表示这棵子树的权值和，e[i,j]表示这棵子树的最优值），由于一棵最优二分检索树根节点的左子树和右子树也都一定是最优的，因此这个满足最优化原理。
解决问题的关键：最优化原理
可行算法：
我们先来看一看最优化原理对于这道题是否适用呢？答案是肯定的，当我们试着写出状态转移方程：f[i,j]=max{i<=t<=j | d[t]+f[i,t-1]f[t+1,j]}(这里面d[i]表示节点i 的加分，f[i,j]表示最优状态)，显然如果f[i,t-1]不是最优的那么我就可以构造出更优的f[i,j]来，因此这道题也是满足最优化原理的。
类似地我们可以写出一个动态规划的算法，我们可以按照状态f[i,j]中i 与j 的距离来划分阶段（当然也有其它的划分阶段的办法），先处理掉边界情况（空树和只含有一个节点的树），然后就可以按照阶段自底向上进行动态规划了，最后再递归地输出答案就可以了。
时间效率： O(n 3)
算法优化：
我们回想起在解决最优二分检索树的问题时，曾经利用单调性得到
root[i+1,j]≤root[i,j]≤root[i,j-1]（其中root[i,j]表示中序遍历为i..j 的子树取道最优值时的根节点），这样把root[i,j]的取值范围进行了一下限制，使得在一个阶段内，所有需要考虑的决策不超过2n 个，于是总的复杂度就被降低到O(n 2)。那么我们是否可以也用类似的办法取优化这道题呢？这里不对优化的可行性作出讨论，不过可以肯定的是
root[i+1,j]≤root[i,j]≤root[i,j-1]
是不一定成立的，一个显然的反例就是当d[1]=d[2]=d[3]=1时，
root[1,2]=1或2，root[2,3]=2或3，root[1,3]=1或3，那么无论root[1,3]是1还是3不等式都总将有一边不成立。那么能不能跳过这种边界情况，寻找新的优化方案，仍然是一个值得探讨的问题。
另外我们跳出固定算法的思维框架，想到最优二分检索树也是可以用贪心思想来解决的，那么这道题能否类似地解决呢？这也应该是这道题的一个研究方向，不过总的来说，研究这道题的时候应该遵循题目本身的特点，不可生搬硬套。
题四：传染病控制（Epidemic）
【问题描述】
近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国
大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
研究表明，这种传染病的传播具有两种很特殊的性质；
第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不
得病，或者是XY之间的传播途径被切断，则X就不会得病。
第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序。
【输入格式】
输入格式的第一行是两个整数n（1≤n≤300）和p。接下来p行，每一行有两个整数i 和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点1是已经被感染的患者。
【输出格式】
只有一行，输出总共被感染的人数。
【输入样例】
7 6
1 2
1 3
2 4
2 5
3 6
3 7
【输出样例】
3
【问题分析】
由于在对这道题进行了一段时间的思考以后，发现很难找到一个多项式级别的算法，因此猜想此题可能是一道NP完全问题，我们先来给出复杂性理论的一些定义：
P（Polynomial）问题：存在解决该问题的多项式级别的确定性算法的问题。
NP(Nondeterministic Polynomial)问题：如果对于该问题，对于每一个解答，存在多项式级别的确定性算法判断该解答是否可行，就称该问题是NP问题。例如，哈密尔顿环游问题就是一个NP问题。
NP完全问题：能够等价转化为哈密尔顿环游问题的问题。这样我们可以知道所有的NP完全问题都是可以等价转化的。
关于NP完全问题是否存在一个多项式级别的确定性算法，至今仍是一个悬而未决的问题。因此对于这道题而言，跳出对这样算法的追求，寻找一个近似算法，或者寻找一个时间效率说得过去的搜索算法不失为一个好的对应策略。
解决问题的关键：理解问题本质, 找出可行的近似算法
可行算法：
我们首先来通过对样例数据和其它的一些比较简单的数据进行一些观察，很容易得到一种贪心的算法，对这种算法可做如下的描述：
1．我们用Sum(i)表示以i为根节点的子树上的节点总数。那么我们每次砍掉当前层中还未砍掉的节点里面使得Sum(i)取到最大值的那个节点；
2．重复第1步直到当前层中的节点为空。
这样在我们构造的许多数据中，这个算法似乎总是能得到正确的结果。那么这样的算法是否就令人满意呢？在算法的正确性没有被彻底证明之前，尝试去找一些反例总不失为一个好的习惯，比如说对于这个贪心算法我们就能找到如下一个反例。
在这个图里面如果用上面贪心的法则来进
行的话，那么最终被截掉的边我们用粗线表示，
可以看到在这种策略的选择下我们最终将保留
3个节点，而用虚线表示的最优策略将使我们最
终只剩下2个节点。
既然反例已经被找到，我们就应该意识到
是算法本身的缺陷造成了这种反例的存在。那
么我们该如何弥补算法的这一缺陷呢？应该看
到，贪心算法对于这道题的大多数数据都能得
到比较不错的结果，但是贪心法本身的固有缺
陷使得一旦作出了错误的决策，就没有希望得
到正确的解。这样我们便容易想到能否通过尝
试做出多次看起来正确的决策并在它们中间选
取一个最优的来进行我们的近似算法。由此思路孕育而生的就是在贪心选择中引入随机化因素而得来随机化算法，这个算法可被描述如下：
1．我们通过随机函数来选择即将被砍掉的节点，可以通过设置权值来使得算法更大可能地去选择“看起来最优”的决策；
2．重复第1步直到当前层中的节点为空；
3．对前两步执行多次并选取所得到的最优结果。
这个算法被设计出来以后，就很难在构造出能使这个算法失败的数据了，因此在考场上能够设计出来这个算法就已经很令人满意了，而事实也恰恰如此（这个算法可以通过所有的测试数据）。
另外，我们在构造数据的过程中也发现，似乎很难构造出不确保是多项式级别的搜索算法低效的数据，因此比赛时选择搜索算法也不失为不错的策略，这里对该算法就不在作赘述。
问题扩展：
在尝试进一步研究这个问题的时候，我们遇到了以下的困难：
1．能否找到一个多项式算法或者证明此题是NP完全？
2．怎样构造数据, 使得解决此题的近似算法或搜索失败？
3．对于这样的数据, 怎样修改算法, 使得算法可以通过这些特殊的数据？
上面的三个问题制约了对该算法的进一步研究，但是同上一道题目一样，本题仍然是一道值得研究的题目。
三、NOIP2004
题一：津津的储蓄计划
【问题描述】
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。
- 输入文件
输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。
- 输出文件
输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。
- 样例输入1
290/230/280/200/300/170/340/50/90/80/200/60
- 样例输出1
-7
- 样例输入2
290/230/280/200/300/170/330/50/90/80/200/60
- 样例输出2
1580
【问题分析】
这是本次分区联赛当中最简单的题，算法也很简单：模拟法。
每个月把津津手上的钱加上妈妈给的300元，再减去预算，得到当前手中的钱，假如这个钱的值是负数（出现亏损），那么就输出负的月数，接着算出存入的钱，并且将手中的钱减去。如此往复，直到最后按要求输出结果或者中间已经停止。
可以边读边处理，也可以把每个月的收入都读入然后处理。模拟时只需要记录当钱手中的钱和已存入的钱即可。时间、空间复杂度均为常数。
处理这种题目关键是要细心，不要丢了冤枉分。
题二：合并果子
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
- 输入文件
输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
- 输出文件
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
- 样例输入
3
1 2 9
- 样例输出
15
- 数据规模
对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。
【问题分析】
首先注意到一个很关键的地方，就是每次合并的两堆果子不一定相邻。也就是说这个问题与经典的石子归并是不同的。
把初始时的每堆果子看成一个叶子节点，重量为w[i]，则合并后的堆相当于一棵子树。合并两棵子树相当于把这两棵子树中所有的叶子节点的深度d[i]增加1，而最后的费用就是∑(wi + di)。这时我们突然发现，这就是经典的Huffman树构造问题。
构造Huffman树问题当中需要执行的操作是：
(1)从一个集合中取出最小的数；
(2)插入一个数字到这个集合中。
支持动态GetMin和Insert操作的数据结构，我们可以选择用堆来实现。堆是一种完全二叉树，且保证根结点的值小于等于其子孙结点。具体实现方法可以参见本书的数据结构部分。
于是整体算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。
但是，有没有更好的方法呢？很显然，每次合并两个结点以后，得到的大小是严格递增的。于是我们可以维护两个队列QA与QB，QA记录叶子结点的权值w[i]，QB记录子树的权值。这样，每次就一定是在QA和QB的队首取数，在QA和QB的队尾删除。这样时间复杂度就降到了O(n)。因为a[i] <= 20000，所以排序也可以用计数排序在O(n)时间内实现，整体时间复杂度仅为O(n)。
题三：合唱队形
【问题描述】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
- 输入文件
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
- 输出文件
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
- 样例输入
8
186 186 150 200 160 130 197 220
- 样例输出
4
- 数据规模
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
【问题分析】
假设已经确定了最高的人的位置P，那么问题就转化为求1-P的最长上升子序列与P-N的最长下降子序列。设left[i]表示从左边开始到i结束的最长上升子序列长度，right[i]表示从右边开始到i结束的最长上升子序列长度。则答案即为N-max{left[i]+right[i]-1}，其中1<=i<=N并且
left[i],right[i]>=2，这是因为最高的人不能在合唱队形的最左边或者最右边。
现在关键的问题转化为求left[i]与right[i]。由于两者的意义类似，只是方向不同，因此只介绍left[i]的求法。
可以用动态规划求left[i]，方程为left[i]=max{left[j]}+1，其中0<=j<=i-1且Ti>Tj。边界条件为left[0]=0。这样的复杂度为O(N^2)，在时限内出解绰绰有余。但事实上本题还有O(NlogN)的算法，请参见本书的动态规划部分。
题四：虫食算
【问题分析】
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。
BADC
+ CRDA
DCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，
- 输入文件
输入文件alpha.in包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。
- 输出文件
输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。
- 样例输入
5
ABCED
BDACE
EBBAA
- 样例输出
1 0 3 4 2
- 数据规模