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

NOIP2016 普及组复赛题解,NOIP2016普及组C+,借鉴百度文库PASCAL版本： ,- 2 -,第1题 “买铅笔”简述,P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋 友们发礼物。 现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱? 【分析】送分题，数据量少，直接模拟即可。 当然，“小心撑得万年船”，“大意失荆州”,- 3 -,例程 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;/判断那种买法最省钱 coutmins; return 0; ,- 4 -,第2题 “回文日期”简述,牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月 份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。 牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。 一个8位数字是回文的，当且仅当从左向右读和从右向左是相同的 例如： 2016年11月19日，表示为20161119，它不是回文的 2010年1月2日，表示为20100102，它是回文的。 求：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。,- 5 -,确定解题思路,一年是365天，如果闰年是366天。月日构成的数字最多只有366个。 第一步：构造出所有的日期（后四位） 第二步：利用回文的规则，构造出相应的年份 第三步：判断这个年份和日期在不在区间内 例如：8月15日，日期写成0815 对应回文的年份是：5180年 判断51800815这一天在不在（指定的起始日期）到（指定的终止日期）之间 程序时间复杂度为O(366),- 6 -,主程序,#include using namespace std; int main() long i,j,y,m,d,t,date1,date2,sum=0; /i,j循环变量，y对应日期,m月倒置的数值,d日倒置的数值 long ms13=0,31,29,31,30,31,30,31,31,30,31,30,31; cindate1date2;/输入起始结束日期 for (i=1;i=12;i+) m=i%10*10+i/10;/1-12月份倒置之后的值 t=msi; for (j=1;j=t;j+),- 7 -,主程序,d=j%10*10+j/10;/1-t日倒置之后的值 y=(d*100+m)*10000+i*100+j;/对应回文的日期 if(y=date1 ,- 8 -,确定解题思路（解法2）,如果从日期入手，一天一天往上加，每一天都要判断是不是合法的日期，是不是回文。容易出错，遇到极限数据还会超时 题目里还有更重要的一点是“回文” 位数是确定的，八位，很容易“组合” 例如：2014，可以组成 20144102 我们只要判断20144102是不是合法的日期就可以了 就算年份的范围是 10009999，也只要计算9000次就可以了,- 9 -,程序框架,输入数据 for i=day_start div 10000 / 取年份 =day_end div 10000 /循环起始到结束年份 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 - 86400 tp = ti的船只p，在所有的x(p,j)中，总共有多少个不同的数 输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。,- 11 -,暴力算法（预计分数70分）,h100001;hx表示国籍为x的乘客到港的最新时间。初始值为-86400. sum 100001；sum 1-n表示1-n个艘船到达海港对应的国籍数量。 每一艘船到达海港，更新对应国籍乘客的到港时间数组h 统计所有国籍的到港时间是否在24小时内，t为当前时间，t-hx86400，表示X国籍满足条件。 时间复杂度：O(kt+n*x),- 12 -,确定解题思路,题目明确告诉我们，要计算的是中间的一段时间的统计结果。 从数据结构的角度看，是“队列”：先进先出 所有 ki之和=300000，也就是总人数少于30万 队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度 O(kt) 如何统计“总共有多少个不同的数” 呢？ 1=Xi,j=100000 ，当然用Hash (桶),- 13 -,数据结构,队列：用数组qt：时间，qx：国籍 int qt300005, qx300005; 头指针: head，尾指针：tail Hash表： int hs 100005;,- 14 -,参考程序,#include #include using namespace std; int const maxn=300005; int qtmaxn,qxmaxn; int hs100005; int head=1,tail=1,n,i,j,ti,tic,ki,xi,cnt=0; int main() memset(hs,0,sizeof(hs); cinn; 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; ,- 15 -,第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物品的次数。,- 16 -,确定解题思路,【分析】压轴题，当然要难 这题几乎是个数学题 首先要会画“线段图” 其次，“加法原理”“乘法原理”要熟练 最后，是“胆大心细”编程能力,- 17 -,确定解题思路1,画“线段图” Xa6x AD=AB+BC+CD 9x x n div 9 也就是说，CD的长度不会超过全长的九分之一,- 18 -,确定解题思路2,乘法原理： 如果魔法值为A的物品有Ya个，B的有Yb个，C的有Yc个，那么，D中的一个物品作为D物品的次数是多少呢？ 根据乘法原理，次数=YaYbYc 对于A,B,C,D的做法是一样的,- 19 -,确定解题思路3,数据范围：1=n=15000 1=m=40000 直接求解，连O(n2) 的算法都不能用 极限的情况下n=15000，m=40000，说明有很多数据是重复的，可以合并 采用“桶”来处理，把数据范围降到n=15000 加上x n div 9，可以枚举x nn/9=1500015000/9=2.5107 也就是说，可以采用O(n2/9)的算法来做,- 20 -,数据结构,s: int s40005; / 存放原数据 f: int f15005; / 桶，下标为魔法值 fa,fb,fc,fd : int 15005; / 次数,- 21 -,参考程序,#include #include using namespace std; int const maxn=40005; int smaxn,fmaxn,famaxn,fbmaxn,fcmaxn,fdmaxn; int n,m,i,j,ad,ac,y; int main() cinnm; for(i=1;isi; fsi+; for(i=1;i=n/9;i+) ad=9*i+1; y=0; for(j=ad+1;j=n;j+), y+=fj-ad*fj-ad+2*i; fdj=fdj+y*fj-i; fcj-i=fcj-i+y*fj; ac=8*i+1;