noip普及组赛前冲刺资料.docx
《noip普及组赛前冲刺资料.docx》由会员分享，可在线阅读，更多相关《noip普及组赛前冲刺资料.docx（70页珍藏版）》请在冰点文库上搜索。
noip普及组赛前冲刺资料
数组
一、数字数组
ex1_1_1.pas
级数求和（NOIP2002）
【题目描述】
已知：
Sn=1+1/2+1/3+…+1/n。
显然对于任意一个数K，当n.足够大的时候，Sn大于K。
现给出一个整数K（1≤K≤15）,要求计算出一个最小的n,使得Sn>K
【输入】一行,一个整数K
【输出】一行,一个整数n
【输入样例】1
【输出样例】2
ex1_1_2.pas
陶陶摘苹果（NOIP2005）
【题目描述】
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。
苹果成熟的时候，陶陶就会跑去摘苹果。
陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。
现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。
假设她碰到苹果，苹果就会掉下来。
【输入】
两行数据。
第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。
第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。
【输出】一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。
【输入样例】
100200150140129134167198200111
110
【输出样例】5
ex1_1_3.pas
数字统计（NOIP2010）
【题目描述】
请统计某个给定范围[L,R]的所有整数中，数字2出现的次数。
比如给定范围[2,22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
【输入】共1行，为两个正整数L和R，之间用一个空格隔开。
【输出】共1行，表示数字2出现的次数。
【输入样例】222
【输出样例】6
【输入输出样例2】2100
【输出】20
【数据范围】1≤L≤R≤10000。
ex1_1_4.pas
狐狸追兔子
【题目描述】围绕着山顶有m个洞（m<=100），一只狐狸和一只兔子住在各自的洞里。
狐狸总想吃掉兔子。
一天，兔子对狐狸说：
“你想吃我有一个条件，先把洞从1~m编上号，你从m号洞出发，先到一号洞找我；第二次隔1个洞找我，第三次隔2个洞找我，以后依次类推，次数不限。
若能找到我，你就可以饱餐一顿。
不过在没有找我以前不能停下来。
”狐狸满口答应就开始找了，它从早到晚进了n次洞（1<=n<=1000），累得昏了过去也没有找到兔子。
请问，兔子躲在几号洞里？
【输入】一行，洞的个数m，狐狸进洞的次数n
【输出】一行，兔子躲的洞的号数，由小到大输出，各数中间用空格隔开
【输入样例】102
【输出样例】245678910
ex1_1_5.pas
不高兴的津津（NOIP2004）
【题目描述】
津津上初中了。
妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。
另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。
但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。
假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。
请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。
【输入】
包括七行数据，分别表示周一到周日的日程安排。
每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。
【输出】
一行，这一行只包含一个数字。
如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1,2,3,4,5,6,7分别表示周一，周二，周三，周四，周五，周六，周日）。
如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。
【输入样例】
53
62
72
53
54
04
06
【输出样例】
3
ex1_1_6.pas
多项式输出（NOIP2009）
【题目描述】
一元n次多项式可用如下的表达式表示：
其中，aixi称为i次项，ai称为i次项的系数。
给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
1.多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
2.多项式中只包含系数不为0的项。
3.如果多项式n次项系数为正，则多项式开头不出现“+”号，如果多项式n次项系数为负，则多项式以“-”号开头。
4.对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。
紧跟一个正整数，表示此项系数的绝对值（如果一个高于0次的项，其系数的绝对值为1，则无需输出1）。
如果x的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b为x的指数；如果x的指数为1，则接下来紧跟的指数部分形式为“x”；
如果x的指数为0，则仅需输出系数即可。
5.多项式中，多项式的开头、结尾不含多余的空格。
【输入】共有2行
第一行1个整数，n，表示一元多项式的次数。
第二行有n+1个整数，其中第i个整数表示第n-i+1次项的系数，每两个整数之间用空格隔开。
【输出】共1行，按题目所述格式输出多项式。
【输入样例】
5
100-11-3010
【输出样例】
100x^5-x^4+x^3-3x^2+10
【输入输出样例2】
3
-50001
【输出】-50x^3+1
【数据范围】1≤n≤100，多项式各次项系数的绝对值均不超过100。
二、字符数组
定义:
String等价于array[0..255]ofchar，其中第0号但有存放的是实际长度。
Ansistring长度不限。
常用操作
Length（st）求st的长度
Copy（st,m,n）从st的第m个位置开始复制n个字符
Delete（st,m,n）删除st的第m个位置开始的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数组中：
A[0]:
=length（st）;
Fori:
=1toa[0]do
A[i]:
=ord（st[a[0]-i+1]）-48;
ex1_2_1.pas
ISBN号码（NOIP2008）
【题目描述】
每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。
ISBN码的首位数字表示书籍的出版语音，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔符之后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别吗的计算方法如下：
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。
例如ISBN码0-670-82162-4中的识别码4是这样得到的：
对0670082162这9个数字，从左至右，分别乘以1，2，…9，再求和，即0×1+6×2+……+2×9=158，然后取158mod11的结果4作为识别码/
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码.
【输入】只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码.的格式要求）。
【输出】一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。
【输入样例】0-670-82162-4
【输出样例】Right
【输入输出洋例2】0-670-82162-0
【输出】0-670-82162-4
ex1_2_2.pas
数字反转（NOIP2011）
【题目描述】
给定一个整数，请将该数各个位上数字反转得到一个新数。
新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。
【输入】输入共1行，一个整数N。
【输出】输出共1行，一个整数，表示反转后的新数。
【输入样例】123
【输出样例】321
【输入输出样例2】
输入：
-380
输出：
-83
【数据范围】
-1,000,000,000≤N≤1,000,000,000
ex1_2_3.pas
乒乓球（noip2003）
【题目描述】
国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。
其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。
华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。
在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。
华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。
比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：
WWWWWWWWWWWWWWWWWWWWWWLW
在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。
而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。
如果一局比赛刚开始，则此时比分为0比0。
你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。
【输入】
每个输入包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。
其中E表示比赛信息结束，程序应该忽略E之后的所有内容。
【输出】
输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。
其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。
【输入样例】
WWWWWWWWWWWWWWWWWWWW
WWLWE
【输出样例】
11:
0
11:
0
1:
1
21:
0
2:
1
ex1_2_4.pas
统计单词数（NOIP2011）
【题目描述】
一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。
现在，请你编程实现这一功能，具体要求是：
给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。
注意：
匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。
【输入】2行：
第1行为一个字符串，其中只含字母，表示给定单词；
第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。
【输出】只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。
【输入样例】
To
tobeornottobeisaquestion
【输出样例】20
【输入输出样例1说明】
输出结果表示给定的单词To在文章中出现两次，第一次出现的位置为0。
【提示】【输入输出样例2】
输入：
to
DidtheOttomanEmpireloseitspoweratthattime
输出：
-1
【输入输出样例2说明】
表示给定的单词to在文章中没有出现，输出整数-1。
【数据范围】
1≤单词长度≤10。
1≤文章长度≤1,000,000。
ex1_2_5.pas
计算器的改良（NOIP2000）
【题目描述】
NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：
需要在该公司某型号的计算器上加上解一元一次方程的功能。
实验室将这个任务交给了一个刚进入的新手ZL先生。
为了很好的完成这个任务,ZL先生首先研究了一些一元一次方程的实例：
4+3x=8
6a-5+1=2-2a
-5+12Y=0
ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及十、一、＝这三个数学符号（当然，符号“一”既可作减号，也可作负号）。
方程中并没有括号，也没有除号，方程中的字母表示未知数。
【输入】输入一个一元一次方程,可认为输入的一元一次方程均为合法的，且有唯一实数解。
【输出】将解方程的结果（精确至小数点后三位）输出。
【输入样例】6a-5+1=2-2a
【输出样例】a=0.750
ex1_2_6.pas
字符串编辑
【题目描述】
从键盘输入一个字符串（长度<=255个字符），例如：
’Thisisabook.’现对该字符串进行编辑，编辑功能有：
D：
删除一个字符，命令的方式为：
D a 其中a为被删除的字符（D和a之间用空格隔开，以下均是）
例如：
D s 表示删除字符’s’，若字符串中有多个‘s’，则删除第一次出现的。
如上例中删除的结果为：
’Thiisabook.’
I：
插入一个字符，命令的格式为：
I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。
例如：
I s d 表示在指定字符’s’的前面插入字符‘d’，若原串中有多个‘s’，则插入在最后一个字符的前面，如上例中：
原 串：
’Thisisabook.’
插入后：
’Thisidsabook.’
R：
替换一个字符，命令格式为：
R a1 a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1则应全部替换。
例如：
原串：
‘Thisisabook.’
输入命令：
R o e
替换后的字符串为：
‘Thisisabeek.’
在编辑过程中，若出现被改的字符不存在时，则给出提示信息”noexsit!
”。
【输入】输入包含两行，第一行为待编辑的字符串；第二行为对该字符串进行操作的命令字符串，其中命令均为大写字符，命令对象大小写均有可能，命令和命令对象间用一个空格隔开。
【输出】输出只有一行，即编辑后的字符串
【输入样例】
Thisisabook
Isd
【输出样例】
Thisidsabook
高精度算法
说明：
type
arr=array[0..maxlen]ofinteger;
Readln（x）;
Fori:
=1tolength（x）do
A[i]:
=ord（x[length（x）-i+1]）-48;
A[0]:
=length（X）;
数x倒序存放在a数组中：
1．高精度加法（结果存放在C数组中）
procedurejia（a,b:
arr;varc:
arr）;
vari,len:
integer;
begin
fillchar（c,sizeof（c）,0）;
ifa[0]>b[0]thenlen:
=a[0]elselen:
=b[0];
fori:
=1tolendobegin
c[i]:
=a[i]+b[i];
c[i+1]:
=c[i]div10;//进位
c[i]:
=c[i]mod10;
end;
ifc[len+1]>0theninc（len）;
c[0]:
=len;
end;
2．高精度减法
在存放到a、b数组时，保证数a>b，结果存放在C数组中。
procedurejian（a,b:
arr;varc:
arr）;
vari,len:
integer;
begin
fillchar（c,sizeof（c）,0）;
len:
=a[0];
fori:
=1tolendobegin
ifa[i]a[i+1]:
=a[i+1]-1;//借位处理
a[i]:
=a[i]+10;
end;
c[i]:
=a[i]-b[i];
end;
ifc[len+1]>0theninc（len）;
c[0]:
=len;
end;{plus}
3．高精度乘以单个数x（0要求：
结果仍然存放在a数组中。
Procedurecheng1（x:
longint;vara:
arr）;
VarI,j,len:
longint;
Begin
Len:
=a[0];
Fori:
=1tolendo
A[i]:
=a[i]*x;//a内所有元素乘以x
Fori:
=1tolendo
Ifa[i]>10thenbegin
A[i+1]:
=a[i+1]+a[i]div10;//进位处理
A[i]:
=a[i]mod10;
End;
Whilea[len+1]>0dobegin
Len:
=len+1;
Ifa[len]>10thenbegin
A[len+1]:
=a[len]div10;
A[len]:
=a[len]mod10;
End;
End;
End;
4．高精度乘以高精度
要求：
结果存放在c数组中。
procedurecheng2（a,b:
arr;varc:
arr}
vari,j,len:
longint;
begin
fillchar（c,sizeof（c）,0）;
fori:
=1toa[0]do
forj:
=1tob[0]dobegin
c[i+j-1]:
=c[i+j-1]+a[i]*b[j];
c[i+j]:
=c[i+j]+c[i+j-1]div10;
c[i+j-1]:
=c[i+j-1]mod10;
end;
len:
=a[0]+b[0];
while（len>1）and（c[len]=0）dolen:
=len-1;
c[0]:
=len;
end;
ex2_1.pas
麦森数（NOIP2003）
【题目描述】
形如2P-1的素数称为麦森数，这时P一定也是个素数。
但反过来不一定，即如果P是个素数，2P-1不一定也是素数。
到1998年底，人们已找到了37个麦森数。
最大的一个是P=3021377，它有909526位。
麦森数有许多重要应用，它与完全数密切相关。
任务：
输入P（1000＜P＜3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
【输入】只包含一个整数P（1000＜P＜3100000）
【输出】
第一行：
十进制高精度数2P-1的位数。
第2-11行：
十进制高精度数2P-1的最后500位数字。
（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2P-1与P是否为素数。
【输入样例】1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
ex2_2.pas
Hanoi双塔问题（NOIP2007）
【题目描述】
给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。
现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。
要求:
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务:
设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的最小公倍数
functionlcm（x,y:
longint）:
longint;
vartemp:
longint;
begin
ifxtemp:
=x;x:
=y;y:
=temp;
end;
lcm:
=x;
whilelcmmody<>0doinc（lcm,x）;
end;
functiongcd（x,y:
longint）:
longint;
begin
ifb=0then
gcd:
=x
else
gcd:
=gcd（y,xmody）;
end;
3、素数的求法
A.判断一个数n是否为质数：
functionprime（n:
integer）:
Boolean;
varI:
integer;
begin
prime:
=true;
forI:
=2totrunc（sqrt（n））do
ifnmodI=0thenbegin
prime:
=false;
break;
end;
end;
B.筛选法判断longint范围内的数有哪些素数
输入范围n，求出1~n中的所有素
升级会员 