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

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提高组解题报告 - NOIP2007 提高组解题报告 1. 统计数字 (count.pas/c/cpp) count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n...
2007noip解题报告.pdf
2007noip解题报告 - 第一题: 开个足够大的数组,把所有数读入,NlogN 的 qsort 排一遍,然后一边统计以便输出。 用 C++内置的 qsort 异常简洁,甚至代码输入量比...
NOIP2007提高组复赛试题解题报告三.doc
NOIP2007提高组复赛试题解题报告三 - 4、【问题描述】 帅帅经常更同学玩
noip2017提高组复赛解题报告.doc
noip2017 提高组复赛解题报告 定期推送帐号信息学新闻...n 是一个表示数据规模的变量,在时间复杂度计算中 ...
NOIP2007提高组题解.doc
NOIP2007提高组解题报告 20页 免费如要投诉违规内容...NOIP2007 提高组题解 1.count 一切直接 nlogn 的算法...这里可以算得答案不超过 30 位 10 进 制数,所以...
NOIP2018 提高组复赛 解题报告.doc
NOIP2018 提高组复赛 解题报告_学科竞赛_高中教育_...每次操作可选择一段区间使其 中的数全部减1,求...然而我们面临的问题不是计算是构造, 我们并不知道...
NOIP2005提高组第一、二题解题报告_图文.ppt
NOIP2005提高组第一、二题解题报告 - NOIP2005提高组第一、二题 解题报告 谁拿了最多奖学金 (scholar.pas/c/cpp) 【问题描述】 某校的惯例是在每学期的...
NOIP2015提高组day1第二题解题报告.doc
NOIP2015提高组day1第题解题报告_学科竞赛_高中...2. 大概需要什么样的算法根据数据规模,我们可以大概...因为除了最后的查找以外,已经没有什么重复计算的地方...
noip2011提高组day2题解转载.txt
第一题 数值计算考察二项式定理 (a*x+b*y)^k展开后 x^n*y^m(n+m=k)...NOIP2011提高组解题报告... 15页 2下载券 Noip 2013 提高组 Day2 ... ...
2008年noip提高组复赛题解.ppt
2008年noip提高组复赛题解_学科竞赛_高中教育_教育...1、 笨小猴(word) 题意简述:给出一个单词,统计...解题思路: 二取方格数很经典的题目了,于是便直接以...
NOIP2008提高组前三题解题报告.doc
[字体:大中小] NOIP2008 提高组前三题解题报告 1...数字的摆法和计算器相同, a,b,c>=0 3、双进程...
2008noip提高组复赛题解.doc
NOIP2008 提高组解题报告石家庄二中 李博杰 1.笨小猴【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数, 输出“...
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 计算系数 【问题描述】 给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(...
2011noip提高组解题报告.pdf
2011noip提高组解题报告 - 第一题很简单,用循环队列可做出。我当初为省时
NOIP2015提高组解题报告.doc
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意...所以从前往后扫一遍 DP 统计一下方案就可以了 70 ...已经 取了 k 个互不重叠的非空子串的方案数,...
Noip 2013 提高组 解题报告.pdf
Noip 2013 提高组 解题报告 --By GreenCloudS Day 1: 第一题:转圈游戏(快速...(先对高度进行基数排序,然后逐行计算区间数,复杂度也是 O(n))(Cpp): #...
NOIP2011提高组解题报告day1.doc
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育...是算法的瓶颈所在,不过对于题中的数据范围已经足够了...2018 Baidu |由 百度云 提供计算服务 | 使用...