《NOIP2016普及组复赛试题讲解(c++版本).ppt》由会员分享，可在线阅读，更多相关《NOIP2016普及组复赛试题讲解(c++版本).ppt（22页珍藏版）》请在金锄头文库上搜索。
1、2017.07.28试题分析NOIP2016普及组复赛题解NOIP2016普及组C+借鉴百度文库PASCAL版本：https:/ xndiv9也就是说，CD的长度不会超过全长的九分之一-18-确定解题思路2乘法原理：如果魔法值为A的物品有Ya个，B的有Yb个，C的有Yc个，那么，D中的一个物品作为D物品的次数是多少呢？根据乘法原理，次数=YaYbYc对于A,B,C,D的做法是一样的-19-确定解题思路3数据范围：1=n=150001=m=40000直接求解，连O(n2)的算法都不能用极限的情况下n=15000，m=40000，说明有很多数据是重复的，可以合并采用“桶”来处理，把数据范围降到n=
2、15000加上xndiv9，可以枚举xnn/9=1500015000/9=2.5107也就是说，可以采用O(n2/9)的算法来做-20-数据结构s:ints40005;/存放原数据f:intf15005;/桶，下标为魔法值fa,fb,fc,fd:int15005;/次数-21-参考程序#include#includeusingnamespacestd;intconstmaxn=40005;intsmaxn,fmaxn,famaxn,fbmaxn,fcmaxn,fdmaxn;intn,m,i,j,ad,ac,y;intmain()cinnm;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+ac+i;faj=faj+y*fj+2*i;fbj+2*i=fbj+2*i+y*fj;for(i=1;i=m;i+)coutfasifbsifcsifdsiendl;return0;2017.07.28试题分析BYETheEND温馨提示：温馨提示：本题借鉴了他人的资料本题借鉴了他人的资料原文原文PASCALPASCAL版，现在修改为版，现在修改为C+C+版本，原文地址如下：版本，原文地址如下：https:/
