长郡NOIp模拟试题二
题目名称 音乐旋律的比对 彩色创作 逆序统计 王位继承
程序文件 music.exe color.exe count.exe kingdom.exe
输入文件 music.in color.in count.in kingdom.in
输出文件 music.out color.out count.out kingdom.out
时间限制 1s 1s 2s 1s
空间限制 128MB 128MB 128MB 128MB
题目分值 100 100 100 100
音乐旋律的比对
问题描述：
音乐的旋律是由音阶与拍子所组成。如果我们修改音乐的简谱记法，将音阶的Do，升Do,Re,升Re,Mi,Fa，升Fa,Sol，升Sol,La，升La,Si分别如下列对照，以1，2，…，12的数字依序表示这些音阶。
表1
因此，音乐的旋律可以表示成序列。序列中每个元素包括表示音阶的数字与拍子。例如，如图1的歌谱是歌曲小蜜蜂。前两小节可以表示成序列<8,1>，<5,1>,<5,2>,<6,1>,<3,1>,<3,2>.。如果我们将这序列以几何折线表示，就可以表示成如图2中单线的折线。而图2中另一条双线的折线是序列<10,2>,<8,1>,<4,1>,<2,4>。因此，两条相同长度的旋律之间，可以其对应之几何折线间的面积总和来衡量其相异度。例如，图2的灰阶区域面积总和18，即是此两条旋律的相异度。
但是由于旋律可以升降key，换句话说，我们可以将整几何折线作上下垂直的位移。例如，我们可以如图3所示，将双线的这条直线往上位移一个单位（音阶上的一个半音）。此时两条旋律之间的相异度，也就是对应折线面积的总和就减少为16。
给定两条旋律，而且此两条旋律可任意作升降key，请设计程序计算此两条旋律的最小相异度。
输入说明：
两行序列，代表两条总拍数相同、由<音阶，拍子>组成的旋律序列。
每对<音阶，拍子>之间以逗号隔开。
输出说明：
此两条旋律的最小相异度。
输入范例：
<8,1>,<5,1>,<5,2>,<6,1>,<3,1>,<3,2>
<10,2>,<8,1>,<4,1>,<2,4>
输出范例：
16
数据约定：
总拍数最多1000个；
对于50%的数据，每个旋律音阶不超过100，长度不超过10；
对于100%的数据，每个旋律音阶不超过100000，长度不超过100000。
彩色创作
问题描述：
某数位艺术创作课程教授学生以丰富的色彩及简单的几何形状进行创作。假设所使用的几何形状限定在矩形，且每一个矩形的颜色都不一样。当不同的色彩叠合在一起时（相邻不算叠合），会出现不同的新颜色（假设新颜色不会重复）。请依照输入的矩形位置及大小，找出一个作品中共有几种不同的颜色（不含底色）。举例而言，下列4个矩形共构成了8种不同的颜色。
输入说明：
第一行为两个整数N和M，代表输入的矩形的个数和矩形颜色个数。
第一行之后的每一行中，有五个以空白分隔的整数，代表每一个矩形的左下角顶点、右上角顶点的座标以及矩形颜色（x1 y1 x2 y2 c）。（所有的坐标数值都是在0与10000之间的整数）
输出说明：
一个正整数，代表此作品中共有几种不同的颜色。
输入范例：
4 4
0 70 30 110 1
30 60 75 110 2
50 40 90 80 3
65 20 80 120 4
输出范例：
8
数据约定：
对于20%的数据，N<=10，M<=5，坐标范围不超过30；
对于50%的数据，N<=30，M<=20，坐标范围不超过500；
对于100%的数据，N<=100，M<=30，坐标范围不超过100000。
逆序统计
问题描述：
我们说(i,j)是a1,a2,…,aN 的一个逆序对当且仅当i<j 且ai>aj。例如2,4,1,3,5 的逆序对有３个，分别为（1,3），（2,3），（2,4）。现在已知N 和K，求1..N 的所有特定排列，这些排列的逆序对的数量恰好为K。输出这些特定排列的数量。
例如N=5，K=3 的时候，满足条件的排列有15 个，他们是
1,2,5,4,3
1,3,4,5,2
1,3,5,2,4
1,4,2,5,3
1,4,3,2,5
1,5,2,3,4
2,1,4,5,3
2,1,5,3,4
2,3,1,5,4
2,3,4,1,5
2,4,1,3,5
3,1,2,5,4
3,1,4,2,5
3,2,1,4,5
4,1,2,3,5
输入格式：
从文件COUNT.IN 输入。输入第一行有两个整数N和K。
输出格式：
将1..N 的逆序对数量为K 的特定排列的数量输出到文件COUNT.OUT。为了避免高精度计算，请将结果mod 10000 以后再输出！
样例输入：
5 3
样例输出：
15
数据约定：
对于50%的数据，N<=50且0<=K<=N(N-1)/2；
对于100%的数据，N<=100且0<=K<=N(N-1)/2。
王位继承
问题描述：
某王国其王位继承的规则如下：
（1） 此国家重男轻女，只有皇室成员中的男性才有继承权。
（2） 若国王退位或去世，此时王位由国王在世的儿子继承，年纪较大的优先继承。
（3） 若国王退位或去世时，国王没有在世的儿子，此时王位由国王的弟弟继承，年纪较大的优先继承。
（4） 若国王退位或去世时，没有在世的儿子与弟弟，此时王位国王在世的叔叔继承，年纪较大的优先继承。（所谓叔叔是指父亲的弟弟）
（5） 若国王退位或去世时，没有在世的儿子、弟弟与叔叔，此时王位由国王在世的叔公继承，年纪较大的优先继承。（所谓叔公是指祖父的弟弟）
我们以下面这个家族树（familytree）为例来说明上述规则（假设不在树上的人皆已去世，不需要列入考虑）。如果目前的国王是Charles，根据上述规则，当Charles退位或去世时，可能继位者的继承优先顺序依序为William、Edward、Adam、Benjamin、Peter、Chris与Bill。其中Adam排在William与Edward之后表示当现任国王Charles退位或去世时，如果William与Edward也都已经去世，Adam便可以继承王位。同样考虑下面这个家族树，如果目前的国王是Peter，当Peter退位或去世时，继位者的优先顺位则为Allen、Chris与Bill.
请写一个程序，依据输入的一棵家族树与现任国王名称，将此家族树中未来可能继位者依继承优先顺位列出。所输入的家族树是一棵以现任国王或其某一位祖先为树根的家族树，树中的成员都是男性，而且必定包括现任国王。
输入说明：
第一行是现任国王的名字。第二行之后，每一行是成对的父子名字，中间以一个空格隔开。若有两对名字而其父亲名字相同，先出现者，其年纪大于后出现者。例如：
Tom
John Tom
Tom Chris
John Bill
代表Tom是现任国王。Tom是Chris的父亲。John是Tom的父亲，也是Bill的父亲。Tom的年纪比Bill大。
输出说明：
王位继承者的优先顺位，由在位者、第一顺位者、第二顺位者、……之顺序，一行一行列出。如果无人能继承王位就不输出。
输入范例：
Charles
Peter Allen
Charles William
George Tom
Charles Edward
Tom John
George Peter
Tom Charles
Tom Adam
Chris James
George Chris
Tom Benjamin
输出范例：
Charles
William
Edward
Adam
Benjamin
Peter
Chris
数据约定：
每个名字由长度不大于30个的英文字元（a-z,A-Z）构成，大小写字符视为不同。
家庭成员最多不超过3000名。
