NOIP2006普及组复赛试题(附题解)VIP免费

NOIP2006 普及组解题报告 1 NOIP2006普及组解题报告 Kyd Dong 1.明明的随机数（random.pas/c/cpp） 【问题描述】 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N 个 1 到 1000 之间的随机整数（ N≤ 100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 【输入文件】 输入文件random.in 有2 行，第1 行为1 个正整数，表示所生成的随机数的个数： N 第 2 行有N 个用空格隔开的正整数，为所产生的随机数。 【输出文件】 输出文件random.out 也是2 行，第1 行为1 个正整数M，表示不相同的随机数的个数。第 2 行为M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。 【输入样例】 10 20 40 32 67 40 20 89 300 400 15 【输出样例】 8 15 20 32 40 67 89 300 400 【试题分析】 简单的映射排序，用一个数组s[1..n]用一个数组a[1..1000]来储存状况，先清空数组为0，在读入s[i]之后，先判断a[s[i]]是否为1，是则再读下一个数据，不是则把a[s[i]]赋值为1， m← m+1。 在输出时，则先输出m,再用一个循环输出各个值，即用如下伪代码： For i← 1 to 1000 do { If a[i]=1 Then 打印i； } NOIP2006 普及组解题报告 2 当然还有许多不同的方法，这里只给出代码，供读者自己研究。 【程序代码】 1. program random; {映射排序} var p:array [1..1000] of shortint; {当前数已有标记1} n,l:shortint; a,max,i:integer; input,output:text; begin assign(input,'random.in'); assign(output,'random.out'); reset(input); readln(input,n); fillchar(p,sizeof(p),0); max:=-1;l:=0; {max:存最大数， l:不同数字的个数} for i:=1 to n do begin read(input,a); if p[a]=0 then begin p[a]:=1;l:=l+1 end; {当前数未重复，则标记并记数} if a>max then max:=a; end; rewrite(output); writeln(output,l); for i:=1 to max do if p[i]=1 then write(output,i,' '); close(input); close(output); end 2. program random; { 插入排序} var p:array [1..1000] of boolean; a:array [1..100] of integer; i,n,...