NOIP普及组历届试题分析.ppt

1、NOIP普及组历届试题分析,安徽省六安第一中学 江家和,引言,noip复赛的知识面很广泛，对选手的综合素质考核要求更为严格，难度和分数的阶梯层次更趋科学合理，对信息学活动的推动力和社会公信力更为增强。,NOIP普及组题型分布,NOIP普及组题型分布,一、枚举类试题,枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。 枚举法其实是最简单的搜索算法。,珠心算测验 (noip2014普及组第一题),珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因

2、而在很多学校得到普及。 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？ 最近老师出了一些测验题，请你帮忙求出答案。,珠心算测验 (noip2014普及组第一题),【输入】 输入共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。 第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。 【输出】 输出共一行，包含一个整数，表示测验题答案。 【样例输入】【样例输出】 4 2 1 2 3 4,对于100%的数据，3n100 测验题给出的

3、正整数大小不超过10,000。,试题分析,题意大意：给你n个数，在这n个数中，找到满足A+B=C的C的个数，注意不是这个等式的个数。,样例中，1,2,3,4有1+2=3，1+3=4两个。,由于本题数据规模n=100，我们可以直接枚举C, A, B，三层循环解决问题。,方法1：三层循环,考试中，有许多选手的程序是这样的，错在哪里？,ans:=0; for c:=1 to n do for a:=1 to n do for b:=1 to n do if (fc=fa+fb)and(ca)and(ab)and(cb) then inc(ans); writeln(ans);,样例中，上述错误答案是

4、4：3=1+2, 3=2+1, 4=1+3, 4=3+1,方法1：参考程序,var i,n,a,b,c,t,ans:longint; f:array0.105of longint; begin readln(n); for i:=1 to n do read(fi); ans:=0; for c:=1 to n do begin t:=0; for a:=1 to n do for b:=1 to n do if (fc=fa+fb)and(t=0)and(ca)and(ab)and(cb) then begin inc(ans); t:=1; end; end; writeln(ans);

5、end.,方法2：两层循环,我们能不能使用两层循环呢？,由于本题测验题给出的正整数大小不超过10,000，我们可以直接枚举A,B，判断A+B在不在给定的数中即可。,定义一个数组vis，初始值为0； 读入数ai时，visai标记为1。 for i=1 to n do read(fi); visfi=1; ,方法2：两层循环,两层循环枚举a,b的值，判断a+b是否存在： for a=1 to n do for b=1 to n do if (visfa+fb=1) and (ab) then begin inc(ans); visfa+fb=2; /避免出现重复的等式 end;,方法2：参考代码,

6、var i, n, a, b, ans:longint; vis:array0.20005of 0.2; f:array0.105of longint; begin readln(n); fillchar(vis,sizeof(vis),0); for i:=1 to n do begin read(fi); visfi:=1; end; ans:=0; for a:=1 to n do for b:=1 to n do if (visfa+fb=1)and(ab) then begin inc(ans); visfa+fb:=2; end; writeln(ans); end.,数字统计 (

7、noip2010普及组第一题),请统计某个给定范围L, R的所有整数中，数字2出现的次数。 比如在给定范围2, 22，数字2在数2中出现了1次，在数12中出现了1次，在数20中出现了1次，在数21中出现了1次，在数22中出现了2次，所以数字2在该范围内一共出现了6次。 输入格式 输入共一行，为两个正整数L和R，之间用一个空格隔开。 输出格式 输出共1行，表示数字2出现的次数。 样例输入：2 22 样例输出：6,试题分析,题目大意是给定a,b，统计a,b之间数字2出现的次数。 从a到b直接枚举每一个数，判断这个数中含有几个2。,for i=a to b do 求i中含2的个数t; ans=ans

8、+t; 输出t;,参考程序：,var i,a,b,ans:longint; begin readln(a,b); ans:=0; for i:=a to b do begin if i mod 10=2 then inc(ans); if i div 10 mod 10=2 then inc(ans); if i div 10 div 10 mod 10=2 then inc(ans); if i div 10 div 10 div 10 mod 10=2 then inc(ans); end; writeln(ans); end.,扫雷游戏 (noip2015普及组第二题),扫雷游戏是一款十

9、分经典的单机小游戏。 在 n 行 m 列的雷区中有一些格子含有地雷（称之为地雷格） ，其他格子不含地雷（称之为非地雷格） 。玩家翻开一个非地雷格时，该格将会出现一个数字提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布， 要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。,扫雷游戏 (noip2015普及组第二题),输入样例133*?*? 输入样例223?*?*?,输出样例1mine.out*102211*1 输出样例2mine.o

10、ut2*1*21,对于100%的数据，1n100，1m100,问题分析：,本题也是简单的枚举类试题。 我们从雷区的第一行第一列(1,1)开始，判断它周围有多少个地雷。 由于本题读入的是字符，读入时需要注意： readln(n,m); for i=1 to n do begin for j=1 to m do read(aij); readln; end;,问题分析：,一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。判断如下： if aij-1=* then inc(s); if aij+1=* then inc(s); if ai+1j-1=* th

11、en inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s);,参考程序：,var i,j,n,m,s:longint; a:array0.105,0.105of char; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(aij); readln; end; for i:=1 to n do begin f

12、or j:=1 to m do begin s:=0; if ai,j=* then write(ai,j),else begin if aij-1=* then inc(s); if aij+1=* then inc(s); if ai+1j-1=* then inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s); write(s); end; end; writeln; end;

13、end.,比例简化 (noip2014普及组第二题),在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某 一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与 真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A比 B，要求在 A和 B均不大于 L

14、 且 A和 B互质（两个整数的最大公约数是 1）的前提下，A/B A/B 且 A/B - A/B 的值尽可能小。,比例简化 (noip2014普及组第二题),输入格式 输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。 输出格式 输出共一行，包含两个整数 A，B，中间用一个空格隔开，表示化简后的比例。 样例输入 1498 902 10 样例输出 5 3,比例简化试题分析,读入a,b,L后，从1到L分别枚举a和b。判断a和b是否合法，合法的话就记录下来。,输入a,b,L; for i=1 to L do for j=1 to L do if

15、i,j合法 then ansx=i; ansy=j; 输出ansx, ansy;,比例简化试题分析,程序的关键在于如何判断i,j合法。,if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end;,条件1：i和j互质；,条件2：i/j的值大于等于A/B的值 ；,条件3：i/jA/B的值尽可能小 ；,比例简化参考程序：,var a,b,L,i,j,ansx,ansy:longint; minn:real; function gcd(x,y:longint):long

16、int; begin if y=0 then exit(x); gcd:=gcd(y,x mod y); end; begin readln(a,b,L); minn:=99999999; for i:=1 to L do for j:=1 to L do if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end; writeln(ansx, ,ansy); end.,二、模拟类试题,有些问题，我们很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等

17、算法。在这种情况下，一般采用模拟策略。 所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。,金币 (noip2015普及组第一题),国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。请计算在前K天里，骑士一共获得了多少金币。 输入格式：输入文件只有1行，包含

18、一个正整数K，表示发放金币的天数。 输出格式：输出文件只有1行，包含一个正整数，即骑士收到的金币数。 输入输出样例 输入样例： 1000 输出样例： 29820,试题分析,本题直接模拟即可。定义变量时注意不要混淆了： i代表枚举的天数，t代表连续的天数，也是每天收到的金币数，s收到的金币总数。,读入天数k; i=1; t=1; s=0; while ik then break; t=t+1; 输出s;,参考程序：,var i, j, k, s, t:longint; begin readln(k); i:=1; t:=1; s:=0; while ik then break; end; inc

19、(t); end; writeln(s); end.,螺旋方阵 (noip2014普及组第三题),一个n行n列的螺旋矩阵可由如下方法生成： 从矩阵的左上角(第1行第1列)出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,3,.，便构成了一个螺旋矩阵。 现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。 下图是一个n=4时的螺旋矩阵。,螺旋方阵 (noip2014普及组第三题),输入格式 输入共一行，包含三个整数 n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在

20、的行号和列号。 输出格式 输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。 样例输入：4 2 3 样例输出：14 对于 50%的数据，1 n 100;对于 100%的数据，1 n 30,000，1 i n，1 j n。,螺旋方阵试题分析,本题首先让我们想到传统的模拟，从1,1开始往数组中填充数字，但对于30000,30000的数组，直接爆零。,对于读入的n, x, y，先判断(x,y)在第几圈，再模拟圈内的数字。,螺旋方阵试题分析,如：n=4, (2,2)在第2圈，(3,1)在第1圈。 n=6，(4,5)在第2圈,圈数q=min(x, y, n-x+1, n-y+1 ),即目

21、标位置到四个边界距离的最小值,螺旋方阵试题分析,圈数q求出后，前q圈的数字总和很容易求出来。,对于任何一个方阵： 第1圈有4n-4个数; 第2圈有4(n-2)-4个数； 第3圈有4(n-4)-4个数； 第q圈有4(n-q(n-1)-4个数,螺旋方阵试题分析,前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)个数；,螺旋方阵试题分析,目标位置(i,j)到底在当前这一圈的第几个位置？ 如目标数26所在的位置(4,5)，在第2圈的什么位置？ 分两种情况： 1

22、）目标数(i,j)在上行或右行； i+j-2q+1 2）目标数(i,j)在下行或左行； 距离第一个数的距离 i+j-2q+1,螺旋方阵参考程序：,var n,i,j,q,ans:longint; function min(a,b:longint):longint; begin if ab then exit(a) else exit(b); end; begin readln(n,i,j); q:=min(i,min(j,min(n-i+1,n-j+1); if i=j then ans:=q*(4*(n-1)-4*q)+10*q-4*n-3+i+j else ans:=q*(4*n-4*q)

23、+2*q+1-i-j; writeln(ans); end.,计数问题 (noip2013普及组第一题),试计算在区间1到n的所有整数中，数字x（0 x9）共出现了多少次？例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，数字1出现了4次。 输入： 输入共1行，包含2个整数n、x，之间用一个空格隔开。输出： 输出共1行，包含一个整数，表示x出现的次数。 输入示例： 111 输出示例： 4 其他说明： 对于100%的数据，1n1,000,000，0 x9。,计数问题 试题分析,这道题入门难度，直接模拟。 循环1到n之间的所有数，对每个数的每位判断即可。,读入n,x; fo

24、r i=1 to n do k=i; while k的每一位j do if j=x then inc(ans); 输出ans;,计数问题 参考程序,这道题入门难度，直接模拟。 循环1到n之间的所有数，对每个数的每位判断即可。,var i,n,x,k,ans:longint; begin readln(n,x); ans:=0; for i:=1 to n do begin k:=i; while k0 do begin if k mod 10=x then inc(ans); k:=k div 10; end; end; writeln(ans); end.,寻宝 (noip2012普及组第二

25、题),传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下： 藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 x，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间（假定该房间的编号为 k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房间的指示牌

26、上写着 2，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。,寻宝 (noip2012普及组第二题),寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。 请帮助小明算出这个打开宝箱的密钥。 【输入】 第一行 2 个整数 N 和 M，之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼，M 表示除顶层外每层楼有 M 个房间。 接下来 N*M 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第

27、(i-1)*M+j 行表示第 i 层 j-1 号房间的情况（i=1, 2, , N；j=1, 2, ,M）。第一个整数表示该房间是否有楼梯通往上一层（0 表示没有，1 表示有），第二个整数表示指示牌上的数字。注意，从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。 最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从 0 开始）。,寻宝 (noip2012普及组第二题),【输出】 输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 20123取模的结果即可。 【输入输出样例】 treasure.in treasure.out 2 3 5

28、 1 2 0 3 1 4 0 1 1 5 1 2 1,寻宝 (noip2012普及组第二题),【输入输出样例说明】 第一层： 0 号房间，有楼梯通往上层，指示牌上的数字是 2； 1 号房间，无楼梯通往上层，指示牌上的数字是 3； 2 号房间，有楼梯通往上层，指示牌上的数字是 4； 第二层： 0 号房间，无楼梯通往上层，指示牌上的数字是 1； 1 号房间，有楼梯通往上层，指示牌上的数字是 5； 2 号房间，有楼梯通往上层，指示牌上的数字是 2； 小明首先进入第一层（底层）的 1 号房间，记下指示牌上的数字为 3，然后从这个房间开始，沿逆时针方向选择第 3 个有楼梯的房间 2 号房间进入，上楼后到

29、达第二层的 2 号房间，记下指示牌上的数字为 2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即 3+2=5，所以打开宝箱的密钥就是 5。,寻宝 试题分析,题目大意：n层楼，每层m个房间。每个房间有一个号码，楼梯。从底楼出发，如果该房间有楼梯，直接上楼，否则走到该层下个指定的房间。 将每一层第一个到达的房间号加起来就是答案。,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节： 1.房间号从0开始，所以读入时要注意；,r

30、eadln(n,m); for i=1 to n do for j=0 to m-1 do 读入楼梯和号码；,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节： 1.房间号从0开始，所以读入时要注意； 2.读入时统计每一层有多少个带楼梯的房间；,readln(n,m); for i=1 to n do for j=0 to m-1 do begin readln(stairi,j, numi,j); if stairi,j=1 then inc(sumi); end;,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节： 1.房

31、间号从0开始，所以读入时要注意； 2.读入时统计每一层有多少个带楼梯的房间； 3.理解“从这个房间开始按逆时针方向选择第 x 个有楼梯的房间”。假如当前房间没有楼梯，指示牌上的号为j：,while j0 do begin if stairi,k=1 then dec(j); if j0 then k:=(k+1) mod m; end;,寻宝 参考程序,var i,j,n,m,k,ans:longint; num:array0.10001,0.101 of longint; sum:array0.10001of longint; stair:array0.10001,0.101 of 0.1;

32、 begin readln(n,m); fillchar(sum,sizeof(sum),0); for i:=1 to n do for j:=0 to m-1 do begin readln(stairi,j,numi,j); if stairi,j=1 then inc(sumi); end; readln(k); ans:=0; for i:=1 to n do begin ans:=(ans+numi,k) mod 20123; numi,k:=numi,k mod sumi; if numi,k=0 then numi,k:=sumi;,j:=numi,k; while j0 do

33、 begin if stairi,k=1 then dec(j); if j0 then k:=(k+1) mod m; end; end; writeln(ans); end.,接水问题 (noip2010普及组第二题),学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。 现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水

34、。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它mn个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。,接水问题 (noip2010普及组第二题),输入 第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、wn，每两个整数之间用一个空格隔开，wi表示i 号同学的接水量。 输出 输出只有一行，1 个整数，表示接水所需的总时间。 样例输入： 5 3 4 4 1 2 1 样例输出： 4,接水问

35、题 试题分析,题目大意：n个人排队顺序接水，共m个水龙头。求接完水需要最少的秒数。 本题直接模拟即可。有的选手在考试中使用秒去枚举，结果严重超时。 对于每一个人， 选择这m个水龙头中接水量最小的去接。 最后输出这m个水龙头中接水量最大的。,接水问题 参考程序,var a:array0.10001of longint; s:array0.101of longint; n,m,i,j,k,ans,minn:longint; begin readln(n,m); for i:=1 to n do read(ai); fillchar(s,sizeof(s),0); for i:=1 to n do

36、begin minn:=9999999; for j:=1 to m do if sjans then ans:=si; writeln(ans); end.,三、字符串类试题,对于字符串、表达式的求解、 大整数的处理等等，我们经常采用字符串来处理。 字符串处理常见函数和过程： length()、delete() pos()、val()、str(),数字反转 (noip2011普及组第一题),给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（如：输入-380，输出-83）。 输入 输入共1行，一个整数

37、N。 输出 输出共1行，一个整数，表示反转后的新数。 样例输入 123 样例输出 321,数字反转 试题分析,方法1：直接降位取个位 降位：n div 10 取个位：n mod 10 注意删去末尾的0！ 缺点：数不能太大，容易溢出！,数字反转 试题分析,var n:longint; begin readln(n); if n0 do begin write(n mod 10); n:=n div 10; end; end; end.,数字反转 试题分析,方法2：字符串 注意1：负数的处理,if s1=- then begin write(-); delete(s,1,1); end;,数字反转

38、 试题分析,方法2：字符串 注意1：负数的处理 注意2：末尾0的处理：,len=length(s); while (slen=0) do dec(len); for i= len downto 1 do write(si);,数字反转 参考程序,var s:ansistring; i,len:longint; begin readln(s); if s1=- then begin write(-); delete(s,1,1); end; len:=length(s); while (slen=0)do dec(len); for i:=len downto 1 do write(si); e

39、nd.,统计单词个数 (noip2011普及组第二题),一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。,统计单词个数 (noip2011普及组第二题),输入格式 第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字

40、符串，其中只可能包含字母和空格，表示给定的文章。 输出格式 只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。,统计单词个数 (noip2011普及组第二题),样例输入1：Totobeornottobeisaquestion 样例输出1：20 样例输入2：toDidtheOttomanEmpireloseitspoweratthattime 样例输出2：-1【输入输出样例2说明】表示给定的单词to在文章中

41、没有出现，输出整数-1。 注释说明 1单词长度10。1文章长度1,000,000。,统计单词个数 试题分析,本题是简单的字符串处理。 读入单词和文章（字符串）后，可以把单词和文章全部转换成大写（或小写），然后循环在文章中对单词进行查找，找到就存储位置，并统计找到的次数。 转换成大写有两种方法： 方法1：利用ord()和chr()函数逐个字符转换： for i=1 to length(s) do if si=a then si:=chr(ord(si)-32); 方法2：利用upcase()函数直接转换： s=upcase(s);,统计单词个数 试题分析,本题还有一个问题需要处理： 查找的单词s

42、1只是文章s中某个单词的一部分，如： To DidtheOttomanEmpire 处理方法：读入单词s1后，在s1的两端各添加一个空格。 s1= + s1 + ,统计单词个数 参考程序,var s1,s:ansistring; i,p,len,ans:longint; begin readln(s1); /单词 readln(s); /文章 s1:= +upcase(s1)+ ; s:= +upcase(s)+ ; p:=-1; ans:=0; len:=length(s1); for i:=1 to length(s)-len+1 do if copy(s,i,len)=s1 then b

43、egin if p=-1 then p:=i-1; inc(ans); end; if p=-1 then write(p) else write(ans, ,p); end.,四、贪心类试题,从问题的某一个初始解出发，向给定的目标递推。推进的每一步不是依据某一固定的递推公式，而是做一个当时看似最佳的贪心选择，不断地将问题归纳为更小的相似的子问题，最终产生出一个全局最优解。,排座椅 (noip2008普及组第二题),上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接

44、耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。 请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。,排座椅 (noip2008普及组第二题),输入 输入的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。接

45、下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。输入数据保证最优方案的唯一性。 输出 输出共两行。第一行包含K个整数，a1a2aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、第aK行和第aK+1行之间要开辟通道，其中aiai+1，每两个整数之间用空格隔开（行尾没有空格）。第二行包含L个整数，b1b2bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、第bL列和第bL+1列之间要开辟通道，其中bibi+1，每两个整数之间用空格隔开（行尾没有

46、空格）。,排座椅 (noip2008普及组第二题),输入样例 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 输出样例 2 2 4,排座椅 试题分析,贪心。 题意：教室有m行n列，现在要划分k条横向通道，L条纵向的通道。交头接耳的学生位置xi,yi和pi,qi。怎么划分通道，使得上课时交头接耳的学生对数最少。 用rowi记录第i行与第i+1行之间有多少对交头接耳的； 用coli记录第i列与第i+1列有多少对交头接耳的。 将row从大到小排序，前k个即为要隔开的行；将col从大到小排序，前L个即为要隔开的列。,排座椅 试题分析,程序的框架： 读入m,n,k,L,d; For

47、i=1 to d 读入x,y,p,q; if x=p then inc(rowmin(x,p).value) else inc(colmin(y,q).value); 对数组row按row.value从大到小排序; 对于数组row1到rowk按row.no从小到大排序； 输出row1rowk; 对数组col按col.value从大到小排序; 对于数组col1到colL按col.no从小到大排序； 输出col1colL;,排座椅 参考程序,var m,n,t,k,L,d,i,j,x,y,p,q,maxx:longint; row,col,a:array0.1005 of longint; fun

48、ction min(x,y:longint):longint; begin if xy then exit(y) else exit(x); end; begin readln(m,n,k,L,d); fillchar(row,sizeof(row),0); fillchar(col,sizeof(col),0); for i:=1 to d do begin readln(x,y,p,q); if x=p then inc(colmin(y,q) else inc(rowmin(x,p); end; t:=0; while trowmaxx then maxx:=i; rowmaxx:=-1

49、; inc(t); end;,t:=0; while tcolmaxx then maxx:=i; colmaxx:=-1; inc(t); end; for i:=1 to m do if rowi=-1 then write(i, ); writeln; for i:=1 to n do if coli=-1 then write(i, ); writeln; end.,纪念品分组 (noip2007普及组第二题),元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并

50、且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。,纪念品分组 (noip2007普及组第二题),输入 包含n+2行: 第1行包括一个整数w，为每组纪念品价格之和的上眼=第2行为一个整数n，表示购来的纪念品的总件数G 第3-n+2行每行包含一个正整数Pi (5 = Pi = w3)w表示所对应纪念品的价格。 输出 仅一行，包含一个整数，ep最少的分组数目合,纪念品分组 (noip2007普及组第二题),样例输入：样例输出： 1006 9 90 20 20

51、30 50 60 70 80 90 100%的数据满足: 1 = n = 30000，80 = W = 200,纪念品分组 试题分析,算法：贪心 先按n件纪念品的价值进行排序，贪心策略是价值最小的与价值最大的为一组，这样分组是最少的。,纪念品分组 试题分析,算法：贪心 先按n件纪念品的价值进行排序，贪心策略是价值最小的与价值最大的为一组，这样分组是最少的。,纪念品分组 参考程序,var i,j,t,m,n,left,right,ans:longint; a:array0.30001of longint; begin readln(m,n); for i:=1 to n do readln(ai

52、); for i:=1 to n-1 do for j:=i+1 to n do if aiaj then begin t:=ai;ai:=aj;aj:=t;end; ans:=0; left:=1;right:=n; while left=right do begin if aleft+aright=m then begin inc(left);dec(right);end else dec(right); inc(ans); end; if left=right then inc(ans); writeln(ans); end.,六、简单动态规划类试题,动态规划是解决多阶段决策最优化问题的

53、一种思想方法。一般我们从初始阶段出发，枚举每个阶段的所有状态，在状态转移的过程中，我们需要决策。根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。 普及组一般考查的动态规划：01背包，最长上升子序列，一些简单的线性动规。,守望者的逃离 (noip2007普及组第三题),恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，岛上的所有人都会遇难：守望者的跑步速

54、度，为17m/s， 以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。,守望者的逃离 (noip2007普及组第三题),输入 输入文件escape.in仅

55、一行，包括空格隔开的三个非负整数M，S，T。 输出 输出文件escape.out包含两行: 第1行为字符串“Yes”或“No” (区分大小写)，即守望者是否能逃离荒岛。 第2行包含一个整数，第一行为“Yes” (区分大小写）时表示守望着逃离荒岛的最短时间 第一行为“No” (区分大小写)时表示守望者能走的最远距离。 样例输入 39 200 4 样例输出 No 197 提示 100%的数据满足: 1 = T = 300000,0 = M=1000 1 =S = 108,守望者的逃离 试题分析,题目大意：一个人在t时间内是否能够行走的s米的距离，行走的方式有两种： 1. 使用魔法（每秒60米），缺

56、点每秒耗费10点魔法值； 2. 跑步（每秒17米）。,守望者的逃离 试题分析,算法：贪心 + 背包型动态规划,贪心的策略：有魔法的情况下，肯定先用魔法跑，这样跑的快！ 如果魔法不够，那么我们利用背包模型，只有在下列两种选择中选择其中一种： 1、使用魔法 2、跑步,守望者的逃离 试题分析,令fi表示前i秒利用魔法行走的距离； dpi表示利用魔法或者跑步行走的最大距离。,很容易求出1到t的fi的值：,for i=1 to t do if magic=10 then magic=magic-10; fi=fi-1+60; else magic=magic+4; fi=fi-1; ,守望者的逃离 试题

57、分析,下面求dpi，01背包： dpi=max(dpi-1+17, fi);,守望者的逃离 参考程序,小朋友的数字 (noip2013普及组第三题),有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p

58、取模后输出。,小朋友的数字 (noip2013普及组第三题),输入格式 第一行包含两个正整数 n、p,之间用一个空格隔开。第二行包含 n 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。 输出格式 输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。 样例输入1 5 997 1 2 3 4 5 样例输出1 21,小朋友的数字 试题分析,主要考查选手的语文理解能力，关键把题读懂。 需要理解的两个值： 特征值：前面连续若干个数字和的最大值； 分数：前面每个小朋友的分数+特征值的最大值,小朋友的数字 试题分析,算法：动态规划 + 贪心,求小朋友的特征值需要求最大子段和。,for i=1 to n do dpi=max( dpi-1+ai, ai );,每个小朋友的特征值ti: for i=1 to n do dpi=max( dpi-1+ai, ai ); ti=max(ti-1, dpi); ,小朋友的数字 试题分析,算法：动态规划 + 贪心,求小朋友的分数需要贪心：如果第一个小朋友的分数+特征值为负数，那么后面所有小朋友的分数=第一个小朋友的分数+特征值，否则=前一个小朋友的分数+特征值。,for i=