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

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...
2007noip解题报告.pdf
2007noip解题报告 - 第一题: 开个足够大的数组,把所有数读入,NlogN 的 qsort 排一遍,然后一边统计以便输出。 用 C++内置的 qsort 异常简洁,甚至代码输入量比...
NOIP2007提高组解题报告.doc
NOIP2007提高组解题报告 - NOIP2007 提高组解题报告 1. 统计数字 (count.pas/c/cpp) count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n...
2007年noip提高组题目解析_图文.ppt
2007年noip提高组题目解析_学科竞赛_高中教育_教育...第一题目 count [题目转述] 给定n个自然数,统计...n,m<=80,操作的数<=1000 [解题思想] 其实看...
2007年NOIP提高组第二题解题报告字符串的展开.doc
2007年NOIP提高组第题解题报告字符串的展开 - 2.字符串的展开 (ex
noip2007题解.doc
noip2007题解_学科竞赛_高中教育_教育专区。解题报告 第一题目 count [题目转述] 给定 n 个自然,统计不同的自然数出现的个数,按照从小到大的顺序输出。其...
NOIP2007提高组复赛试题解题报告三.doc
NOIP2007提高组复赛试题解题报告三 - 4、【问题描述】 帅帅经常更同学玩
NOIP2007提高组题解.doc
NOIP2007提高组解题报告 20页 免费如要投诉违规内容...NOIP2007 提高组题解 1.count 一切直接 nlogn 的算法...这里可以算得答案不超过 30 位 10 进 制数,所以...
NOIP2005提高组第一、二题解题报告_图文.ppt
NOIP2005提高组第一、二题解题报告 - NOIP2005提高组第一、二题 解题报告 谁拿了最多奖学金 (scholar.pas/c/cpp) 【问题描述】 某校的惯例是在每学期的...
NOIP2005提高组第三题解题报告_图文.ppt
NOIP2005提高组第题解题报告_IT/计算机_专业资料...p[i+1]:=next[p[i],2]//如果第二个数的第...{用来计算最小代 价的数组} n,ans,i,j,t,max...
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 计算系数 【问题描述】 给定一个多项式(ax + by)^k,请求出多项式展开后(x^n)*(...
NOIP 2012 提高组 解题报告.pdf
NOIP 2012 提高组 解题报告_调查/报告_表格/模板_...这是 USACO 2007 年某 次月赛的改编题。 我们不...手两个数 的乘积由小到大排序后计算得来,对于乘积...
2011noip提高组解题报告.pdf
2011noip提高组解题报告 - 第一题很简单,用循环队列可做出。我当初为省时
NOIP2008提高组前三题解题报告.doc
[字体:大中小] NOIP2008 提高组前三题解题报告 1...数字的摆法和计算器相同, a,b,c>=0 3、双进程...
2008年noip提高组复赛题解.ppt
2008年noip提高组复赛题解_学科竞赛_高中教育_教育...1、 笨小猴(word) 题意简述:给出一个单词,统计...解题思路: 二取方格数很经典的题目了,于是便直接以...
NOIP提高组04-09第一题.doc
NOIP提高组04-09第一题_政史地_高中教育_教育专区...} } 2007 统计数字 (count.pas/c/cpp) 【问题描述...NOIP2004提高组解题报告 8页 免费 NOIP2009提高组...
NOIP2000-2009提高组解题报告.doc
收集整理NOIP2000-2009提高组解题报告收集整理NOIP2000-2009提高组解题报告隐藏>> NOI 分区联赛 - 2000 年第六届提高组试题解析注意:解析和源程序均为 OIBH 站长刘...
2008noip提高组复赛题解.doc
NOIP2008 提高组解题报告石家庄二中 李博杰 1.笨小猴【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数, 输出“...
NOIP2015提高组解题报告.doc
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意...所以从前往后扫一遍 DP 统计一下方案就可以了 70 ...已经 取了 k 个互不重叠的非空子串的方案数,...
更多相关标签: