nbhkdz.com冰点文库

NOIP普及组解题报告

时间:2014-03-01


NOIP2006 复赛普及组解题报告

【第一题解题思想】 :这道题属于容易题,但是题目难度大于 NOIP2005 和 2004 普及组第一题, 和去年第二题难度相当后者略低一些。 解法 1:我们可以用先去掉重复(读入第 i 个数,和他前面的 i-1 个数比较) ,然后用简单排序 和冒泡排序排序,最后输出结果。 解法 2:运用插入排序(略加修改) ,边排序边除

掉重复。 解法 3:直接排序,不去掉重复,计算出不重复的元素个数,输出不重复的元素即可。如果用 数组 A 存储这些随机数,对于 2 到 N 个元素需要比较 A 是否等于 A[i-1]。 解法 4:开一个 1 到 1000 初值均为假的布尔数组 A。用整型变量 X 读入 N 个随机数,赋 A[X] 的值为真。统计数组中值为真的元素个数即 M,从 i 从 1 到 1000 输出 A 值为真的 i。这种方法 可以算作哈希表的简单应用。 解法 5:很多人想到排序,效率大概是 O(n^2)吧,其实还有个更简单的方法。用一个 1 到 1000 的数组储存每个数的出现情况,t 每出现一次,a[t]=a[t]+1,而且,同时操作 if(a[t]>1) 则 总数=总数-1。然后从 1 到 1000 的循环,如果 a≠0,输出,这样就根本不用排序了。大概这个 应该是最优算法吧。O(n)的效率。 program random(input,output); var a:array[1..1000] of integer; / ’a 是记录数组,相当于数轴,与数一一对应,temp

是临时存储数据,n 和题目一样,记录不相同的数的个数’ /
i,m,temp,n:integer; begin assign(input,'d:\data\random.in'); reset(input); assign(output,'d:\data\random.out'); rewrite(output); read(n); readln; fillchar(a,sizeof(a),0); /*初始化数组为 0,pascal 有 fillchar*/ m:=n; for i:=1 to n do begin read(temp); a[temp]:=a[temp]+1; /*记录是哪个数*/ if a[temp]>1 then dec(m); end; write(m);writeln; for i:=1 to 1000 do

if a>0 then / *如果 a 不为 0。这样就根本不用排序*/ write(i,' '); end.

【第二题解题思想】 :
这是一道典型的动态规划题,和 NOIP2005 第 3 题“菜药”很相似。我们用 f(i,x)表示前 i 件 物 品 总 钱 数 不 超 过 x 的 物 品 的 价 格 与重 要 度 乘 积 的 总 合的 最 大 值 , f(0,x)=0,f(i,0)=0, f(i,x)=max( f(i-1,x),f(i-1,x-v)+v*w ) 。v 表示第 i 件物品的 价值,w 表示第 i 件商品的重要度。用一个一维数组就可以存储 f,但是 x 要从 k 向 1 变化。

【第三题解题思路】 :
这道题难度不大也用不到过多的编程知识, 解题的关键在于读懂题意, 找到 Jam 数的规律。 对于给定的 Jam 数字, 我们从最后一位到第一位找看第一个可以更换为可选字母表中他后面字 母 x 的 i 位, 把 i 位字母换成 x, 把可选字母表 x 后面的 w-i 个字母依次填充到 Jam 数字的 i+1 到 w 位,这样就找到了原 Jam 数的下一个数。如果到第一位都不能换为他后面的字母,即这个 Jam 数没有后继。

【第四题解题思路】 :
这道题目和 3 题类似,解决关键是找到规律。把序列的每一项用数组 S[1..2010]存储,S[1]= K0=1;以后加入 k 的 x(x=1,2,3,…)次方后,依次加入这项与第一项到他前面一项的和组成 的项,直到总项数等于 N 或者超过 N 一些时停止加入项,输出 S[N]即可。 另外这个题好像是 2005NOIP 训练题中的一个类似题目。


NOIP2008普及组复赛试题与解题报告

NOIP 2008 普及组解题报告一、ISBN 号码(isbn.pas/c/cpp) 【问题描述】 每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别...

NOIP1997普及组解题报告

NOI 分区联赛 - 1997 年第四届初中组 试题解析注意:解析和源程序均为 OIBH 站长刘汝佳所写,疏漏在所难免 注意: 站长刘汝佳所写, 方格的棋盘(l<=N<=100,1<...

noip2005普及组解题报告

noip2005普及组解题报告_建筑/土木_工程科技_专业资料。noip2005普及组解题报告noip2005 普及组解题报告 陶陶摘苹果 【文件名】: apple.pas/c/cpp 【问题描述】 ...

NOIP2010普及组第四题《三国游戏》解题报告

NOIP2010 普及组第四题 三国游戏 解题报告 (sanguo.pas/c/cpp) 【问题描述】 小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。 在游戏中, 小涵和...

noip2015普及组解题报告

noip2015普及组解题报告_学科竞赛_初中教育_教育专区。noip2015普及组解题报告 NOIP2015 普及组(Junior) 解题报告 1. 金币 (coin.cpp/c/pas) 国王将金币作为工资...

NOIP2011普及组解题报告

NOIP2011普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2011 普及组解题报告一、数字反转 没得满分只能说明一个问题,你的程序写的太少了。 program reverse; ...

NOIP2012普及组复赛解题报告

NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区。第一题:筛选法求素数。 var a:array[1..50000]of boolean; x,y,i,j,n:longint; begin assign(in...

2008年NOIP普及组解题报告

2008 年 NOIP 普及组解题报告 王祺磊 (本份解题报告以 C++为参考程序) 一、ISBN 号码 一道让人很长知识的题目,但是题目所蕴含的解题方法,却十分直接。你甚至可...

NOIP2007普及组解题报告

NOIP 2007 普及组解题报告 1、 奖学金 (scholar.pas/c/cpp) 、 【问题描述】 问题描述】 某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前 5...

NOIP2013复赛模拟8解题报告

NOIP2013复赛模拟8解题报告_学科竞赛_高中教育_教育专区。NOIP2008 模拟试题 1(4P24)普及组 1.报数(read.pas/c/cpp) OIP2010 模拟试题 4(4P36) [题目描述]...