NOIP2016普及组复赛试题讲解c版本[通用]

1、NOIP2016普及组复赛题解NOIP2016普及组C+借鉴百度文库PASCAL版本：https:/ “买铅笔”简述P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋 友们发礼物。现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱?【分析】送分题，数据量少，直接模拟即可。当然，“小心撑得万年船”，“大意失荆州”2例程 C+#includeusin

2、g 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;3第2题 “回文日期”简述牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月 份，最后2位代表日期。显然：一个日期只有一种表示方法，而

3、两个不同的日期的表 示方法不会相同。牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。一个8位数字是回文的，当且仅当从左向右读和从右向左是相同的例如：2016年11月19日，表示为20161119，它不是回文的2010年1月2日，表示为20100102，它是回文的。求：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。4确定解题思路一年是365天，如果闰年是366天。月日构成的数字最多只有366个。第一步：构造出所有的日期（后四位）第二步：利用回文的规则，

4、构造出相应的年份第三步：判断这个年份和日期在不在区间内例如：8月15日，日期写成0815 对应回文的年份是：5180年判断51800815这一天在不在（指定的起始日期）到（指定的终止日期）之间程序时间复杂度为O(366)5主程序#includeusing 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

5、=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，可以组成 20144102我们只要判断20144102是不是合法的日期就可以了就算年份的范围是 10009999，也只要计算9000次就可以了8程序框架输入数据fo

6、r i=day_start div 10000 / 取年份 =day_end div 10000 /循环起始到结束年份if （check(i)） / 判断i年对应的日期是否符合要求特别注意：还要判断这个日期是否在范围内9第3题 “海港”简述小K按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数量ki，以及每名乘客的国籍 x(i,1), x(i,2),，x(i,k)。小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。形式化地讲，你需要计算n

7、条信息。对于输出的第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(kt+n*x) 11确定解题思路题目明确告诉我们，要计算的是中间

8、的一段时间的统计结果。从数据结构的角度看，是“队列”：先进先出所有 ki之和=300000，也就是总人数少于30万队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度 O(kt) 如何统计“总共有多少个不同的数” 呢？1=Xi,j=100000 ，当然用Hash (桶)12数据结构队列：用数组qt：时间，qx：国籍int qt300005, qx300005;头指针: head，尾指针：tailHash表： int hs 100005;13参考程序#include#includeusing namespace std;int const maxn=300005;int qtma

9、xn,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;14第4题 “魔法阵”简述大魔

10、法师认为，当且仅当四个编号为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 XdXb-Xa=2(Xd-Xc)Xb-Xa(Xc-Xb)3 Xc-Xb6xAD=AB+BC+CD 9x 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(n2) 的算法都不能用极限的情况下n=15000，m=40000，说明有很多数据是重复的，可以