NOIP2007提高组试题与解析.doc

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个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。【输入输出样例】count.in 8242451002100count.out2 34 25 1100 2【限制】??? 40%的数据满足：1=n=1000??? 80%的数据满足：1=n=50000??? 100%的数据满足：1=n=200000，每个数均不超过1500 000 000（1.5*109）【解题思想1】显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。【解题思想2】维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息。之后中序遍历即可。 看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn)【实际数据规模】挺小的，而且也没有传说中的卡Qsort的数据，全部都很温柔。【分 析】这个题目实在不能说是一道TG组的好题。实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。话说回来，此题是送分 题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。在考试的时候，要相信有简单的题目，要相信有直接的算法。在我的身边就有几个同学因为 这个题目与一等失之交臂，这是最可惜的事情。var a:array[1..200001] of longint;i,j,k,m,n:longint;procedure qsort(s,t:longint);var i,j,mid,temp:longint;begini:=s;j:=t;mid:=a[(s+t) div 2];while i=j dobegin?? while a[i]mid do inc(i);?? while a[j]mid do dec(j);?? if i=j then??? begin???? temp:=a[i];a[i]:=a[j];a[j]:=temp;???? inc(i);dec(j);??? end;end;if it then qsort(i,t);if js then qsort(s,j);end;beginreadln(n);for i:=1 to n do readln(a[i]);qsort(1,n);a[n+1]:=maxlongint;k:=1;for i:=2 to n+1 doif a[i]a[i-1] then?? begin writeln(a[i-1], ,k); k:=1;endelse k:=k+1;end. ?????????????????????????????????????????????????? 2.字符串的展开（expand.pas/c/cpp）【问题描述】??? 在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就 把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过 增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：??? (1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。??? (2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。??? (3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。??? (4) 参数p3：是否改为逆序：p3=1表示维持原来