判断两序列是否为同一个二叉搜索树序列
要求：输入：开始一个数n，(1<=n<=20) 表示有n个序列需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：如果序列相同则输出YES，否则输出NO Sample Input 2
567432 543267 576342 0
Sample Output YES NO
44 会议中心
会议中心 Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。
对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。
例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。
开始日期 结束日期 公司1 4 9 公司2 9 11 公司3 13 19 公司4 10 17
上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1和公司2不能同时租借会议中心，因为他们在第九天重合了。
销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小[1]的候选策略作为最终的策略。
例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。
你的任务是帮助销售主管确定应该将会堂租借给哪些公司。
输入格式
输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每
36
行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司
9
的申请，起始日期为不小于1的整数，终止日期为不大于10的整数。
输出格式
输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，表示最终将会堂租借给哪些公司。
数据规模和约定
对于50%的输入，N≤3000。在所有输入中，N≤200000。
样例输入
4 4 9 9 11 13 19 10 17
样例输出
2 1 3
[1] 字典序指在字典中排列的顺序，如果序列l1是序列l2的前缀，或者对于l1和l2的第一个不同位置j，l1[j] 45 串数 一个A和两个B一共可以组成三种字符串:\给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串. 要求：输入：每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,...,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束. 输出：对于每一组测试数据,输出一个m,表示一共有多少种字符串. Sample Input 2 1 2 3 2 2 2 0 Sample Output 3 90 46 树的应用 要实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。 47 求先序排列 37 问题描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。 输入格式 两行，每行一个字符串，分别表示中序和后序排列 输出格式 一个字符串，表示所求先序排列 样例输入 BADC BDCA 样例输出 ABCD 48 大臣的旅费 问题描述 很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。 为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。 J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。 聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。 J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？ 输入格式 输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数 城市从1开始依次编号，1号城市为首都。 接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条） 每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。 输出格式 输出一个整数，表示大臣J最多花费的路费是多少。 样例输入1 5 1 2 2 1 3 1 2 4 5 2 5 4 样例输出1 135 输出格式 38 大臣J从城市4到城市5要花费135的路费。 49 小朋友排队 问题描述 n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。 请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。 如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。 输入格式 输入的第一行包含一个整数n，表示小朋友的个数。 第二行包含 n 个整数 H1 H2 ? Hn，分别表示每个小朋友的身高。 输出格式 输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。 样例输入 3 3 2 1 样例输出 9 样例说明 首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。 50 接水问题 问题描述 学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m?n’个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。 输入格式 第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、??、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。 39 输出格式 输出只有一行，1 个整数，表示接水所需的总时间。 样例输入 5 3 4 4 1 2 1 样例输出 4 样例输入 8 4 23 71 87 32 70 93 80 76 样例输出 163 输入输出样例 1 说明 第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完 水，4 号同学接替3 号同学开始接水。 第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接 水量为1。 第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接 水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。 第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接 水量为1。1、2、5 号同学接完水，即所有人完成接水。 总接水时间为4 秒。 40