当前位置:首页 >> 电脑基础知识 >>

2007年NOIP提高组第一题解题报告统计数字

1.统计数字
(count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1.5*109)。已知不相同的 数 不超过 10000 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输 出统 计结果。 【输入】 输入文件 count.in 包含 n+1 行: 第 1 行是整数 n,表示自然数的个数。 第 2~n+1 行每行一个自然数。 【输出】 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数),按照自然数从小到大 的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。 【输入输出样例】 count.in 8 2 4 2 4 5 100 2 100 【限制】 40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*109) 【主要算法】 1、一道去重排序,本来用基数排序已经足够。但数据范围过大导致超空间,所以可以用快 排先对数列进行排序,形成压缩的作用。 【参考程序】var n,i,q,p,k:longint; a:array[1..200000] of longint; num,s:array[1..10000] of longint; procedure qsort(left,right:longint); var i,j,x,m:longint; 23 42 51 100 2 count.out

begin i:=left;j:=right; m:=a[(left+right)div 2]; repeat while m>a[i] do inc(i); while m<a[j] do dec(j); if j>=i then begin x:=a[i];a[i]:=a[j];a[j]:=x; inc(i);dec(j); end; until i>j; if j>left then qsort(left,j); if i<right then qsort(i,right); end; begin assign(input,'count.in');reset(input); assign(output,'count.out');rewrite(output); readln(n); for i:=1 to n do readln(a[i]); qsort(1,n); // for i:=1 to n do write(a[i],' '); p:=1;q:=2;num[1]:=a[1];k:=1; for i:=1 to 10000 do s[i]:=1; while q<=n do begin if a[p]<>a[q] then begin p:=q;q:=q+1;k:=k+1;num[k]:=a[p];end; while a[p]=a[q] do begin s[k]:=s[k]+1; q:=q+1; end; // write(s[k],' '); end; for i:=1 to k do writeln(num[i],' ',s[i]); close(input); close(output); end.


相关文章:
2007年NOIP提高组第一题解题报告统计数字.doc
2007年NOIP提高组第一题解题报告统计数字 - 1.统计数字 (count.
NOIP2007提高组解题报告.doc
NOIP2007提高组解题报告 - NOIP2007 提高组解题报告 1. 统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均不超过 150...
2007年NOIP提高组第二题解题报告字符串的展开.doc
2007年NOIP提高组第题解题报告字符串的展开 - 2.字符串的展开 (ex
NOIP2007提高组复赛试题解题报告三.doc
NOIP2007提高组复赛试题解题报告三 - 4、【问题描述】 帅帅经常更同学玩
noip2017提高组复赛解题报告.doc
noip2017 提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息学专业 ...第一行包含一个整数 T, 代表数据组 数。接下来 T 组数据,对于每组数据:第...
NOIP2018提高组解题报告.doc
NOIP2018提高组解题报告_学科竞赛_高中教育_教育专区...的范畴,且在此题数据范围下没有明显优势,在此 ...一个很自然的想法是, 处进行统计。如果给定某点 ...
NOIP2018 提高组 解题报告.doc
NOIP2018 提高组 解题报告_学科竞赛_高中教育_教育...这部分 内容超出了 NOIP 的范畴,且在此题数据范围...一个很自然的想法是, 处进行统计。如果给定某点 ...
NOIP2018 提高组复赛 解题报告.doc
NOIP2018 提高组复赛 解题报告_学科竞赛_高中教育_...这部分 内容超出了NOIP的范畴,且在此题数据范围下...很自然的想法是, 对于每条路径,我们在其处进行统计...
NOIP2007提高组题解.doc
NOIP2007提高组解题报告 20页 免费如要投诉违规内容...NOIP2007 提高组题解 1.count 一切直接 nlogn 的算法...Hash 表中,读完以后再取出 Hash 表内 的数据排序...
NOIP2005提高组第一、二题解题报告_图文.ppt
NOIP2005提高组第一、二题解题报告 - NOIP2005提高组第一、二题 解题报告 谁拿了最多奖学金 (scholar.pas/c/cpp) 【问题描述】 某校的惯例是在每学期的...
2007NOIP普及组奖学金解题报告.doc
2007NOIP普及组奖学金解题报告 - 1.奖学金 . (scholar.pa
NOIP2000-2009提高组解题报告.doc
收集整理NOIP2000-2009提高组解题报告收集整理NOIP2000-2009提高组解题报告隐藏>> NOI 分区联赛 - 2000 年第六届提高组试题解析注意:解析和源程序均为 OIBH 站长刘...
NOIP2008提高组前三题解题报告.doc
NOIP2008 提高组前三题解题报告 [日期:2008-11-18...NOIP2008 提高组复赛 解题思路 1、字符串中统计字母...数字的摆法和计算器相同, a,b,c>=0 3、双进程...
NOIP2009提高组解题报告.doc
NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>>...取值范围(若为空则说明无解), 并按照乘法原理统计...但是还有很多数据是有环的, 也就是对于有些点对(...
2008noip提高组复赛题解.doc
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组解题报告石家庄二中 李博杰 1.笨小猴【问题描述】 输入一个由小写字母构成的字符串,统计出现...
Noip 2013 提高组 解题报告.pdf
Noip 2013 提高组 解题报告 --By GreenCloudS Day 1: 第一题:转圈游戏(快速幂)根据题目, 答案明显是(x+10^km) mod n, 化简一下, 就成了(x + m (10...
NOIP2006提高组复赛解题报告.doc
NOIP2006提高组复赛解题报告_理学_高等教育_教育专区。noip历届复赛试
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2 - 计算系数 【问题描述】 给定一个多项
NOIP2008提高组复赛题解___best_图文.ppt
NOIP2008提高组复赛题解___best_学科竞赛_初中教育...? 总结: 这也是比较水的一道题,数据规模较小,...NOIP2008提高组解题报告 13页 1下载券 复赛NOIP2010...
noip2009提高组解题报告(C语言).doc
noip2009提高组解题报告(C语言)_IT/计算机_专业资料...第一行为一个正整数 n,表示有 n 组输入数据。接...的道路,双向通行的道路在统计条数时也计为 1 条...