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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NOIP,普及组历届试题分析,安徽省六安第一中学 江家和,1,引言,noip,复赛的知识面,很,广泛，对选手的综合素质考核要求,更,为严格，难度和分数的阶梯层次,更,趋科学合理，对信息学活动的推动力和社会公信力,更,为增强。,2,NOIP普及组题型分布,题型,题目,枚举,扫雷游戏,(2015p2),、珠心算测验,(2014p1),数字统计,(2010p1),、比例简化,(2014p2),模拟,金币,(2015p1),、,螺旋方阵,(2014p3),、计数问题,(2013p1),、,寻宝,(2012p2),、接水问题,(2010p2),字符串,数字反转,(2011p1),、统计单词个数,(2011p2),ISBN,号码,(2008p1),、乒乓球,(2003p1),贪心,排座椅,(2008p2),、纪念品分组,(2007p2),3,NOIP普及组题型分布,题型,题目,简单,动态规划,子矩阵,(2014p4),、小朋友的数字,(2013p3),摆花,(2012p3),、导弹拦截,(2010p3),道路游戏,(2009p4),、传球游戏,(2008p3),守望者的逃离,(2007p3),、开心的金明,(2006p2),采药,(2005p3),、数字游戏,(2003p2),数学,/,数论,质因数分解,(2012p1),、细胞分裂,(2009p3),Hanoi双塔问题,(2007p4),、数列,(2006p4),循环,(2005p4),、栈,(2003p3,卡特兰数,),数据结构,表达式求值,(2013p2),、表达式的值,(2011p4),FBI,树,(2004p1),、求先序排列,(2001p2),图论,（提高组）,车站分级,(2013p4,拓扑排序,),文化之旅,(2012p4,floyd,算法,),4,一、枚举类试题,枚举法的基本思想是根据提出的问题枚举所有可能的解，并用问题给定的条件检验哪些解是需要的，哪些解是不需要的。能使条件成立，即为其解。,枚举法其实是最简单的搜索算法。,5,珠心算测验(noip2014普及组第一题),珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。,某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？最近老师出了一些测验题，请你帮忙求出答案。,6,珠心算测验(noip2014普及组第一题),【,输入,】,输入共两行，第一行包含一个整数,n,，表示测试题中给出的正整数个数。,第二行有,n,个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。,【,输出,】,输出共一行，包含一个整数，表示测验题答案。,【,样例输入,】【,样例输出,】,4 2,1 2 3 4,对于,100%,的数据，,3n100,测验题给出的正整数大小不超过,10,000,。,7,试题分析,题意大意：给你,n,个数，在这,n,个数中，找到满足,A+B=C,的,C,的个数，,注意不是这个等式的个数,。,样例中，,1,2,3,4,有,1+2=3,，,1+3=4,两个。,由于本题数据规模,n=a/b)then,if,i/j-a/b,=a/b)then,if,i/j-a/b,minn,then,begin,minn,:=,i/j-a/b,;,ansx,:=i;,ansy,:=j;,end;,writeln(ansx,ansy,);,end.,26,二、模拟类试题,有些问题，我们很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。,所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。,27,金币(noip2015普及组第一题),国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币,；这种工资发放模式会一直这样延续下去：当连续,N,天每天收到,N,枚金币后，骑士会在之后的连续,N+1,天里，每天收到,N+1,枚金币。请计算在前,K,天里，骑士一共获得了多少金币。,输入格式：输入文件只有,1,行，包含一个正整数,K,，表示发放金币的天数。,输出格式：输出文件只有,1,行，包含一个正整数，即骑士收到的金币数。,输入输出样例,输入样例：,1000,输出样例：,29820,28,试题分析,本题直接,模拟,即可。定义变量时注意不要混淆了：,i,代表枚举的天数，,t,代表连续的天数，也是每天收到的金币数，,s,收到的金币总数。,读入天数,k;,i=1;t=1;s=0;,while ik then break;,t=t+1;,输出,s;,29,参考程序：,var i,j,k,s,t:longint;,begin,readln(k);,i:=1;t:=1;s:=0;,while ik then break;,end;,inc(t);,end;,writeln(s);,end.,30,螺旋方阵(noip2014普及组第三题),一个,n,行,n,列的螺旋矩阵可由如下方法生成：,从矩阵的左上角,(,第,1,行第,1,列,),出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入,1,2,3,.,，便构成了一个螺旋矩阵。,现给出矩阵大小,n,以及,i,和,j,，请你求出该矩阵中第,i,行第,j,列的数是多少。,下图是一个,n=4,时的螺旋矩阵。,31,螺旋方阵(noip2014普及组第三题),输入格式,输入共一行，包含三个整数,n,，,i,，,j,，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。,输出格式,输出共一行，包含一个整数，表示相应矩阵中第,i,行第,j,列的数。,样例输入：,4 2 3,样例输出：,14,对于,50%,的数据，,1 n 100;,对于,100%,的数据，,1 n 30,000,，,1 i n,，,1 j n,。,32,螺旋方阵试题分析,本题首先让我们想到传统的模拟，从,1,1,开始往数组中填充数字，但对于,30000,30000,的数组，直接爆零。,对于读入的,n,x,y,，先判断,(x,y),在第几圈，再模拟圈内的数字。,33,螺旋方阵试题分析,如：,n=4,(2,2),在第,2,圈，,(3,1),在第,1,圈。,n=6,，,(4,5),在第,2,圈,圈数,q=min(x,y,n-x+1,n-y+1,),即目标位置到四个边界距离的最小值,34,螺旋方阵试题分析,圈数,q,求出后，前,q,圈的数字总和很容易求出来。,对于任何一个方阵：,第,1,圈有,4n-4,个数,;,第,2,圈有,4(n-2)-4,个数；,第,3,圈有,4(n-4)-4,个数；,第,q,圈有,4(n-q(n-1)-4,个数,35,螺旋方阵试题分析,前,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),个数；,36,螺旋方阵试题分析,目标位置,(i,j),到底在当前这一圈的第几个位置？,如目标数,26,所在的位置,(4,5),，在第,2,圈的什么位置？,分两种情况：,1,）目标数,(i,j),在上行或右行；,i+j-2q+1,2,）目标数,(i,j),在下行或左行；,距离第一个数的距离,i+j-2q+1,37,螺旋方阵参考程序：,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 i0 do,begin,if k mod 10=x then inc(ans);,k:=k div 10;,end;,end;,writeln(ans);,end.,41,寻宝(noip2012普及组第二题),传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：,藏宝楼共有,N+1,层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有,N,层，每层,M,个房间，这,M,个房间围成一圈并按逆时针方向依次编号为,0,，,，,M-1,。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字,x,，表示从这个房间开始按逆时针方向选择第,x,个有楼梯的房间（假定该房间的编号为,k,），从该房间上楼，上楼后到达上一层的,k,号房间。比如当前房间的指示牌上写着,2,，则按逆时针方向开始尝试，找到第,2,个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。,42,寻宝(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,开始）。,43,寻宝(noip2012普及组第二题),【,输出,】,输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对,20123,取模的结果即可。,【,输入输出样例,】,treasure.in treasure.out,2 3 5,1 2,0 3,1 4,0 1,1 5,1 2,1,44,寻宝(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,。,45,寻宝 试题分析,题目大意：,n,层楼，每层,m,个房间。每个房间有一个号码，楼梯。从底楼出发，如果该房间有楼梯，直接上楼，否则走到该层下个指定的房间。,将每一层第一个到达的房间号加起来就是答案。,46,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：,1.,房间号从,0,开始，所以读入时要注意；,readln(n,m);,for i=1 to n do,for j=0 to m-1 do,读入楼梯和号码；,47,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：,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;,48,寻宝 试题分析,我们把每一层楼看成一个圈，完全模拟一下小明的行走路线即可。注意细节：,1.,房间号从,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;,49,寻宝 参考程序,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;,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,begin,if,stairi,k,=1 then,dec(j,);,if j0 then k:=(k+1)mod m;,end;,end;,writeln(ans,);,end.,50,接水问题(noip2010普及组第二题),学校里有一个水房，水房里一共装有,m,个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为,1,。,现在有,n,名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从,1,到,n,编号，,i,号同学的接水量为,wi,。接水开始时，,1,到,m,号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学,j,完成其接水量要求,wj,后，下一名排队等候接水的同学,k,马上接替,j,同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即,j,同学第,x,秒结束时完成接水，则,k,同学第,x+1,秒立刻开始接水。若当前接水人数,n,不足,m,，则只有,n,个龙头供水，其它,mn,个龙头关闭。,现在给出,n,名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。,51,接水问题(noip2010普及组第二题),输入,第,1,行,2,个整数,n,和,m,，用一个空格隔开，分别表示接水人数和龙头个数。,第,2,行,n,个整数,w1,、,w2,、,、,wn,，每两个整数之间用一个空格隔开，,wi,表示,i,号同学的接水量。,输出,输出只有一行，,1,个整数，表示接水所需的总时间。,样例输入：,5 3,4 4 1 2 1,样例输出：,4,52,接水问题 试题分析,题目大意：,n,个人排队顺序接水，共,m,个水龙头。求接完水需要最少的秒数。,本题直接,模拟,即可。有的选手在考试中使用秒去枚举，结果严重超时。,对于每一个人，,选择这,m,个水龙头中接水量最小的去接,。,最后输出这,m,个水龙头中接水量最大的。,53,接水问题 参考程序,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,begin,minn,:=9999999;,for j:=1 to m do,if,sj,ans,then,ans,:=,si,;,writeln(ans,);,end.,54,三、字符串类试题,对于字符串、表达式的求解、大整数的处理等等，我们经常采用字符串来处理。,字符串处理常见函数和过程：,length(),、,delete(),pos(),、,val(),、,str(),55,数字反转(noip2011普及组第一题),给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（如：输入,-380,，输出,-83,）。,输入,输入共,1,行，一个整数,N,。,输出,输出共,1,行，一个整数，表示反转后的新数。,样例输入,123,样例输出,321,56,数字反转 试题分析,方法,1,：直接降位取个位,降位：,n div 10,取个位：,n mod 10,注意删去末尾的,0,！,缺点：数不能太大，容易溢出！,57,数字反转 试题分析,var,n:longint,;,begin,readln(n,);,if n0 do,begin,write(n,mod 10);,n:=n div 10;,end;,end;,end.,58,数字反转 试题分析,方法,2,：字符串,注意,1,：负数的处理,if s1=-then,begin,write(-);,delete(s,1,1);,end;,59,数字反转 试题分析,方法,2,：字符串,注意,1,：负数的处理,注意,2,：末尾,0,的处理：,len=length(s);,while(slen=0)do dec(len);,for i=len downto 1 do write(si);,60,数字反转 参考程序,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,);,end.,61,统计单词个数(noip2011普及组第二题),一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例,1,），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例,2,）。,62,统计单词个数(noip2011普及组第二题),输入格式,第,1,行为一个字符串，其中只含字母，表示给定单词；第,2,行为一个字符串，其中只可能包含字母和空格，表示给定的文章。,输出格式,只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从,0,开始）；如果单词在文章中没有出现，则直接输出一个整数,-1,。,63,统计单词个数(noip2011普及组第二题),样例输入,1,：,Totobeornottobeisaquestion,样例输出,1,：,20,样例输入,2,：,toDidtheOttomanEmpireloseitspoweratthattime,样例输出,2,：,-1【,输入输出样例,2,说明,】,表示给定的单词,to,在文章中没有出现，输出整数,-1,。,注释说明,1,单词长度,10,。,1,文章长度,1,000,000,。,64,统计单词个数 试题分析,本题是简单的字符串处理。,读入单词和文章（字符串）后，可以把单词和文章全部转换成大写（或小写），然后循环在文章中对单词进行查找，找到就存储位置，并统计找到的次数。,转换成大写有两种方法：,方法,1,：,利用,ord(),和,chr(),函数逐个字符转换：,for i=1 to length(s)do,if si=a then si:=chr(ord(si)-32);,方法,2,：,利用,upcase(),函数直接转换：,s=upcase(s);,65,统计单词个数 试题分析,本题还有一个问题需要处理：,查找的单词,s1,只是文章,s,中某个单词的一部分，如：,To,DidtheOttomanEmpire,处理方法：读入单词,s1,后，在,s1,的两端各添加一个空格。,s1=+s1+,66,统计单词个数 参考程序,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,begin,if p=-1 then p:=i-1;,inc(ans,);,end;,if p=-1 then,write(p,),else,write(ans,p);,end.,67,四、贪心类试题,从问题的某一个初始解出发，向给定的目标递推。推进的每一步不是依据某一固定的递推公式，而是做一个当时看似最佳的贪心选择，不断地将问题归纳为更小的相似的子问题，最终产生出一个全局最优解。,68,排座椅(noip2008普及组第二题),上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的,D,对同学上课时会交头接耳。同学们在教室中坐成了,M,行,N,列，坐在第,i,行第,j,列的同学的位置是（,i,，,j,），为了方便同学们进出，在教室中设置了,K,条横向的通道，,L,条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。,请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。,69,排座椅(noip2008普及组第二题),输入,输入的第一行，有,5,个用空格隔开的整数，分别是,M,，,N,，,K,，,L,，,D,（,2=N,，,M=1000,，,0=KM,，,0=LN,，,D=2000,）。接下来,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,列之间要开辟通道，其中,biy 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 t,rowmaxx,then,maxx,:=i;,rowmaxx,:=-1;,inc(t,);,end;,t:=0;,while t,colmaxx,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.,74,纪念品分组(noip2007普及组第二题),元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。,你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。,75,纪念品分组(noip2007普及组第二题),输入,包含,n+2,行,:,第,1,行包括一个整数,w,，为每组纪念品价格之和的上眼,=,第,2,行为一个整数,n,，表示购来的纪念品的总件数,G,第,3-n+2,行每行包含一个正整数,Pi(5=Pi=w3)w,表示所对应纪念品的价格。,输出,仅一行，包含一个整数，,ep,最少的分组数目合,76,纪念品分组(noip2007普及组第二题),样例输入：样例输出：,1006,9,90,20,20,30,50,60,70,80,90,100%,的数据满足,:1=n=30000,，,80=W,aj,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.,80,六、简单动态规划类试题,动态规划是解决多阶段决策最优化问题的一种思想方法。一般我们从初始,阶段,出发，枚举每个阶段的所有,状态,，在状态转移的过程中，我们需要,决策,。根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。,普及组一般考查的动态规划：,01,背包，最长上升子序列，一些简单的线性动规。,81,守望者的逃离(noip2007普及组第三题),恶魔猎手尤迫安野心勃勃,.,他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀,.,被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，岛上的所有人都会遇难：守望者的跑步速度，为,17m/s,，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在,1s,内移动,60m,，不过每次使用闪烁法术都会消耗魔法值,10,点。守望者的魔法值恢复的速度为,4,点,/s,，只有处在原地休息状态时才能恢复。,现在已知守望者的魔法初值,M,，他所在的初始位置与岛的出口之间的距离,S,，岛沉没的时间,T,。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意,:,守望者跑步、闪烁或休息活动均以秒,(s),为单位。且每次活动的持续时间为整数秒。距离的单位为米,(m),。,82,守望者的逃离(noip2007普及组第三题),输入,输入文件,escape.in,仅一行，包括空格隔开的三个非负整数,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=10 then,magic=magic-10;,fi=fi-1+60;,else,magic=magic+4;,fi=fi-1;,86,守望者的逃离 试题分析,下面求,dpi,，,01,背包：,dpi=max(dpi-1+17,fi);,87,守望者的逃离 参考程序,var,i,m,s,t,ok:longint,;,f,dp:array0.300001 of,longint,;,function,max(x,y:longint):longint,;,begin if xy then,exit(x,)else,exit(y,);end;,begin,readln(m,s,t,);,fillchar(f,sizeof(f),0);,fillchar(dp,sizeof(dp),0);,ok:=0;,for i:=1 to t do,begin,if m=10 then,begin,m:=m-10;,fi,:=fi-1+60;,end else begin,m:=m+4;,fi,:=fi-1;,end;,dpi,:=max(dpi-1+17,fi);,if,dpi,=s then,begin,writeln(Yes,);,writeln(i,);,ok:=1;,break;,end;,end;,if ok=0 then begin,writeln(No);writeln(dpt);end,;,end.,88,小朋友的数字(noip2013普及组第三题),有,n,个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面,(,包括他本人,),的小朋友中连续若干个,(,最少有一个,),小朋友手上的数字之和的最大值。作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的,:,第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中,(,不包括他本人,),小朋友分数加上其特征值的最大值。请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对,p,取模后输出。,89,小朋友的数字(noip2013普及组第三题),输入格式,第一行包含两个正整数,n,、,p,之间用一个空格隔开。第二行包含,n,个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。,输出格式,输出只有一行,包含一个整数,表示最大分数对,p,取模的结果。,样例输入,1,5 997,1 2 3 4 5,样例输出,1,21,90,小朋友的数字 试题分析,主要考查选手的语文理解能力，关键把题读懂。,需要理解的两个值：,特征值：前面连续若干个数字和的最大值；,分数：前面每个小朋友的分数,+,特征值的最大值,91,小朋友的数字 试题分析,算法：,动态规划,+,贪心,求小朋友的特征值需要求最大子段和。,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);,92,小朋友的数字 试题分析,算法：,动态规划,+,贪心,求小朋友的分数需要贪心：如果第一个小朋友的分数,+,特征值为负数，那么后面所有小朋友的分数,=,第一个小朋友的分数,+,特征值，否则,=,前一个小朋友的分数,+,特征值。,for i=2 to n do,if te1+fen10 then feni=te1+fen1,else feni=tei-1+feni-1;,93,采药（noip2005普及组第三题）,辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”,94,采药（noip2005普及组第三题）,输入格式：第一行有两个整数,T,和,M,，,T,代表总共能够用来采药的时间，,M,代表山洞里的草药的数目。接下来的,M,行每行包括两个在,1,到,100,之间（包括,1,和,100,）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式：一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。,输入样例：,70 371 10069 11 2,输出样例：,3,（,1=T=1000,）（,1=M y then,exit(x,)else,exit(y);end,;,begin,readln(t,n,);,for i:=1 to n do,readln(wi,vi,);,for i:=1 to n do,for j:=t,downto,wi,do,dpj,:=,max(dpj,dpj-wi+vi,);,writeln(dpt,);,end.,98,开心的金明（noip2006普及组第二题）,金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过,N,元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的,N,元。于是，他把每件物品规定了一个重要度，分为,5,等：用整数,15,表示，第,5,等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过,N,元（可以等于,N,元）的前提下，使每件物品的价格与重要度的乘积的总和最大。,设第,j,件物品的价格为,vj,，重要度为,wj,，共选中了,k,件物品，编号依次为,j1,，,j2,，,，,jk,，则所求的总和为：,vj1*wj1+vj2*wj2+vjk*wjk,。（其中*为乘号）,请你帮助金明设计一个满足要求的购物单。,99,开心的金明（noip2006普及组第二题）,输入,输入文件,happy.in,的第,1,行，为两个正整数，用一个空格隔开：,N m,（其中,N,（,30000,）表示总钱数，,m,（,25,）为希望购买物品的个数。）,从第,2,行到第,m+1,行，第,j