大二极限编程社团纳新

组题人：徐苏洋
考试时间：9月29日 18：30 - 10月2日 22：00 中抽取任意4小时答题
请大家写程序时打开录屏软件 EV
10月2日23：00 后未提交至钉钉群众默认放弃比赛，成绩为0分
具体分数以最后公布为准，非ACM赛制！！OJ赛制，有部分分！！！

诚信考试诚信考试！！

第一题：American Heritage 美国血统

【问题描述】

农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树。）
显然，这里的树不会有多于 26 个的顶点。这是在样例输入和样例输出中的树的图形表达方式：
在这里插入图片描述

树的中序遍历是按照左子树，根，右子树的顺序访问节点。
树的前序遍历是按照根，左子树，右子树的顺序访问节点。
树的后序遍历是按照左子树，右子树，根的顺序访问节点。

【输入】

第一行：树的中序遍历
第二行：同样的树的前序遍历

【输出】

单独的一行表示该树的后序遍历。

输入样例

ABEDFCHG
CBADEFGH

输出样例

AEFDBHGC

第二题：花匠

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数 h1, h2,… ,hn 。设当一部分花被移走后，剩下的花的高度依次为 g1,g2,…,gm，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的1≤i≤m/2,有 g2i>g2i-1，同时对于所有的 1≤i≤m/2,有 g2i>g2i+1；
条件 B：对于所有的1≤i≤m/2,有 g2i< g2i-1，同时对于所有的 1≤i≤m/2,有 g2i<g2i+1；
注意上面两个条件在 m=1 时同时满足，当 m>1 时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入格式

输入的第一行包含一个整数 n，表示开始时花的株数。
第二行包含 n 个整数，依次为 h1, h2,…,hn ，表示每株花的高度。

输出格式

输出一行，包含一个整数 m，表示最多能留在原地的花的株数。

样例数据 1

输入
5
5 3 2 1 2
输出
3

【样例说明】

有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。

【数据范围】

对于 20% 的数据，n≤10；
对于 30% 的数据，n≤25；
对于 70% 的数据，n≤1000，0≤hi≤1000；
对于100% 的数据，1 ≤n≤ 100,000，0≤hi≤1,000,000，所有的 hi 随机生成，所有随机数服从某区间内的均匀分布。

第三题：黑匣子

题目描述

Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的．而i等于0。这个Black Box要处理一串命令。
命令只有两种：
ADD(x):把x元素放进BlackBox;
GET:i加1，然后输出Blackhox中第i小的数。
记住：第i小的数，就是Black Box里的数的按从小到大的顺序排序后的第i个元素。例如：
我们来演示一下一个有11个命令的命令串。（如下图所示）
在这里插入图片描述
现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多200000个。现在用两个整数数组来表示命令串：

1.A(1)，A(2)，…A(M)：一串将要被放进Black Box的元素。每个数都是绝对值不超过2000000000的整数，M$200000。例如上面的例子就是A=(3，1，一4，2，8，-1000，2)。
2.u(1)，u(2)，…u(N)：表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(l，2，6，6)。输入数据不用判错。

输入格式：

第一行，两个整数，M，N。
第二行，M个整数，表示A(l)……A(M)。
第三行，N个整数，表示u(l)…u(N)。

输出格式：

输出Black Box根据命令串所得出的输出串，一个数字一行。

输入输出样例

输入样例#1：
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
输出样例#1：
3
3
1
2

说明

对于30%的数据，M≤10000;
对于50%的数据，M≤100000：
对于100%的数据，M≤200000。

第四题：采药

【问题描述】

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

【输入文件】

输入文件 medic.in 的第一行有两个整数 T（1 <= T <= 1000）和 M（1 <= M <= 100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

【输出文件】

输出文件 medic.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

【样例输入】

70 3
71 100
69 1
1 2

【样例输出】

【数据规模】

对于 30%的数据，M <= 10；对于全部的数据，M <= 100。

第五题：村村通

【问题描述】

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

【输入】

每个输入文件包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 N（N<1000）和道路数目 M；随后的 M行对应 M 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 1到 N 编号。
注意：两个城市间可以有多条道路相通。例如：
3 3
1 2
1 2
2 1
这组数据也是合法的。当 N 为 0时，输入结束。

【输出】

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

输入样例

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

输出样例

1
0
2
998

第六题：零食

题目描述

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱，为此，约翰购置了N(1≤N<2000)份美味的零食来卖给奶牛们，每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性:
· 零食按照1…N编号，它们被排成一列放在一个很长的盒子里.盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个
· 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃，当然，这样约翰就可以把它们卖出更高的价钱。
· 每份零食的初始价值不一定相同.约翰进货时，第i份零食的初始价值为v(1≤vi<1000).
· 第i份零食如果在被买进后的第a天出售，则它的售价是vi * a.
u,对应的是从盒子顶端往下的第;份零食的初始价值，约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱.
第一份零食在买进后的第1天售出，也就是说此时a=1.以后每过一天，a的值就增加1.