NOIP2016普及组复赛试题讲解(c++版本).pptx

NOIP2016普及组复赛题解,NOIP2016普及组C+,-2-,第1题“买铅笔”简述,P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋友们发礼物。现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱?【分析】送分题，数据量少，直接模拟即可。当然，“小心撑得万年船”，“大意失荆州”,-3-,例程C+,#includeusingnamespacestd;intmain()longn,i,s,mins=100000000;/n铅笔数量，i循环变量，s费用，mins最小费用longc4,p4;/三种铅笔的数量和价格cinn;for(i=1;icipi;if(n%ci=0)s=n/ci*pi;/正好整包elses=(n/ci+1)*pi;/有多余，再来一包if(minss)mins=s;/判断那种买法最省钱coutdate1date2;/输入起始结束日期for(i=1;i=12;i+)m=i%10*10+i/10;/1-12月份倒置之后的值t=msi;for(j=1;j=date1,-8-,确定解题思路（解法2）,如果从日期入手，一天一天往上加，每一天都要判断是不是合法的日期，是不是回文。容易出错，遇到极限数据还会超时题目里还有更重要的一点是“回文”位数是确定的，八位，很容易“组合”例如：2014，可以组成20144102我们只要判断20144102是不是合法的日期就可以了就算年份的范围是10009999，也只要计算9000次就可以了,-9-,程序框架,输入数据fori=day_startdiv10000/取年份=day_enddiv10000/循环起始到结束年份if（check(i)）/判断i年对应的日期是否符合要求特别注意：还要判断这个日期是否在范围内,-10-,第3题“海港”简述,小K按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti(单位：秒)，船上的乘客数量ki，以及每名乘客的国籍x(i,1),x(i,2),，x(i,k)。小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。形式化地讲，你需要计算n条信息。对于输出的第i条信息，你需要统计满足ti-86400tp=ti的船只p，在所有的x(p,j)中，总共有多少个不同的数输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。,-11-,暴力算法（预计分数70分）,h100001;hx表示国籍为x的乘客到港的最新时间。初始值为-86400.sum100001；sum1-n表示1-n个艘船到达海港对应的国籍数量。每一艘船到达海港，更新对应国籍乘客的到港时间数组h统计所有国籍的到港时间是否在24小时内，t为当前时间，t-hx86400，表示X国籍满足条件。时间复杂度：O(kt+n*x),-12-,确定解题思路,题目明确告诉我们，要计算的是中间的一段时间的统计结果。从数据结构的角度看，是“队列”：先进先出所有ki之和=300000，也就是总人数少于30万队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度O(kt)如何统计“总共有多少个不同的数”呢？1n;for(i=1;itiki;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;return0;,-15-,第4题“魔法阵”简述,大魔法师认为，当且仅当四个编号为a,b,c,d的魔法物品满足XaXbXcXd，Xb-Xa=2(Xd-Xc)，并且Xb-Xa9xxndiv9也就是说，CD的长度不会超过全长的九分之一,-18-,确定解题思路2,乘法原理：如果魔法值为A的物品有Ya个，B的有Yb个，C的有Yc个，那么，D中的一个物品作为D物品的次数是多少呢？根据乘法原理，次数=YaYbYc对于A,B,C,D的做法是一样的,-19-,确定解题思路3,数据范围：1=n=150001=mnm;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+a