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

2017.07.28 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 分析NOIP2016普及组复赛题解NOIP2016普及组C++借鉴百度文库PASCAL版本：https://wenku.baidu.com/view/9aafb5f30342a8956bec0975f46527d3240ca6dc.html-*-第1题“买铅笔”简述 P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有3种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。  商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过n支铅笔才够给小朋友们发礼物。  现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少n支铅笔最少需要花费多少钱? 【分析】送分题，数据量少，直接模拟即可。 当然，“小心撑得万年船”，“大意失荆州”-*-第2题“回文日期”简述 牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。  牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。  一个8位数字是回文的，当且仅当从左向右读和从右向左是相同的  例如：  2016年11月19日，表示为20161119，它不是回文的  2010年1月2日，表示为20100102，它是回文的。 求：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。-*-确定解题思路 一年是365天，如果闰年是366天。月日构成的数字最多只有366个。 第一步：构造出所有的日期（后四位） 第二步：利用回文的规则，构造出相应的年份 第三步：判断这个年份和日期在不在区间内 例如：8月15日，日期写成0815 对应回文的年份是：5180年 判断51800815这一天在不在（指定的起始日期）到（指定的终止日期）之间 程序时间复杂度为O(366)*-*-主程序 #include<iostream> 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}; cin>>date1>>date2;//输入起始结束日期 for(i=1;i<=12;i++) { m=i%10*10+i/10;//1-12月份倒置之后的值 t=ms[i]; for(j=1;j<=t;j++) -*-主程序 d=j%10*10+j/10;//1-t日倒置之后的值 y=(d*100+m)*10000+i*100+j;//对应回文的日期 if(y>=date1&&y<=date2) sum++;//判断这个日期在不在查询范围内 } } cout<<sum<<endl; return0; }-*-确定解题思路（解法2） 如果从日期入手，一天一天往上加，每一天都要判断是不是合法的日期，是不是回文。容易出错，遇到极限数据还会超时 题目里还有更重要的一点是“回文” 位数是确定的，八位，很容易“组合” 例如：2014，可以组成20144102 我们只要判断20144102是不是合法的日期就可以了 就算年份的范围是1000~9999，也只要计算9000次就可以了-*-程序框架 输入数据 fori=day_startdiv10000//取年份 <=day_enddiv10000//循环起始到结束年份 if（check(i)）//判断i年对应的日期是否符合要求 特别注意：还要判断这个日期是否在范围内-*-第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艘船到达后的统计信息。 -*-暴力算法（预计分数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)-*-确定解题思路 题目明确告诉我们，要计算的是中间的一段时间的统计结果。 从数据结构的角度看，是“队列”：先进先出 所有ki之和<=300000，也就是总人数少于30万 队列中记录时间和国籍，到达的入队，超过86400秒的出队，时间复杂度O(kt) 如何统计“总共有多少个不同的数”呢？ 1<=Xi,j<=100000，当然用Hash(桶)-*-数据结构 队列：用数组qt：时间，qx：国籍 intqt[300005],qx[300005]; 头指针:head，尾指针：tail Hash表： inths[100005;-*-参考程序 #include<iostream> #include<cstring> 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)); cin>>n; for(i=1;i<=n;i++) { cin>>ti>>ki; for(j=1;j<=ki;j++) for(j=1;j<=ki;j++) { cin>>xi; 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++; } cout<<cnt<<endl; } return0; }-*-第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物品的次数。-*-确定解题思路 【分析】压轴题，当然要难 这题几乎是个数学题 首先要会画“线段图” 其次，“加法原理”“乘法原理”要熟练 最后，是“胆大心细”编程能力-*-确定解题思路1 画“线段图” Xa<Xb<Xc<Xd Xb-Xa=2(Xd-Xc) Xb-Xa<(Xc-Xb)÷3Xc-Xb<(Xb-Xa)×3 设CD=x AB=2xBC>6x AD=AB+BC+CD>9xx<ndiv9 也就是说，CD的长度不会超过全长的九分之一-*-确定解题思路2 乘法原理： 如果魔法值为A的物品有Ya个，B的有Yb个，C的有Yc个，那么，D中的一个物品作为D物品的次数是多少呢？ 根据乘法原理，次数=Ya×Yb×Yc 对于A,B,C,D的做法是一样的-*-确定解题思路3 数据范围：1<=n<=150001<=m<=40000 直接求解，连O(n2)的算法都不能用 极限的情况下n=15000，m=40000，说明有很多数据是重复的，可以合并 采用“桶”来处理，把数据范围降到n=15000 加上x<ndiv9，可以枚举x n×n/9=15000×15000/9=2.5×107 也就是说，可以采用O(n2/9)的算法来做-*-数据结构 s:ints[40005];//存放原数据 f:intf[15005];//桶，下标为魔法值 fa,fb,fc,fd:int[15005];//次数-*-参考程序 #include<iostream> #include<cstring> usingnamespacestd; intconstmaxn=40005; ints[maxn],f[maxn],fa[maxn],fb[maxn],fc[maxn],fd[maxn]; intn,m,i,j,ad,ac,y; intmain() { cin>>n>>m; for(i=1;i<=m;i++) { cin>>s[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++) cout<<fa[s[i]]<<""<<fb[s[i]]<<""<<fc[s[i]]<<""<<fd[s[i]]<<endl; return0;}2017.07.28试题分析BYETheEND温馨提示：本题借鉴了他人的 资料 新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单 原文PASCAL版，现在修改为C++版本，原文地址如下：https://wenku.baidu.com/view/dbdbf27dc950ad02de80d4d8d15abe23482f03e3*