NOIP2007改进小组半决赛试题

输入一个数字n (n

样本输入:

八

2

四

2

四

五

100

2

100

样本输出:

2 3

4 2

5 1

100 2

第二个问题:扩展字符串的扩展

我们可以用减号来缩写连续的字母或数字，这样字符串a-dha3-68就可以展开成abcdha34568。

输入三个参数p1、p2、p3，然后输入一个仅由数字、小写字母和减号组成的字符串(长度不超过100)。请根据参数扩展该字符串。

每个参数的含义如下:

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

参数p 1 = 2->；所有填好的字母都用大写；

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

参数p2 = k-& gt；连续写入相同的填充字符k次；

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

参数P3 = 2-& gt；反向填充。

另外，如果减号两边的字符是数字和字母，或者减号右边的ASCII码没有左边的大，就保持不变。

样本输入1:

1 2 1

abcs-w1234-9s-4zz

样本输出1:

abcsttuuvw 1234556677889s-4zz

样本输入2:

2 3 2

答-答-答

样本输出2:

aCCCBBBd-d

样本输入3:

3 4 2

di-jkstra2-6

样本输出3:

dijkstra2************6

问题3:游戏矩阵访问游戏。

一个N行M列的矩阵，每次需要按要求取出N个数，M次正好取出所有的个数。每拿出一个数字，就会得到一个分数。求最高分。

一次取号要求:每行恰好取一个号，只能取其余号中最左边或最右边位置的号。

每取一个数的分数:取的数的值乘以2 I，其中I表示这是第I轮取数。

矩阵中的数字是不超过100和1的自然数

样本输入:

2 3

1 2 3

3 4 2

样本输出:

82

样本描述:

1*2+2*2 + 2*4+3*4 + 3*8+4*8 = 82

问题4:核心树网络的核心。

树上任意两点之间都有唯一的路径。从树上的一个点到路径的距离被定义为从该点到路径上所有点的最小路径长度。将树中路径的偏心率定义为从所有其他点到该路径的最大距离。将树的直径定义为树的最长路径(可能不是唯一的)。给定一棵有n个节点的无根树，请在某个直径上找一条长度小于s的路(可能退化为一个点)，使其偏心度最小。请输出这个最小偏心率的值。

题目已经告诉你以下定理:一棵树所有直径的中点必重合(这个中点可能在一条边上)。其实这个结论很明显，因为如果中点不重合，可以找到更长的路。

5 & lt= n & lt=300，& lt= s & lt=1000，边权是不超过1000的正整数。