noip普及组赛前冲刺资料#优质参考

1、数组 一、数字数组ex1_1_1.pas级数求和(NOIP2002)【题目描述】已知：Sn=1+1/2+1/3+1/n。显然对于任意一个数K，当n.足够大的时候，Sn大于K。 现给出一个整数K(1K15),要求计算出一个最小的n,使得SnK 【输入】一行,一个整数K【输出】一行,一个整数n【输入样例】1【输出样例】2ex1_1_2.pas陶陶摘苹果(NOIP2005)【题目描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 现在已知10个苹果到地面的高度，以及陶陶

2、把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。【输入】两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。【输出】一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。【输入样例】100 200 150 140 129 134 167 198 200 111110【输出样例】5ex1_1_3.pas数字统计(NO

3、IP2010)【题目描述】请统计某个给定范围L, R的所有整数中，数字2 出现的次数。比如给定范围2, 22，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。【输入】共1 行，为两个正整数L 和R，之间用一个空格隔开。【输出】共1 行，表示数字2 出现的次数。【输入样例】2 22【输出样例】6【输入输出样例2】2 100【输出】20【数据范围】1 L R 10000。ex1_1_4.pas狐狸追兔子【题目描述】围绕着山顶有m个洞(m=100)，一只狐狸和一只兔子住在各自的洞里。

4、狐狸总想吃掉兔子。一天，兔子对狐狸说：“你想吃我有一个条件，先把洞从1m编上号，你从m号洞出发，先到一号洞找我；第二次隔1个洞找我，第三次隔2个洞找我，以后依次类推，次数不限。若能找到我，你就可以饱餐一顿。不过在没有找我以前不能停下来。”狐狸满口答应就开始找了，它从早到晚进了n次洞（1=n=1000），累得昏了过去也没有找到兔子。请问，兔子躲在几号洞里？【输入】一行，洞的个数m，狐狸进洞的次数n【输出】一行，兔子躲的洞的号数，由小到大输出，各数中间用空格隔开【输入样例】10 2【输出样例】2 4 5 6 7 8 9 10ex1_1_5.pas不高兴的津津(NOIP2004)【题目描述】津津上初

5、中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。【输入】包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。【输出】一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1,

6、2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。【输入样例】5 36 27 25 35 40 40 6【输出样例】3ex1_1_6.pas多项式输出(NOIP2009)【题目描述】一元 n 次多项式可用如下的表达式表示：其中，aixi 称为i次项，ai称为i次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。2. 多项式中只包含系数不为0 的项。3. 如果多项式n 次项系数为正，则多项式开头不出现“+”

7、号，如果多项式n 次项系数为负，则多项式以“-”号开头。4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形式为“xb”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。5. 多项式中，多项式的开头、结尾不含多余的空格。【输入】共有2 行第一行 1 个整数，n，表示一元多项式的次数。第二行有 n+1 个整数，其中第i 个整数表示第n-

8、i+1 次项的系数，每两个整数之间用空格隔开。【输出】共1 行，按题目所述格式输出多项式。【输入样例】5100 -1 1 -3 0 10【输出样例】100x5-x4+x3-3x2+10【输入输出样例2】3-50 0 0 1【输出】-50x3+1【数据范围】1 n 100，多项式各次项系数的绝对值均不超过100。二、字符数组定义:String等价于array0.255 of char，其中第0号但有存放的是实际长度。Ansistring长度不限。常用操作Length(st) 求st的长度Copy(st,m,n) 从st的第m个位置开始复制n个字符Delete(st,m,n) 删除st的第m个位置

9、开始的n个字符Val(st,x,code) 将字符串st转化为数字x，若能成功转化，则code=0；若不能，code返回第一个非法字符的位置。注：当st只有一个字符时，code返回的数值不准，建议少用code判断位置。 Str(x,st) 将数字x转化为字符串st将单个字符c转化为数字x： x:=ord(c)-48;将单个数字x转化为字符c： c:=chr(x);将字符串倒序存放在a数组中：A0:=length(st);For i:=1 to a0 do Ai:=ord(sta0-i+1)-48;ex1_2_1.pasISBN号码(NOIP2008)【题目描述】每一本正式出版的图书都有一个IS

10、BN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语音，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔符之后的五位数字代表该书在该出版社的编号；最后一位为识别码。识别吗的计算方法如下：首位数字乘以1加上次位数字乘以2以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN码0-670-82

11、162-4中的识别码4是这样得到的：对0670082162这9个数字，从左至右，分别乘以1，2，9，再求和，即01+62+29=158，然后取158 mod 11的结果4作为识别码/你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码.【输入】只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码.的格式要求）。【输出】一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。【输入样例】0-670-82162-4【输

12、出样例】Right【输入输出洋例2】0-670-82162-0【输出】0-670-82162-4ex1_2_2.pas数字反转（NOIP2011）【题目描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【输入】输入共 1 行，一个整数N。【输出】输出共 1 行，一个整数，表示反转后的新数。【输入样例】123【输出样例】321【输入输出样例 2】输入：-380输出：-83【数据范围】-1,000,000,000 N 1,000,000,000ex1_2_3.pas乒乓球(noip20

13、03)【题目描述】国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。 华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。 比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）： WWWWWWWWWWWWW

14、WWWWWWWWWLW 在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。 你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。【输入】每个输入包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。【输出】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分

15、制下的结果，两部分之间由一个空行分隔。【输入样例】WWWWWWWWWWWWWWWWWWWWWWLWE【输出样例】11:011:01:121:02:1ex1_2_4.pas统计单词数(NOIP2011)【题目描述】一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单

16、词的一部分则不算匹配（参见样例2）。【输入】2 行：第 1 行为一个字符串，其中只含字母，表示给定单词；第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。【输出】只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。【输入样例】Toto be or not to be is a question【输出样例】2 0【输入输出样例 1 说明】输出结果表示给定的单词 To 在文章中出现两次，第一次

17、出现的位置为0。【提示】【输入输出样例 2】输入：toDid the Ottoman Empire lose its power at that time输出：-1【输入输出样例 2 说明】表示给定的单词 to 在文章中没有出现，输出整数-1。【数据范围】1 单词长度 10。1 文章长度 1,000,000。ex1_2_5.pas计算器的改良(NOIP2000)【题目描述】NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。为了很好的完成这个任务,ZL先生首

18、先研究了一些一元一次方程的实例： 4+3x=8 6a-5+1=2-2a -5+12Y=0 ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母 及十、一、这三个数学符号（当然，符号“一”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。 【输入】输入一个一元一次方程,可认为输入的一元一次方程均为合法的，且有唯一实数解。【输出】将解方程的结果（精确至小数点后三位）输出。【输入样例】6a-5+1=2-2a【输出样例】a=0.750ex1_2_6.pas字符串编辑【题目描述】从键盘输入一个字符串（长度b0 then len:=a0 else le

19、n:=b0;for i:=1 to len do begin ci:=ai+bi;ci+1:=ci div 10; /进位ci:=ci mod 10;end;if clen+10 then inc(len);c0:=len;end;2高精度减法 在存放到a、b数组时，保证数ab，结果存放在C数组中。procedure jian( a,b:arr; var c:arr);var i,len:integer;beginfillchar(c,sizeof(c),0);len:=a0;for i:=1 to len do begin if ai0 then inc(len);c0:=len;end;p

20、lus3高精度乘以单个数x（0x10 then begin Ai+1:=ai+1+ai div 10; /进位处理 Ai:=ai mod 10;End; While alen+10 do begin Len:=len+1; If alen10 then begin Alen+1:=alen div 10; Alen:=alen mod 10; End; End;End;4高精度乘以高精度要求：结果存放在c数组中。procedure cheng2(a,b:arr; var c:arrvar i,j,len:longint;beginfillchar(c,sizeof(c),0);for i:=1

21、 to a0 dofor j:=1 to b0 do begin ci+j-1:=ci+j-1+ai*bj; ci+j:=ci+j+ci+j-1 div 10;ci+j-1:=ci+j-1 mod 10;end;len:=a0+b0;while (len1) and (clen=0) do len:=len-1;c0:=len;end;ex2_1.pas麦森数（NOIP2003）【题目描述】形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦

22、森数有许多重要应用，它与完全数密切相关。任务：输入P（1000P3100000），计算2P-1的位数和最后500位数字(用十进制高精度数表示)【输入】只包含一个整数P（1000P3100000）【输出】第一行：十进制高精度数2P-1的位数。第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）不必验证2P-1与P是否为素数。【输入样例】1279【输出样例】38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

23、000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416

24、585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087ex2_2.pasHanoi双塔问题(NOIP2007)【题目描述】给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的

25、顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】一个正整数n，表示在A柱上放有2n个圆盘。【输出】仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。【输入样例】1【输出样例】2【输入输出样例2】 2 【输出】6 【限制】对于50%的数据， 1=n=25 对于100% 数据， 1=n=200 【提示】 设法建立An与An-1的递推关系式。数论算法1求两数x,y的最大公约数. 2求两数x、y的最小公倍数function lcm(x,y:longint):longint;var temp:longint;beginif xy then b

26、egin temp:=x;x:=y;y:=temp;end;lcm:=x;while lcm mod y0 do inc(lcm,x);end;function gcd(x,y:longint):longint;beginif b=0 then gcd:=xelse gcd:=gcd(y,x mod y);end ;3、素数的求法A.判断一个数n是否为质数：function prime (n: integer): Boolean;var I: integer;beginprime:=true;for I:=2 to trunc(sqrt(n) doif n mod I=0 then begin

27、prime:=false; break;end;end;B.筛选法判断longint范围内的数有哪些素数输入范围n，求出1n中的所有素数。procedure sushu(n);var i,j:longint; f:array1.n of boolean;begin fillchar(f,sizeof(f),true); f1:=false; for i:=2 to trunc(sqrt(n) do if fi then for j:=2 to n div i do fi*j:=false;end;ex3_1.pas最大公约数与最小公倍数(NOIP2001)【题目描述】二个正整数x0,y0(2x

28、0100000,2y01000000),求满足下列条件的P,Q的个数。 条件： 1.P,Q是正整数； 2.要求P,Q以x0为最大公约数，以y0为最小公倍数。 试求：满足条件的所有可能的两个正整数的个数。【输入】输入x0和y0【输出】满足条件的所有可能的两个正整数的个数【输入样例】3 60【输出样例】4【提示】样例说明:此时的P Q分别为： 3 60 15 12 12 15 60 3排序算法对a数组进行从小到大的排序1.快速排序：procedure qsort(l,r:integer);var i,j,mid:integer;begini:=l;j:=r; mid:=a(l+r) div 2;

29、将当前序列在中间位置的数定义为中间数repeatwhile aimid do dec(j);在右半部分寻找比中间数小的数if ij;if lj then qsort(l,j); 若未到两个数的边界，则递归搜索左右区间if iaj then begin temp:=ai; ai:=aj;aj:=temp;end;end;3. 冒泡排序procedure bubble_sort;var i,j,temp:integer;beginfor i:=1 to n-1 dofor j:=1 to n-i doif ajaj+1 then begin temp:=aj; aj:=aj+1;aj+1:=tem

30、p;end; 每次比较相邻元素的关系end;4.桶排序 当数据的范围在一有限范围内时。例：输入n个范围在0.1000之间的整数，从小到大排序输出。Var I,n,x:integer; a:array0.1000 of integer;begin readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); ax:=ax+1; end; for i:=1 to 1000 doif ax0 then write(I, );end.5. 归并排序例：a,b均为已按从小到大排好序的两个数组，将其合并为有序的一个数组。proced

31、ure guibin(a,b:arr;la,lb:longint);var i,j,k:longint;begin fillchar(c,sizeof(c),0); i:=1;j:=1;k:=0; repeat k:=k+1; if aila)or(jlb); if i=la then for j:=i to la do begin k:=k+1; ck:=ai; end; if j=lb then for i:=j to lb do begin k:=k+1; ck:=bj; end;end;ex4_1.pas校门外的树(NOIP2005)【题目描述】某校大门外长度为L的马路上有一排树，每两

32、棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 【输入】第一行有两个整数L（1 = L = 10000）和 M（1 = M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，

33、用一个空格隔开，表示一个区域的起始点和终止点的坐标。【输出】一行，这一行只包含一个整数，表示马路上剩余的树的数目。【输入样例】500 3150 300100 200470 471【输出样例】298【数据规模】 对于20%的数据，区域之间没有重合的部分； 对于其它的数据，区域之间有重合的情况。ex4_2.pas明明的随机数（NOIP2006）【题目描述】明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的

34、顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入】有2行，第1行为1个正整数，表示所生成的随机数的个数：N 第2行有N个用空格隔开的正整数，为所产生的随机数。【输出】2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】1020 40 32 67 40 20 89 300 400 15【输出样例】815 20 32 40 67 89 300 400ex4_3.pas奖学金(NOIP2007)【题目描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都

35、有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。 任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是: 7 279 5 279 这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语

36、文、数学、英语三科成绩之和)，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是: 5 279 7 279 则按输出错误处理，不能得分。【输入】第1行为一个正整数n，表示该校参加评选的学生人数。 第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为ln (恰好是输入数据的行号减1)。 所给的数据都是正确的，不必检验。 【输出】共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。借鉴内容#【输入样例1】690 67 8087 66 9178 89

37、9188 99 7767 89 6478 89 98【输出样例1】6 2654 2643 2582 2441 237【输入样例2】 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 7767 89 64 78 89 98 【输出样例2】 8 2652 264 6 264 1 258 5 258 【限制】 50%的数据满足:各学生的总成绩各不相同；100%的数据满足: 6=namid then i:=mid+1else j:=mid-1; until ij; binsearch:=i;end;进制转换Type Arr:array1.maxl

38、en of integer;说明：除十进制外的其余进制存放在a数组中。1、十进制数x转二进制Procedure shi_zhuan_er(x:longint;var a:arr);Var i:longint;Begin Fillchar(a,sizeof(a),0); I:=0; While x0 do beginI:=i+1;Ai:=x mod 2;X:=x div 2; End; a0:=i; /转化后的数倒着存放在a数组中。End;除2取余法2、任意正整数x转化成n进制Procedure shi_zhuan_n(x,n:longint;var a:arr);Var i:longint;Begin Fillchar(a,sizeof(a),0); I:=0; While x0 do beginI:=i+1;Ai:=x mod n;X:=x div n; End; a0:=i; /转化后的数倒着存放在a数组中。End;除n取余3、n进制转换为十进制正整数x（x在longint范围内）procedure n_zhuan_shi(n:longint;a:arr;var x:longint);var i,y:longint;begin y