Question

NOIP2007提高组复赛试题

拜托拉，谢谢

Answer 1

第一题：count 统计数字
输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。输入数据保证不相同的数不超过10000个。

样例输入：
8
2
4
2
4
5
100
2
100
样例输出：
2 3
4 2
5 1
100 2

第二题：expand 字符串的展开
我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。
输入三个参数p1,p2,p3，再输入一个仅由数字、小写字母和减号组成的字符串（长度不超过100），请按参数展开此字符串
各个参数的意义如下：

参数p1=1 -> 所有填充的字母都写成小写；

参数p1=2 -> 所有填充的字母都写成大写；

参数p1=3 -> 所有填充的字母和数字都用星号代替；

参数p2=k -> 同一个填充字符连续写k遍；

参数p3=1 -> 顺序填充；

参数p3=2 -> 逆序填充。

另外，如果减号两边的字符一个是数字一个是字母，或者减号右边的ASCII码没左边的大，则该处不变

样例输入1：
1 2 1
abcs-w1234-9s-4zz
样例输出1：
abcsttuuvvw1234556677889s-4zz

样例输入2：
2 3 2
a-d-d
样例输出2：
aCCCBBBd-d

样例输入3：
3 4 2
di-jkstra2-6
样例输出3：
dijkstra2************6

第三题：game 矩阵取数游戏
一个n行m列的矩阵，每次你需要按要求取出n个数，m次正好将所有数取完。每取出一个数你都会有一个得分，请求出最终的得分最大是多少。
每一次取数的要求：每一行中恰好取一个数，且只能取剩下的数中最左边或最右边位置上的数
每取一个数的得分：所取数的数值乘以2^i，i表示这是第i轮取数。
矩阵中的数为不超过100的自然数，1<=n,m<=80

样例输入：
2 3
1 2 3
3 4 2
样例输出：
82
样例说明：
1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

第四题：core 树网的核
树上的任两点间都有唯一路径。定义某一点到树上某一路径的距离为该点到路径上所有点的路径长度中的最小值。定义树中某条路径的“偏心距”为所有其它点到此路径的距离的最大值。定义树的直径为树的最长路径（可能不唯一）。给出一个有n个节点的无根树，请找出某个直径上的一段长度不超过s的路径（可能退化为一个点），使它的偏心距最小。请输出这个最小偏心距的值。
题目已经告诉你如下定理：树的所有直径的中点必然重合（这个中点可能在某条边上）。其实这个结论很显然嘛，因为如果中点不重合的话必然可以找到一条更长的路。
5<=n<=300，0<=s<=1000，边权是不超过1000的正整数