tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 电脑基础知识 >>

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.


推荐相关:

NOIP2007提高组试题及解析

NOIP2007 提高组试题及解析 1.统计数字(count.pas/c/cpp) 【问题描述】 某...的数据满足:1<=n<=200000,每个数均不超过 1500 000 000(1.5*109) 【解题...


NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第题解题报告_学科竞赛_高中...2. 大概需要什么样的算法根据数据规模,我们可以大概...因为除了最后的查找以外,已经没有什么重复计算的地方...


NOIP2007提高组复赛试题解题报告

NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料 暂无评价|0人阅读|0次下载|举报文档 NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料。...


2007noip提高组复赛

第1页 共6页 全国信息学奥林匹克联赛(NOIP2007)复赛 提高组 1.统计数字 . (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均...


NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意...所以从前往后扫一遍 DP 统计一下方案就可以了 70 ...已经 取了 k 个互不重叠的非空子串的方案数,...


NOIP2001提高组解题报告1

NOIP2001提高组解题报告1_初三数学_数学_初中教育_教育专区。NOIP2001提高组(...第三题: 第三题:统计单词个数给出一个长度不超过 200 的由小写英文字母组成...


NOIP2007tg解题报告

NOIP 2007 提高组 解题报告 By Redswallow 统计数字 解题思路: 这是个水题 注意不要被不相同的数不超过 10000 个这个条件迷惑去做 hash 不要想太复杂,直接快...


noip2010提高组解题报告

noip2010提高组解题报告_学科竞赛_高中教育_教育专区...输入文件的每行中两个数之间用一个空格隔开。 第 ...可 用计算公式(i-1-a-2b-3c}div 4 得出第四种...


NOIP2011提高组解题报告day2

NOIP2011提高组解题报告day2_理学_高等教育_教育专区...出一个参数 W; 3、对于一个区间[Li,Ri],计算...注意题中 N 数据范围,必须要用 O(n) 的算法得出...


NOIP2008提高组解题报告

NOIP2008 提高组解题报告 提高组解题报告 石家庄二中 李博杰 1.笨小猴 【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com