NOIP普及组复赛习题源程序.doc
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《NOIP普及组复赛习题源程序.doc》由用户(刘殿科)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 普及 复赛 习题 源程序
- 资源描述:
-
1、NOIP2011普及组复赛1数字反转(reverse.cpp/c/pas)【问题描述】给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零。(参见样例2)【输入】输入文件名为reverse.in。输入共一行,一个整数N。【输出】输出文件名为reverse.out。输出共1行,一个整数,表示反转后的新数。【输入输出样例1】reverse.inreverse.out123321【输入输出样例2】reverse.inreverse.out-380-83【数据范围】-1,000,000,000N1,000,000
2、,000。【解题】这道题非常简单,可以读字符串处理,也可以读数字来处理,只不过要注意符号问题(以及-0,但测试数据没出)。【法一】字符串处理Vari,l,k:integer;s:string;p:boolean;beginassign(input,reverse.in);reset(input);assign(output,reverse.out);rewrite(output);readln(s);l:=length(s);k:=1;ifs1=-thenbeginwrite(-);k:=2;end;p:=true;fori:=ldowntokdobeginif(p)and(si=0)then
3、continueelsebeginwrite(si);p:=false;end;end;close(input);close(output);end.【法二】数字处理Varf:integer;n,ans:longint;beginassign(input,reverse.in);reset(input);assign(output,reverse.out);rewrite(output);readln(n);ifn0thenbeginf:=-1;n:=-n;endelsef:=1;ans:=0;whilen0dobeginans:=ans*10+nmod10;n:=ndiv10;end;ans
4、:=ans*f;writeln(ans);close(input);close(output);end.2.统计单词数(stat.pas/c/cpp)【问题描述】一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例1),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2)【输入】输入文件名
5、为stat.in,2行。第1行为一个字符串,其中只含字母,表示给定单词;第2行为一个字符串,其中只可能包含字母和空格,表示给定的文章。【输出】输出文件名为stat.out。只有一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从0开始);如果单词在文章中没有出现,则直接输出一个整数-1。【输入输出样例1】stat.instat.outTotobeornottobeisaquestion20【输入输出样例1解释】输出结果表示给定的单词To在文章中出现两次,第一次出现的位置
6、为0。【输入输出样例2】stat.instat.outtoDidtheOttoman Empireloseitspoweratthattime-1【输入输出样例2解释】表示给定的单词to在文章中没有出现,输出整数-1。【数据范围】1单词长度10。1文章长度1,000,000。【解题】这道题也不是很难,programstat;varI,n,p:longint;s,s1:string;c:char;beginassign(input,stat.in);reset(input);assign(output,stat.out);rewrite(output);readln(s);s:=upcase(s
7、);/函数upcase()参数可为char,也可为stringi:=-1;/i统计读入的字符位置,首个字符出现的位置是0s1:=;/s1累加读入的字符n:=0;/n统计出现次数p:=-1;/p标记第一次出现的位置repeatread(c);c:=upcase(c);/统一大小写i:=i+1;ifc=then/遇到空格,匹配是否相同beginifs=s1thenbeginn:=n+1;ifp=-1then/p标记第一次出现的位置,如果p是第一次更改,记录位置p:=i-length(s);end;s1:=;endelses1:=s1+c;/不是空格,继续叠加untileoln(input);ifs
8、1=sthen/处理最后一个单词是否相同的情况beginn:=n+1;ifp=-1thenp:=i-length(s)+1;/最后没有空格end;ifn=0thenwriteln(-1)elsewriteln(n,p);close(input);close(output);end.3.瑞士轮(swiss.cpp/c/pas)【背景】在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛
9、而得名。它可以看作是淘汰赛与循环赛的折衷,既保证了比赛的稳定性,又能使赛程不至于过长。【问题描述】2*N名编号为12N的选手共进行R轮比赛。每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1名和第2名、第3名和第4名、第2K1名和第2K名、第2N1名和第2N名,各进行一场比赛。每场比赛胜者得1分,负者得0分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确定,而是要取决于选手在之前比赛中的表现。现给定每个选手的初
10、始分数及其实力值,试计算在R轮比赛过后,排名第Q的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。【输入】输入文件名为swiss.in。输入的第一行是三个正整数N、R、Q,每两个数之间用一个空格隔开,表示有2*N名选手、R轮比赛,以及我们关心的名次Q。第二行是2*N个非负整数s1,s2,s2N,每两个数之间用一个空格隔开,其中si表示编号为i的选手的初始分数。第三行是2*N个正整数w1,w2,w2N,每两个数之间用一个空格隔开,其中wi表示编号为i的选手的实力值。【输出】输出文件名为swiss.out。输出只有一行,包含一个整数,即R轮比赛结束后,排名第Q的选手
11、的编号。【输入输出样例】swiss.inswiss.out242766710520151【输入输出样例说明】本轮对阵本轮结束后的得分选手编号/初始/7667第1轮7678第2轮7689第3轮8699第4轮96109【数据范围】对于30%的数据,1N100;对于50%的数据,1N10,000;对于100%的数据,1N100,000,1R50,1Q2N,0s1,s2,s2N,1w1,w2,w2N。【解题】题目虽然长,但理解题意后就发现解题的瓶颈在于排序。如果每一轮比赛的结果都进行快速排序,时间复杂度为O(Rlongn),但事实证明这样只能拿60分。如何AC,这需要一个巧算法:分析得知,快速排序实际
展开阅读全文