第一题：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的正整数 


2007NOIP普及复赛试题

1.奖学金

 

(scholar.pas/c/cpp)

 

【问题描述】 

 

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。 

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是: 

7 279

 

5 279 

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是: 

5 279 

 

7 279 

则按输出错误处理，不能得分。 

 

【输入】 

 

输入文件scholar.in包含n+1行: 

 

第1行为一个正整数n，表示该校参加评选的学生人数。 

 

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。 

 

所给的数据都是正确的，不必检验。 

 

【输出】 

 

输出文件scholar.out共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。 

 

 



 

全国信息学奥林匹克联赛(NOIP2007)复赛                                     普及组 

 

 



【输入输出样例1】 

 

scholar.in     
 scholar.out
 
6       

90 67 80   

87 66 91      

78 89 91       

88 99 77       

67 89 64       

78 89 98       

 
 6 265

4 264

3 258

2 244

1 237
 

 

【输入输出样例2】 

 

scholar. in
 scholar. out
 
8          

80 89 89       

88 98 78      

90 67 80      

87 66 91       

78 89 91     

88 99 77     

67 89 64     

78 89 98     

 
 8 265

2 264

6 264

1 258

5 258
 

 

【限制】 

 

50%的数据满足:各学生的总成绩各不相同 100%的数据满足: 6<=n<=300 

 



 

全国信息学奥林匹克联赛(NOIP2007)复赛                                普及组 

 



2.纪念品分组

 

(group.pas/c/cpp)

 

【题目描述】 

 

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 

 

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。 

 

【输入】 

 

输入文件group.in包含n+2行: 

 

第1行包括一个整数w，为每组纪念品价格之和的上眼= 第2行为一个整数n，表示购来的纪念品的总件数G 

 

第3-n+2行每行包含一个正整数Pi (5 <= Pi <= w3)w表示所对应纪念品的价格。 

   

【输出】 

 

输出文件group.out仅→行，包含一个整数， ep最少的分组数目合 

 

【输入输出样例】 

 

group.in
 group. out   
 
100

9     

90     

20     

20     

30     

50     

60     

70     

80     

90     

 
 6
 

 

【限制】 

 

50%的数据满足: 1 <=n <= 15 

 

100%的数据满足: 1 <= n <= 30000， 80 <= W <= 200 


全国信息学奥林匹克联赛(NOIP2007)复赛                               普及组 

 



3. 守望者的逃离

 

(escape.pas/c/cpp)

 

【问题描述】 

恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，刀上的所有人都会遇难：守望者的跑步速度，为17m/s， 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 

 

【输入】 

 

输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。 

 

【输出】 

 

输出文件escape.out包含两行: 

   

第1行为字符串"Yes"或"No" (区分大小写)，即守望者是否能逃离荒岛。 

 

第2行包含一个整数，第一行为"Yes" (区分大小写）时表示守望着逃离荒岛的最短时间 

 

第一行为"No" (区分大小写) 时表示守望者能走的最远距离。 

 

【输入输出样例1】 

escape.in  
 escape.out
 
39 200 4
 No

197
 

 

【输入输出样例2】 

escape.in  
 escape.out
 
36 255 10  
 Yes

6
 

 

【限制】 

 

30%的数据满足: 1 <= T<= 10， 1 <=S<= 100 

 

50%的数据满足: 1 <= T <= 1000， 1 <= S <= 10000

 

100%的数据满足: 1 <= T <= 300000， 0 <= M<=1000  1 <=S <= 10^8 

 



 

全国信息学奥林匹克联赛(NOIP2007)复赛                                普及组 

 



4.HanOI双塔问题

 

hanOI.pas/c/cpp

 

【问题描述】 

 

给定A,B,c三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到c柱上，在移动过程中可放在B柱上暂存。要求: 

 


(1)每次只能移动一个圆盘；

 

(2) A、B、c三根细柱上的圆盘都要保持上小下大的顺序；

 

任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 

 

【输入】 

 

输入文件hanOI.in为一个正整数n，表示在A柱上放有2n个圆盘。 

 

【输出】 

 

输出文件hanOI.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。 

 

【输入输出样例1】 

hanOI.in
 hanOI.out
 
1
 2
 

 

【输入输出样例2】 

hanOI.in
 hanOI.out
 
2
 6
 

 

【限制】 

对于50%的数据， 1<=n<=25 

对于100% 数据， 1<=n<=200 

 

【提示】 

 

设法建立An与An-1的递推关系式。