NOIP普与组历届试题分析

NOIP普与组历届试题分析第一页，共105页。引言

noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。第二页，共105页。NOIP普及组题型分布题型题目枚举扫雷游戏(2015p2)、珠心算测验(2014p1)数字统计(2010p1)、比例简化(2014p2)模拟金币(2015p1)、螺旋方阵(2014p3)、计数问题(2013p1)、寻宝(2012p2)、接水问题(2010p2)字符串数字反转(2011p1)、统计单词个数(2011p2)ISBN号码(2008p1)、乒乓球(2003p1)贪心排座椅(2008p2)、纪念品分组(2007p2)第三页，共105页。NOIP普及组题型分布题型题目简单动态规划子矩阵(2014p4)、小朋友的数字(2013p3)摆花(2012p3)、导弹拦截(2010p3)道路游戏(2009p4)、传球游戏(2008p3)守望者的逃离(2007p3)、开心的金明(2006p2)采药(2005p3)、数字游戏(2003p2)数学/数论质因数分解(2012p1)、细胞分裂(2009p3)Hanoi双塔问题(2007p4)、数列(2006p4)循环(2005p4)、栈(2003p3卡特兰数)数据结构表达式求值(2013p2)、表达式的值(2011p4)FBI树(2004p1)、求先序排列(2001p2)图论（提高组）车站分级(2013p4拓扑排序)文化之旅(2012p4floyd算法)第四页，共105页。一、枚举类试题枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。枚举法其实是最简单的搜索算法。第五页，共105页。珠心算测验(noip2014普及组第一题)珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。第六页，共105页。珠心算测验(noip2014普及组第一题)【输入】输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。【输出】输出共一行，包含一个整数，表示测验题答案。【样例输入】 【样例输出】4 21234对于100%的数据，3

≤

n

≤

100测验题给出的正整数大小不超过10,000。第七页，共105页。试题分析题意大意：给你n个数，在这n个数中，找到满足A+B=C的C的个数，注意不是这个等式的个数。样例中，1,2,3,4有1+2=3，1+3=4两个。由于本题数据规模n<=100，我们可以直接枚举C,A,B，三层循环解决问题。第八页，共105页。方法1：三层循环考试中，有许多选手的程序是这样的，错在哪里？ans:=0;forc:=1tondofora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(c<>a)and(a<>b)and(c<>b)theninc(ans);writeln(ans);样例中，上述错误答案是4：3=1+2,3=2+1,4=1+3,4=3+1第九页，共105页。方法1：参考程序vari,n,a,b,c,t,ans:longint;f:array[0..105]oflongint;beginreadln(n);fori:=1tondoread(f[i]);ans:=0;forc:=1tondobegin

t:=0;fora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(t=0)and(c<>a)and(a<>b)and(c<>b)thenbegininc(ans);

t:=1;end;end;writeln(ans);end.第十页，共105页。方法2：两层循环我们能不能使用两层循环呢？由于本题测验题给出的正整数大小不超过10,000，我们可以直接枚举A,B，判断A+B在不在给定的数中即可。定义一个数组vis，初始值为0；读入数a[i]时，vis[a[i]]标记为1。

fori=1tondo{read(f[i]);vis[f[i]]=1;}第十一页，共105页。方法2：两层循环两层循环枚举a,b的值，判断a+b是否存在：

fora=1tondoforb=1tondoif(vis[f[a]+f[b]]=1)and(a<>b)thenbegininc(ans);vis[f[a]+f[b]]=2;//避免出现重复的等式 end;第十二页，共105页。方法2：参考代码vari,n,a,b,ans:longint;vis:array[0..20005]of0..2;f:array[0..105]oflongint;beginreadln(n);fillchar(vis,sizeof(vis),0);fori:=1tondobeginread(f[i]);vis[f[i]]:=1;end;ans:=0;fora:=1tondoforb:=1tondoif(vis[f[a]+f[b]]=1)and(a<>b)thenbegininc(ans);vis[f[a]+f[b]]:=2;end;writeln(ans);end.第十三页，共105页。数字统计(noip2010普及组第一题)请统计某个给定范围[L,R]的所有整数中，数字2出现的次数。比如在给定范围[2,22]，数字2在数2中出现了1次，在数12中出现了1次，在数20中出现了1次，在数21中出现了1次，在数22中出现了2次，所以数字2在该范围内一共出现了6次。输入格式输入共一行，为两个正整数L和R，之间用一个空格隔开。输出格式输出共1行，表示数字2出现的次数。样例输入：222样例输出：6第十四页，共105页。试题分析题目大意是给定a,b，统计a,b之间数字2出现的次数。从a到b直接枚举每一个数，判断这个数中含有几个2。fori=atobdo{

求i中含2的个数t;ans=ans+t;}输出t;第十五页，共105页。参考程序：vari,a,b,ans:longint;beginreadln(a,b);ans:=0;fori:=atobdobeginifimod10=2theninc(ans);ifidiv10mod10=2theninc(ans);ifidiv10div10mod10=2theninc(ans);ifidiv10div10div10mod10=2theninc(ans);end;writeln(ans);end.第十六页，共105页。扫雷游戏(noip2015普及组第二题)扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

第十七页，共105页。扫雷游戏(noip2015普及组第二题)输入样例

1

3

3

*??

???

?*?

输入样例

2

2

3

?*?

*??

输出样例

1

mine.out

*10

221

1*1

输出样例

2

mine.out

2*1

*21对于

100%的数据，1≤n≤100，1≤m≤100

第十八页，共105页。问题分析：本题也是简单的枚举类试题。我们从雷区的第一行第一列(1,1)开始，判断它周围有多少个地雷。由于本题读入的是字符，读入时需要注意：

readln(n,m);fori=1tondobeginforj=1tomdoread(a[i][j]);

readln;end;第十九页，共105页。问题分析：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。判断如下：

ifa[i][j-1]='*'theninc(s);ifa[i][j+1]='*'theninc(s);ifa[i+1][j-1]='*'theninc(s);ifa[i+1][j+1]='*'theninc(s);ifa[i+1][j]='*'theninc(s);ifa[i-1][j-1]='*'theninc(s);ifa[i-1][j+1]='*'theninc(s);ifa[i-1][j]='*'theninc(s);

第二十页，共105页。参考程序：vari,j,n,m,s:longint;a:array[0..105,0..105]ofchar;beginreadln(n,m);fori:=1tondobeginforj:=1tomdoread(a[i][j]);readln;end;fori:=1tondobeginforj:=1tomdobegins:=0;ifa[i,j]='*'thenwrite(a[i,j])elsebeginifa[i][j-1]='*'theninc(s);ifa[i][j+1]='*'theninc(s);ifa[i+1][j-1]='*'theninc(s);ifa[i+1][j+1]='*'theninc(s);ifa[i+1][j]='*'theninc(s);ifa[i-1][j-1]='*'theninc(s);ifa[i-1][j+1]='*'theninc(s);ifa[i-1][j]='*'theninc(s);write(s);end;end;writeln;end;end.第二十一页，共105页。比例简化(noip2014普及组第二题)在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498:902。不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值尽可能小。

第二十二页，共105页。比例简化(noip2014普及组第二题)输入格式输入共一行，包含三个整数A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。输出格式输出共一行，包含两个整数A’，B’，中间用一个空格隔开，表示化简后的比例。样例输入149890210样例输出53第二十三页，共105页。比例简化试题分析读入a,b,L后，从1到L分别枚举a’和b’。判断a’和b’是否合法，合法的话就记录下来。输入a,b,L;

fori=1toLdoforj=1toLdoifi,j合法then{ansx=i;ansy=j;}输出ansx,ansy;第二十四页，共105页。比例简化试题分析程序的关键在于如何判断i,j合法。if(gcd(i,j)=1)and(i/j>=a/b)thenifi/j-a/b<minnthenbeginminn:=i/j-a/b;ansx:=i;ansy:=j;end;条件1：i和j互质；条件2：i/j的值大于等于A/B的值

；条件3：i/j－A/B的值尽可能小

；第二十五页，共105页。比例简化参考程序：vara,b,L,i,j,ansx,ansy:longint;minn:real;functiongcd(x,y:longint):longint;beginify=0thenexit(x);gcd:=gcd(y,xmody);end;beginreadln(a,b,L);minn:=99999999;fori:=1toLdoforj:=1toLdoif(gcd(i,j)=1)and(i/j>=a/b)thenifi/j-a/b<minnthenbeginminn:=i/j-a/b;ansx:=i;ansy:=j;end;writeln(ansx,'',ansy);end.

第二十六页，共105页。二、模拟类试题有些问题，我们很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。第二十七页，共105页。金币(noip2015普及组第一题)国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。

请计算在前K天里，骑士一共获得了多少金币。

输入格式：

输入文件只有1行，包含一个正整数K，表示发放金币的天数。输出格式：

输出文件只有1行，包含一个正整数，即骑士收到的金币数。输入输出样例

输入样例：

1000输出样例： 29820第二十八页，共105页。试题分析本题直接模拟即可。定义变量时注意不要混淆了：i代表枚举的天数，t代表连续的天数，也是每天收到的金币数，s收到的金币总数。读入天数k;i=1;t=1;s=0;whilei<=kdo{forj=1totdo{s=s+t;i=i+1;ifi>kthenbreak;}t=t+1;}输出s;第二十九页，共105页。参考程序：vari,

j,

k,

s,

t:longint;beginreadln(k);i:=1;t:=1;s:=0;whilei<=kdobeginforj:=1totdobegininc(s,t);inc(i);

ifi>kthenbreak;end;inc(t);end;writeln(s);end.第三十页，共105页。螺旋方阵(noip2014普及组第三题)一个n行n列的螺旋矩阵可由如下方法生成：从矩阵的左上角(第1行第1列)出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,3,....，便构成了一个螺旋矩阵。

现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。

下图是一个n=4时的螺旋矩阵。第三十一页，共105页。螺旋方阵(noip2014普及组第三题)输入格式输入共一行，包含三个整数n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。输出格式输出共一行，包含一个整数，表示相应矩阵中第i行第j列的数。样例输入：423

样例输出：14对于50%的数据，1≤n≤100;

对于100%的数据，1≤n≤30,000，1≤i≤n，1≤j≤n。

第三十二页，共105页。螺旋方阵试题分析本题首先让我们想到传统的模拟，从[1,1]开始往数组中填充数字，但对于[30000,30000]的数组，直接爆零。对于读入的n,x,y，先判断(x,y)在第几圈，再模拟圈内的数字。第三十三页，共105页。螺旋方阵试题分析如：n=4,(2,2)在第2圈，(3,1)在第1圈。n=6，(4,5)在第2圈圈数q=min(x,y,n-x+1,n-y+1

)即目标位置到四个边界距离的最小值第三十四页，共105页。螺旋方阵试题分析圈数q求出后，前q圈的数字总和很容易求出来。对于任何一个方阵：第1圈有4n-4个数;第2圈有4(n-2)-4个数；第3圈有4(n-4)-4个数；……第q圈有4(n-q(n-1))-4个数第三十五页，共105页。螺旋方阵试题分析前1圈有4n-4个数;前2圈有4n-4+4(n-2)-4=2(4n-2*4)个数；前3圈有4(n-4)-4+2(4n-8)=3(4n-3*4)个数；……前q圈有q(4n-4q)个数；第三十六页，共105页。螺旋方阵试题分析目标位置(i,j)到底在当前这一圈的第几个位置？如目标数26所在的位置(4,5)，在第2圈的什么位置？分两种情况：1）目标数(i,j)在上行或右行；i+j-2q+12）目标数(i,j)在下行或左行；距离第一个数的距离

i+j-2q+1第三十七页，共105页。螺旋方阵参考程序：varn,i,j,q,ans:longint;functionmin(a,b:longint):longint;beginifa<bthenexit(a)elseexit(b);end;beginreadln(n,i,j);q:=min(i,min(j,min(n-i+1,n-j+1)));ifi<=jthenans:=q*(4*(n-1)-4*q)+10*q-4*n-3+i+jelseans:=q*(4*n-4*q)+2*q+1-i-j;writeln(ans);end.第三十八页，共105页。计数问题(noip2013普及组第一题)试计算在区间1到n的所有整数中，数字x（0≤x≤9）共出现了多少次？

例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，数字1出现了4次。输入：输入共1行，包含2个整数n、x，之间用一个空格隔开。

输出：输出共1行，包含一个整数，表示x出现的次数。

输入示例：

11

1输出示例：

4其他说明：对于100%的数据，1≤n≤1,000,000，0≤x≤9。

第三十九页，共105页。计数问题试题分析这道题入门难度，直接模拟。循环1到n之间的所有数，对每个数的每位判断即可。读入n,x;fori=1tondo{k=i;whilek的每一位jdoifj=xtheninc(ans);}输出ans;第四十页，共105页。计数问题参考程序这道题入门难度，直接模拟。循环1到n之间的所有数，对每个数的每位判断即可。vari,n,x,k,ans:longint;beginreadln(n,x);ans:=0;fori:=1tondobegink:=i;whilek>0dobeginifkmod10=xtheninc(ans);k:=kdiv10;end;end;writeln(ans);end.第四十一页，共105页。寻宝(noip2012普及组第二题)

传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有N层，每层M个房间，这M个房间围成一圈并按逆时针方向依次编号为0，…，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的k号房间。比如当前房间的指示牌上写着2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。第四十二页，共105页。寻宝(noip2012普及组第二题)

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。【输入】

第一行2个整数N和M，之间用一个空格隔开。N表示除了顶层外藏宝楼共N层楼，M表示除顶层外每层楼有M个房间。

接下来N*M

行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第(i-1)*M+j行表示第i层j-1号房间的情况（i=1,2,…,N；j=1,2,…,M）。第一个整数表示该房间是否有楼梯通往上一层（0表示没有，1表示有），第二个整数表示指示牌上的数字。注意，从j号房间的楼梯爬到上一层到达的房间一定也是j号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从0开始）。第四十三页，共105页。寻宝(noip2012普及组第二题)【输出】输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对20123取模的结果即可。

【输入输出样例】treasure.in treasure.out23 51203140115121第四十四页，共105页。寻宝(noip2012普及组第二题)【输入输出样例说明】第一层：0号房间，有楼梯通往上层，指示牌上的数字是2；1号房间，无楼梯通往上层，指示牌上的数字是3；2号房间，有楼梯通往上层，指示牌上的数字是4；第二层：0号房间，无楼梯通往上层，指示牌上的数字是1；1号房间，有楼梯通往上层，指示牌上的数字是5；2号房间，有楼梯通往上层，指示牌上的数字是2；小明首先进入第一层（底层）的1号房间，记下指示牌上的数字为3，然后从这个房间开始，沿逆时针方向选择第3个有楼梯的房间2号房间进入，上楼后到达第二层的2号房间，记下指示牌上的数字为2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第2个有楼梯的房间即为1号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即3+2=5，所以打开宝箱的密钥就是5。第四十五页，共105页。寻宝试题分析题目大意：n层楼，每层m个房间。每个房间有一个号码，楼梯。从底楼出发，如果该房间有楼梯，直接上楼，否则走到该层下个指定的房间。将每一层第一个到达的房间号加起来就是答案。第四十六页，共105页。寻宝试题分析我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：1.房间号从0开始，所以读入时要注意；readln(n,m);fori=1tondoforj=0tom-1do读入楼梯和号码；第四十七页，共105页。寻宝试题分析我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：1.房间号从0开始，所以读入时要注意；2.读入时统计每一层有多少个带楼梯的房间；readln(n,m);fori=1tondoforj=0tom-1do

beginreadln(stair[i,j],num[i,j]);ifstair[i,j]=1theninc(sum[i]);end;第四十八页，共105页。寻宝试题分析我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：1.房间号从0开始，所以读入时要注意；2.读入时统计每一层有多少个带楼梯的房间；3.理解“从这个房间开始按逆时针方向选择第x个有楼梯的房间”。假如当前房间没有楼梯，指示牌上的号为j：whilej>0dobeginifstair[i,k]=1thendec(j);ifj>0thenk:=(k+1)modm;end;第四十九页，共105页。寻宝参考程序vari,j,n,m,k,ans:longint;num:array[0..10001,0..101]oflongint;sum:array[0..10001]oflongint;stair:array[0..10001,0..101]of0..1;beginreadln(n,m);fillchar(sum,sizeof(sum),0);fori:=1tondoforj:=0tom-1dobeginreadln(stair[i,j],num[i,j]);ifstair[i,j]=1theninc(sum[i]);end;readln(k);ans:=0;fori:=1tondobeginans:=(ans+num[i,k])mod20123;num[i,k]:=num[i,k]modsum[i];ifnum[i,k]=0thennum[i,k]:=sum[i];j:=num[i,k];whilej>0dobeginifstair[i,k]=1thendec(j);ifj>0thenk:=(k+1)modm;end;end;writeln(ans);end.

第五十页，共105页。接水问题(noip2010普及组第二题)学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj

后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水，则k同学第x+1秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它m−n个龙头关闭。现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。第五十一页，共105页。接水问题(noip2010普及组第二题)输入第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。第2行n个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi

表示i号同学的接水量。输出输出只有一行，1个整数，表示接水所需的总时间。样例输入： 53 44121样例输出：

4第五十二页，共105页。接水问题试题分析题目大意：n个人排队顺序接水，共m个水龙头。求接完水需要最少的秒数。本题直接模拟即可。有的选手在考试中使用秒去枚举，结果严重超时。对于每一个人，选择这m个水龙头中接水量最小的去接。最后输出这m个水龙头中接水量最大的。第五十三页，共105页。接水问题参考程序vara:array[0..10001]oflongint;s:array[0..101]oflongint;n,m,i,j,k,ans,minn:longint;beginreadln(n,m);fori:=1tondoread(a[i]);fillchar(s,sizeof(s),0);fori:=1tondobeginminn:=9999999;forj:=1tomdoifs[j]<minnthenbegink:=j;minn:=s[j];end;inc(s[k],a[i]);end;ans:=0;fori:=1tomdoifs[i]>ansthenans:=s[i];writeln(ans);end.

第五十四页，共105页。三、字符串类试题对于字符串、表达式的求解、大整数的处理等等，我们经常采用字符串来处理。字符串处理常见函数和过程：length()、delete()pos()、val()、str()第五十五页，共105页。数字反转(noip2011普及组第一题)给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（如：输入-380，输出-83）。输入输入共1行，一个整数N。输出输出共1行，一个整数，表示反转后的新数。样例输入123样例输出321第五十六页，共105页。数字反转试题分析方法1：直接降位取个位降位：ndiv10取个位：nmod10注意删去末尾的0！缺点：数不能太大，容易溢出！第五十七页，共105页。数字反转试题分析varn:longint;beginreadln(n);ifn<0thenbeginwrite('-');n:=-n;end;ifn=0thenwrite(0)elsebeginwhile(nmod10=0)don:=ndiv10;whilen>0dobeginwrite(nmod10);n:=ndiv10;end;end;end.第五十八页，共105页。数字反转试题分析方法2：字符串注意1：负数的处理ifs[1]='-'thenbeginwrite('-');delete(s,1,1);end;

第五十九页，共105页。数字反转试题分析方法2：字符串注意1：负数的处理注意2：末尾0的处理：len=length(s);while(s[len]='0')dodec(len);

fori=lendownto1dowrite(s[i]);

第六十页，共105页。数字反转参考程序vars:ansistring;i,len:longint;beginreadln(s);ifs[1]='-'thenbeginwrite('-');delete(s,1,1);end;len:=length(s);while(s[len]='0')dodec(len);fori:=lendownto1dowrite(s[i]);end.第六十一页，共105页。统计单词个数(noip2011普及组第二题)一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。

第六十二页，共105页。统计单词个数(noip2011普及组第二题)输入格式第1行为一个字符串，其中只含字母，表示给定单词；

第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。输出格式只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

第六十三页，共105页。统计单词个数(noip2011普及组第二题)样例输入1：

To

to

be

or

not

to

be

is

a

question样例输出1：

2

0样例输入2：

to

Did

the

Ottoman

Empire

lose

its

power

at

that

time

样例输出2：

-1

【输入输出样例2说明】

表示给定的单词to在文章中没有出现，输出整数-1。注释说明1≤单词长度≤10。

1≤文章长度≤1,000,000。第六十四页，共105页。统计单词个数试题分析本题是简单的字符串处理。读入单词和文章（字符串）后，可以把单词和文章全部转换成大写（或小写），然后循环在文章中对单词进行查找，找到就存储位置，并统计找到的次数。转换成大写有两种方法：方法1：利用ord()和chr()函数逐个字符转换：fori=1tolength(s)doifs[i]>='a'thens[i]:=chr(ord(s[i])-32);方法2：利用upcase()函数直接转换：s=upcase(s);第六十五页，共105页。统计单词个数试题分析本题还有一个问题需要处理：查找的单词s1只是文章s中某个单词的一部分，如：ToDid

the

Ottoman

Empire处理方法：读入单词s1后，在s1的两端各添加一个空格。s1=''+s1+''第六十六页，共105页。统计单词个数参考程序vars1,s:ansistring;i,p,len,ans:longint;beginreadln(s1);//单词

readln(s);//文章

s1:=''+upcase(s1)+'';s:=''+upcase(s)+'';p:=-1;ans:=0;len:=length(s1);fori:=1tolength(s)-len+1doifcopy(s,i,len)=s1thenbeginifp=-1thenp:=i-1;inc(ans);end;ifp=-1thenwrite(p)elsewrite(ans,'',p);end.第六十七页，共105页。四、贪心类试题从问题的某一个初始解出发，向给定的目标递推。推进的每一步不是依据某一固定的递推公式，而是做一个当时看似最佳的贪心选择，不断地将问题归纳为更小的相似的子问题，最终产生出一个全局最优解。第六十八页，共105页。排座椅(noip2008普及组第二题)上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。第六十九页，共105页。排座椅(noip2008普及组第二题)输入输入的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。

接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。输出输出共两行。

第一行包含K个整数，a1a2……aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai<

ai+1，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含L个整数，b1b2……bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi<

bi+1，每两个整数之间用空格隔开（行尾没有空格）。第七十页，共105页。排座椅(noip2008普及组第二题)输入样例45123424323332524

输出样例224第七十一页，共105页。排座椅试题分析贪心。题意：教室有m行n列，现在要划分k条横向通道，L条纵向的通道。交头接耳的学生位置[xi,yi]和[pi,qi]。怎么划分通道，使得上课时交头接耳的学生对数最少。用row[i]记录第i行与第i+1行之间有多少对交头接耳的；用col[i]记录第i列与第i+1列有多少对交头接耳的。将row从大到小排序，前k个即为要隔开的行；将col从大到小排序，前L个即为要隔开的列。第七十二页，共105页。排座椅试题分析程序的框架：读入m,n,k,L,d;Fori=1tod{

读入x,y,p,q;ifx=ptheninc(row[min(x,p)].value)elseinc(col[min(y,q)].value);}对数组row按row.value从大到小排序;对于数组row[1]到row[k]按row.no从小到大排序；输出row[1]…row[k];对数组col按col.value从大到小排序;对于数组col[1]到col[L]按col.no从小到大排序；输出col[1]…col[L];第七十三页，共105页。排座椅参考程序varm,n,t,k,L,d,i,j,x,y,p,q,maxx:longint;row,col,a:array[0..1005]oflongint;functionmin(x,y:longint):longint;beginifx>ythenexit(y)elseexit(x);end;beginreadln(m,n,k,L,d);fillchar(row,sizeof(row),0);fillchar(col,sizeof(col),0);fori:=1toddobeginreadln(x,y,p,q);ifx=ptheninc(col[min(y,q)])elseinc(row[min(x,p)]);end;t:=0;whilet<kdo//求行中说话最多的k个人

beginmaxx:=1;fori:=2tomdoifrow[i]>row[maxx]thenmaxx:=i;row[maxx]:=-1;inc(t);end;t:=0;whilet<Ldo//求列中说话最多的L个人

beginmaxx:=1;fori:=2tondoifcol[i]>col[maxx]thenmaxx:=i;col[maxx]:=-1;inc(t);end;fori:=1tomdoifrow[i]=-1thenwrite(i,'');writeln;fori:=1tondoifcol[i]=-1thenwrite(i,'');writeln;end.第七十四页，共105页。纪念品分组(noip2007普及组第二题)元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。第七十五页，共105页。纪念品分组(noip2007普及组第二题)输入包含n+2行:第1行包括一个整数w，为每组纪念品价格之和的上眼=

第2行为一个整数n，表示购来的纪念品的总件数G第3-n+2行每行包含一个正整数Pi(5<=Pi<=w3)w表示所对应纪念品的价格。输出仅一行，包含一个整数，

ep最少的分组数目合第七十六页，共105页。纪念品分组(noip2007普及组第二题)样例输入： 样例输出：100 69

90

20

20

30

50

60

70

80

90100%的数据满足:1<=n<=30000，

80<=W<=200第七十七页，共105页。纪念品分组试题分析算法：贪心先按n件纪念品的价值进行排序，贪心策略是价值最小的与价值最大的为一组，这样分组是最少的。第七十八页，共105页。纪念品分组试题分析算法：贪心先按n件纪念品的价值进行排序，贪心策略是价值最小的与价值最大的为一组，这样分组是最少的。第七十九页，共105页。纪念品分组参考程序vari,j,t,m,n,left,right,ans:longint;a:array[0..30001]oflongint;beginreadln(m,n);fori:=1tondoreadln(a[i]);fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenbegint:=a[i];a[i]:=a[j];a[j]:=t;end;ans:=0;left:=1;right:=n;whileleft<=rightdobeginifa[left]+a[right]<=mthenbegininc(left);dec(right);endelsedec(right);inc(ans);end;ifleft=righttheninc(ans);writeln(ans);end.第八十页，共105页。六、简单动态规划类试题动态规划是解决多阶段决策最优化问题的一种思想方法。一般我们从初始阶段出发，枚举每个阶段的所有状态，在状态转移的过程中，我们需要决策。根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。普及组一般考查的动态规划：01背包，最长上升子序列，一些简单的线性动规。第八十一页，共105页。守望者的逃离(noip2007普及组第三题)恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，岛上的所有人都会遇难：守望者的跑步速度，为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。第八十二页，共105页。守望者的逃离(noip2007普及组第三题)输入输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。输出输出文件escape.out包含两行:第1行为字符串“Yes”或“No”(区分大小写)，即守望者是否能逃离荒岛。第2行包含一个整数，第一行为“Yes”(区分大小写）时表示守望着逃离荒岛的最短时间第一行为“No”(区分大小写)

时表示守望者能走的最远距离。样例输入392004样例输出No197提示100%的数据满足:1<=T<=300000,

0<=M<=10001<=S<=10^8第八十三页，共105页。守望者的逃离试题分析题目大意：一个人在t时间内是否能够行走的s米的距离，行走的方式有两种：1.使用魔法（每秒60米），缺点每秒耗费10点魔法值；2.跑步（每秒17米）。第八十四页，共105页。守望者的逃离试题分析算法：贪心

+背包型动态规划贪心的策略：有魔法的情况下，肯定先用魔法跑，这样跑的快！如果魔法不够，那么我们利用背包模型，只有在下列两种选择中选择其中一种：1、使用魔法2、跑步第八十五页，共105页。守望者的逃离试题分析令f[i]表示前i秒利用魔法行走的距离；dp[i]表示利用魔法或者跑步行走的最大距离。很容易求出1到t的f[i]的值：fori=1totdo{ifmagic>=10then{magic=magic-10;f[i]=f[i-1]+60;}else{magic=magic+4;f[i]=f[i-1];}}第八十六页，共105页。守望者的逃离试题分析下面求dp[i]，01背包：

dp[i]=max(dp[i-1]+17,f[i]);第八十七页，共105页。守望者的逃离参考程序vari,m,s,t,ok:longint;f,dp:array[0..300001]oflongint;functionmax(x,y:longint):longint;beginifx>ythenexit(x)elseexit(y);end;beginreadln(m,s,t);fillchar(f,sizeof(f),0);fillchar(dp,sizeof(dp),0);ok:=0;fori:=1totdobeginifm>=10thenbeginm:=m-10;f[i]:=f[i-1]+60;endelsebeginm:=m+4;f[i]:=f[i-1];end;dp[i]:=max(dp[i-1]+17,f[i]);

ifdp[i]>=sthenbeginwriteln('Yes');writeln(i);ok:=1;break;end;end;ifok=0thenbeginwriteln('No');writeln(dp[t]);end;end.

第八十八页，共105页。小朋友的数字(noip2013普及组第三题)有n个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对p取模后输出。第八十九页，共105页。小朋友的数字(noip2013普及组第三题)输入格式第一行包含两个正整数n、p,之间用一个空格隔开。

第二行包含n个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。输出格式输出只有一行,包含一个整数,表示最大分数对p取模的结果。样例输入1599712345样例输出121第九十页，共105页。小朋友的数字试题分析主要考查选手的语文理解能力，关键把题读懂。需要理解的两个值：特征值：前面连续若干个数字和的最大值；分数：前面每个小朋友的分数+特征值的最大值第九十一页，共105页。小朋友的数字试题分析算法：动态规划

+贪心求小朋友的特征值需要求最大子段和。fori=1tondodp[i]=max(dp[i-1]+a[i],a[i]);每个小朋友的特征值t[i]:fori=1tondo{dp[i]=max(dp[i-1]+a[i],a[i]);

t[i]=max(t[i-1],dp[i]);}第九十二页，共105页。小朋友的数字试题分析算法：动态规划

+贪心求小朋友的分数需要贪心：如果第一个小朋友的分数+特征值为负数，那么后面所有小朋友的分数=第一个小朋友的分数+特征值，否则=前一个小朋友的分数+特征值。fori=2tondoifte[1]+fen[1]<0thenfen[i]=te[1]+fen[1]elsefen[i]=te[i-1]+fen[i-1];第九十三页，共105页。采药（noip2005普及组第三题）辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近