noip2007提高组试题及解析

《noip2007提高组试题及解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP2007提高组试题及解析1.统计数字（count.pas/c/cpp）【问题描述】   某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入】   输入文件count.in包含n+1行；   第一行是整数n，表示自然数的个数；   第2~n+1每行一个自然数。【输出】   输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整

2、数，分别是自然数和该数出现的次数，其间用一个空格隔开。【输入输出样例】count.in8242451002100count.out2342511002【限制】   40%的数据满足：1<=n<=1000   80%的数据满足：1<=n<=50000   100%的数据满足：1<=n<=200000，每个数均不超过1500000000（1.5*109）【解题思想1】显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。【解题思想2】维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息

3、。之后中序遍历即可。看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn)【实际数据规模】挺小的，而且也没有传说中的卡Qsort的数据，全部都很温柔。【分析】这个题目实在不能说是一道TG组的好题。实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。话说回来，此题是送分题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。在考试的时候，要相信有简单的题目，要相信有直接的算法。在我的身边就有几个同学因为这个题目与一等失之交臂，这是最可惜的事情。vara:array[1..20

4、0001]oflongint;i,j,k,m,n:longint;procedureqsort(s,t:longint);vari,j,mid,temp:longint;begini:=s;j:=t;mid:=a[(s+t)div2];whilei<=jdobegin  whilea[i]middodec(j);  ifi<=jthen   begin    temp:=a[i];a[i]:=a[j];a[j]:=temp;    inc(i);dec(j);   end;end;ifi

5、henqsort(i,t);ifj>sthenqsort(s,j);end;beginreadln(n);fori:=1tondoreadln(a[i]);qsort(1,n);a[n+1]:=maxlongint;k:=1;fori:=2ton+1doifa[i]<>a[i-1]then  beginwriteln(a[i-1],'',k);k:=1;endelsek:=k+1;end.                                                  2.字符串的展开（expand.pas/c/cpp）【问

6、题描述】   在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：   (1)遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。   (2)参

7、数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。   (3)参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。   (4)参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2

8、时，子串“d-h”应扩展为“dggffeeh”。   (5)如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应