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

2017.07.28试题分析NOIP2016普及组复赛题解NOIP2016普及组C++借鉴百度文库PASCAL版本：第1题“买铅笔”简述P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋友们发礼物。现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱?【分析】送分题，数据量少，直接模拟即可。当然，“小心撑得万年船”，“大意失荆州”-3-例程C++#includeiostreamusingnamespacestd;intmain(){longn,i,s,mins=100000000;//n铅笔数量，i循环变量，s费用，mins最小费用longc[4],p[4];//三种铅笔的数量和价格cinn;for(i=1;i4;i++){cinc[i]p[i];if(n%c[i]==0)s=n/c[i]*p[i];//正好整包elses=(n/c[i]+1)*p[i];//有多余，再来一包if(minss)mins=s;//判断那种买法最省钱}coutmins;return0;}-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-主程序#includeiostreamusingnamespacestd;intmain(){longi,j,y,m,d,t,date1,date2,sum=0;//i,j循环变量，y对应日期,m月倒置的数值,d日倒置的数值longms[13]={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=ms[i];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&&y=date2)sum++;//判断这个日期在不在查询范围内}}coutsumendl;return0;}-8-确定解题思路（解法2）如果从日期入手，一天一天往上加，每一天都要判断是不是合法的日期，是不是回文。容易出错，遇到极限数据还会超时题目里还有更重要的一点是“回文”位数是确定的，八位，很容易“组合”例如：2014，可以组成20144102我们只要判断20144102是不是合法的日期就可以了就算年份的范围是1000~9999，也只要计算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分）h[100001];h[x]表示国籍为x的乘客到港的最新时间。初始值为-86400.sum[100001]；sum[1-n]表示1-n个艘船到达海港对应的国籍数量。每一艘船到达海港，更新对应国籍乘客的到港时间数组h统计所有国籍的到港时间是否在24小时内，t为当前时间，t-h[x]86400，表示X国籍满足条件。时间复杂度：O(kt+n*x)-12-确定解题思路题目明确告诉我们，要计算的是中间的一段时间的统计结果。从数据结构的角度看，是“队列”：先进先出所有ki之和=300000，也就是总人数少于30万队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度O(kt)如何统计“总共有多少个不同的数”呢？1=Xi,j=100000，当然用Hash(桶)-13-数据结构队列：用数组qt：时间，qx：国籍intqt[300005],qx[300005];头指针:head，尾指针：tailHash表：inths[100005;-14-参考程序#includeiostream#includecstringusingnamespacestd;intconstmaxn=300005;intqt[maxn],qx[maxn];inths[100005];inthead=1,tail=1,n,i,j,ti,tic,ki,xi,cnt=0;intmain(){memset(hs,0,sizeof(hs));cinn;for(i=1;i=n;i++){cintiki;for(j=1;j=ki;j++)for(j=1;j=ki;j++){cinxi;qt[tail]=ti;qx[tail]=xi;if(hs[xi]==0)cnt++;hs[xi]++;tail++;}tic=ti-86400;while(qt[head]=tic){xi=qx[head];hs[xi]--;if(hs[xi]==0)cnt--;head++;}coutcntendl;}return0;}-15-第4题“魔法阵”简述大魔法师认为，当且仅当四个编号为a,b,c,d的魔法物品满足①XaXbXcXd，②Xb-Xa=2(Xd-Xc)，③并且Xb-Xa(Xc-Xb)/3时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的A物品，B物品，C物品，D物品。现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的A物品出现的次数，作为B物品的次数，作为C物品的次数，和作为D物品的次数。-16-确定解题思路【分析】压轴题，当然要难这题几乎是个数学题①首先要会画“线段图”②其次，“加法原理”“乘法原理”要熟练③最后，是“胆大心细”编程能力-17-确定解题思路1画“线段图”XaXbXcXdXb-Xa=2(Xd-Xc)Xb-Xa(Xc-Xb)÷3Xc-Xb(Xb-Xa)×3设CD=xAB=2xBC6xAD=AB+BC+CD9xxndiv9也就是说，CD的长度不会超过全长的九分之一-18-确定解题思路2乘法原理：如果魔法值为A的物品有Ya个，B的有Yb个，C的有Yc个，那么，D中的一个物品作为D物品的次数是多少呢？根据乘法原理，次数=Ya×Yb×Yc对于A,B,C,D的做法是一样的-19-确定解题思路3数据范围：1=n=150001=m=40000直接求解，连O(n2)的算法都不能用极限的情况下n=15000，m=40000，说明有很多数据是重复的，可以合并采用“桶”来处理，把数据范围降到n=15000加上xndiv9，可以枚举xn×n/9=15000×15000/9=2.5×107也就是说，可以采用O(n2/9)的算法来做-20-数据结构s:ints[40005];//存放原数据f:intf[15005];//桶，下标为魔法值fa,fb,fc,fd:int[15005];//次数-21-参考程序#includeiostream#includecstringusingnamespacestd;intconstmaxn=40005;ints[maxn],f[maxn],fa[maxn],fb[maxn],fc[maxn],fd[maxn];intn,m,i,j,ad,ac,y;intmain(){cinnm;for(i=1;i=m;i++){cins[i];f[s[i]]++;}for(i=1;i=n/9;i++){ad=9*i+1;y=0;for(j=ad+1;j=n;j++){y+=f[j-ad]*f[j-ad+2*i];fd[j]=fd[j]+y*f[j-i];fc[j-i]=fc[j-i]+y*f[j];}ac=8*i+1;y=0;for(j=n-9*i-1;j=1;j--){y+=f[j+ac]*f[j+ac+i];fa[j]=fa[j]+y*f[j+2*i];fb[j+2*i]=fb[j+2*i]+y*f[j];}}for(i=1;i=m;i++)coutfa[s[i]]fb[s[i]]fc[s[i]]fd[s[i]]endl;return0;}2017.07.28试题分析BYETheEND温馨提示：本题借鉴了他人的资料原文PASCAL版，现在修改为C++版本，原文地址如下：