NOIP2016普及组复赛试题讲解(c++版本)(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,-,*,-,2017.07.28,试题分析,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,NOIP2016,普及组复赛题解,NOIP2016,普及组,C+,借鉴百度文库,PASCAL,版本：,见，,P,老师决定只买同一种包装的铅笔。,商店不允许将铅笔的包装拆开，因此,P,老师可能需要购买超过,n,支铅笔才够给小朋 友们发礼物。,现在,P,老师想知道，在商店每种包装的数量都足够的情况下，要买够至少,n,支铅笔最少需要花费多少钱,?,【,分析,】,送分题，数据量少，直接模拟即可当然，,“,小心撑得万年船,”,，,“,大意失荆州,”,2,例程,C+,#include,using namespace std;,int main(),long n,i,s,mins=100000000;,/n,铅笔数量，,i,循环变量，,s,费用，,mins,最小费用,long c4,p4;/,三种铅笔的数量和价格,cinn;,for(i=1;icipi;,if(n%ci=0)s=n/ci*pi;/,正好整包,else s=(n/ci+1)*pi;/,有多余，再来一包,if(minss)mins=s;/,判断那种买法最省钱,coutdate1date2;/,输入起始结束日期,for(i1;i=12;i+),m=i%10*10+i/10;/1-12,月份倒置之后的值,t=msi;,for(j=1;j=date1&y=date2),sum+;/,判断这个日期在不在查询范围内,coutsumendl;,return 0;,7,确定解题思路（解法,2,）,如果从日期入手，一天一天往上加，每一天都要判断是不是合法的日期，是不是回文。容易出错，遇到极限数据还会超时,题目里还有更重要的一点是,“,回文,”,位数是确定的，八位，很容易,“,组合,”,例如：,2014,，可以组成,2014,4102,我们只要判断,2014,4102,是不是合法的日期就可以了,就算年份的范围是,10009999,，也只要计算,9000,次就可以了,8,程序框架,输入数据,for i=day_start div 10000 /,取年份,=day_end div 10000 /,循环起始到结束年份,if,（,check(i),）,/,判断,i,年对应的日期是否符合要求,特别注意：还要判断这个日期是否在,范围,内,9,第,3,题,“,海港,”,简述,小,K,按照时间记录下了到达海港的每一艘船只情况；对于第,i,艘到达的船，他记录了这艘船到达的时间,t,i,(,单位：秒,),，船上的乘客数量,k,i,，以及每名乘客的国籍,x(i,1),x(i,2),，,x(i,k),。,小,K,统计了,n,艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的,24,小时,(24,小时,=86400,秒）内所有乘船到达的乘客来自多少个不同的国家。,形式化地讲，你需要计算,n,条信息。对于输出的第,i,条信息，你需要统计满足,ti-86400 tp=ti,的船只,p,，在所有的,x(p,j),中，总共有多少个不同的数,输出,n,行，第,i,行输出一个整数表示第,i,艘船到达后的统计信息。,10,暴力算法（预计分数,70,分）,h100001;hx,表示国籍为,x,的乘客到港的最新时间。初始值为,-86400.,sum 100001,；,sum 1-n,表示,1-n,个艘船到达海港对应的国籍数量。,每一艘船到达海港，更新对应国籍乘客的到港时间数组,h,统计所有国籍的到港时间是否在,24,小时内，,t,为当前时间，,t-hx86400,，表示,X,国籍满足条件。,时间复杂度：,O(k,t,+n*x),11,确定解题思路,题目明确告诉我们，要计算的是中间的一段时间的统计结果。,从数据结构的角度看，是,“,队列,”,：先进先出,所有,ki,之和,=300000,，也就是总人数少于,30,万,队列中记录时间和国籍，到达的入队，超过,86400,秒的出队，时间复杂度,O(k,t,),如何统计,“,总共有多少个不同的数,”,呢？,1=X,i,j,n;,for(i=1;itiki;,for(j=1;j=ki;j+)for(j=1;jxi;,qttail=ti;,qxtail=xi;,if(hsxi=0)cnt+;,hsxi+;,tail+;,tic=ti-86400;,while(qthead=tic),xi=qxhead;,hsxi-;,if(hsxi=0)cnt-;,head+;,coutcntendl;,return 0;,14,第,4,题,“,魔法阵,”,简述,大魔法师认为，当且仅当四个编号为,a,b,c,d,的魔法物品满足,Xa Xb Xc Xd,，,Xb-Xa=2(Xd-Xc),，,并且,Xb-Xa(Xc-Xb)/3,时，,这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的,A,物品，,B,物品，,C,物品，,D,物品。,现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的,A,物品出现的次数，作为,B,物品的次数，作为,C,物品的次数，和作为,D,物品的次数。,15,确定解题思路,【,分析,】,压轴题，当然要难,这题几乎是个数学题,首先要会画,“,线段图,”,其次，,“,加法原理,”“,乘法原理,”,要熟练,最后，是,“,胆大心细,”,编程能力,16,确定解题思路,1,画,“,线段图,”,Xa Xb Xc Xd,Xb-Xa=2(Xd-Xc),Xb-Xa(Xc-Xb),3 Xc-Xb6,x,AD=AB+BC+CD 9,x x,n div 9,也就是,说，CD,的长度不会超过全长的九分之一,17,确定解题思路,2,乘法原理：,如果魔法值为,A,的物品有,Ya,个，,B,的有,Yb,个，,C,的有,Yc,个，那么，,D,中的一个物品作为,D,物品的次数是多少呢？,根据乘法原理，次数,=YaYbYc,对于,A,B,C,D,的做法是一样的,18,确定解题思路,3,数据范围：,1=n=15000 1=m=40000,直接求解，连,O(n,2,),的算法都不能用,极限的情况下,n=15000,，,m=40000,，说明有很多数据是重复的，可以合并,采用,“,桶,”,来处理，把数据范围降到,n=15000,加上,x,nm;,for(i=1;isi;,fsi+;,for(i=1;i=n/9;i+),ad=9*i+1;,y=0;,for(j=ad+1;j=1;j-),y+=fj+ac*fj+ac+i;,faj=faj+y*fj+2*i;,fbj+2*i=fbj+2*i+y*fj;,for(i=1;i=m;i+),coutfasi fbsi fcsi fdsiendl;,return 0;,21,BYE,The END,温馨提示：,本题借鉴了他人的资料,原文,PASCAL,版，现在修改为,C+,版本，原文地址如下：,