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

2017.07.28试题分析NOIP2015普及组复赛题解NOIP2015普及组C++-2-第1题“金币”简述国王将金币作为工资，发放给忠诚的骑士。第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。请计算前K天里，骑士一共获得了多少金币。对于全部数据，1≤K≤10000。【分析】K的规模比较少，直接用模拟，一天一天发金币。N天发N枚金币，N递增1，剩余天数K-N预计时间15-25分钟-3-参考程序C++#includeiostreamusingnamespacestd;intmain(){longk,n=1,sum=0;cink;while(n=k){sum+=n*n;//N个金币发N天k=k-n;//剩余天数n=n+1;//接下来发的金币数量和天数}sum+=k*n;//剩余不足N天的按实际天数发放coutsum;return0;}-4-第2题“扫雷游戏”简述扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。-5-确定解题思路模拟题，对每个格子进行标记。如果是雷，标记为-1，并把对应八个格子中不是雷的格子的数值递增1。注意字符的读入二维数组存放数据。-6-参考程序#includeiostreamusingnamespacestd;intmain(){longd[102][102];longn,m;cinnm;longi,j;charch;for(i=0;i=n;i++){for(j=0;j=m;j++)d[i][j]=0;}//数组初始化for(i=1;i=n;i++){for(j=1;j=m;j++){cinch;//输入数据if(ch=='*'){d[i][j]=-1;//用-1表示地雷longl1,l2;for(l1=-1;l1=1;l1++)for(l2=-1;l2=1;l2++){if(d[i+l1][j+l2]!=-1)d[i+l1][j+l2]++;}//边上八个位置的格子不是雷则数值加1}}}for(i=1;i=n;i++){for(j=1;j=m;j++)if(d[i][j]==-1)cout'*';elsecoutd[i][j];coutendl;}//输出return0;}-7-第3题“求和”简述一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色colori（用[1，m]当中的一个整数表示），并且写了一个数字numberi。定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：x,y,z都是整数,xyz,y−x=z−ycolorx=colorz满足上述条件的三元组的分数规定为(x+z)∗(numberx+numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。-8-暴力算法（预计分数40分，有点少）根据条件1：x,y,z都是整数,xyz,y−x=z−y确定y为外层循环，y从1-n，确定内层循环x=1&&z=n根据条件2colorx=colorz判断是否要计算每次计算结束10007取模-9-参考程序（40分超时）#includeiostreamusingnamespacestd;intconstmaxn=100005;intmain(){inti,y,n,m,number[maxn],color[maxn],sum=0;cinnm;for(i=1;i=n;i++)cinnumber[i];for(i=1;i=n;i++)cincolor[i];for(y=1;y=n;y++){intj=1;while(y-j=1&&y+j=n){if(color[y-j]==color[y+j])sum+=2*y*(number[y-j]+number[y+j]);sum%=10007;j++;}}coutsumendl;return0;}-10-确定解题思路观察题意可以得知，如果第i位和第j位同色，那么就一定能够组成一个三元组，并且三元组的价值完全与中间那个数无关。那么，我们就用一个数组存储同奇偶性的同色方块，用n表示数值，i和j表示坐标。那么价值就是(ni+nj)*(i+j)每组的数的下标用a1～an表示，数值用n1～nk表示，用sum表示数值之和。答案就是(n1+n2)*(a1+a2)+……+……。如果这样做就是O(n^2/m)的算法。（估计能过60分）转换公式(a1*n1+a2*n2+…+ak*nk)*(n-2)+(a1+a2+…+ak)*(n1+n2+…nk)O(n)的时间复杂度-11-数据结构SIZE=100005数组大小intcolor[SIZE];格子的颜色值intnum[SIZE];，格子上的数值intsum[2][SIZE];相同颜色分奇偶求和intd[2][SIZE];相同颜色的数量，分奇偶统计数据输入量较多，使用scanf();-12-参考程序#includecstdiousingnamespacestd;constintSIZE=100005,mod=10007;intn,m;intcolor[SIZE];intnum[SIZE];intsum[2][SIZE];intd[2][SIZE];intans=0;intmain(){scanf(%d%d,&n,&m);inti;for(i=1;i=n;i++){scanf(%d,num+i);}for(i=1;i=n;i++){scanf(%d,color+i);sum[i%2][color[i]]=(sum[i%2][color[i]]+num[i])%mod;d[i%2][color[i]]++;}for(i=1;i=n;i++){ans=(ans+sum[i%2][color[i]]*i%mod+(d[i%2][color[i]]-2)%mod*num[i]%mod*i%mod)%mod;}printf(%d\n,ans);return0;}-13-第4题“推销员”简述阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。-14-确定解题思路每一次的最优解必然包含了上一次的最优解，也就是说只要知道这一轮的最大疲劳值就行了。而这一次的最大疲劳值也就是找最大能多消耗的疲劳值。(贪心算法)分成两部分：一部分的距离小于已经到达的最远距离，另一部分大于可以到达的最远距离。-15-数据结构小于最远距离的部分，它们的疲劳增加值就是各个点的疲劳值，所以用最大堆存储，疲劳值最大的在最前。位置大于最远距离远的点的依次搜索找到最大值（距离两倍+疲劳值），与最大堆的堆顶比较。如果在左侧最大堆中，POP_HEAP如果在右侧，将当前最远距离前的所有点PUSH_HEAP。代码写得有点长，大家将就着看，可以复制到DEV-C++中查看。-16-参考程序#includeiostream#includecstdio#includealgorithm#includestringusingnamespacestd;intconstmaxn=100005;structdata{intx,s,a;//序号，距离，疲劳值};datadt[maxn];intn,ans[maxn],lt,rt,now;boolcmp(datad1,datad2){returnd1.ad2.a;}intmain(){scanf(%d,&n);for(inti=1;i=n;i++)scanf(%d,&dt[i].s);for(inti=1;i=n;i++){scanf(%d,&dt[i].a);dt[i].x=i;intt=2*dt[i].s+dt[i].a;if(ans[1]t){ans[1]=t;now=i;}}lt=now;rt=now+1;make_heap(dt,dt+lt,cmp);for(inti=2;i=n;i++){if(rt=n){intnowt=0,sumt=0;for(intj=rt;j=n;j++){intt=2*(dt[j].s-dt[now].s)+dt[j].a;if(t=sumt)sumt=t,nowt=j;}if(sumt=dt[0].a){for(intj=rt;jnowt;j++){dt[lt-1]=dt[j];push_heap(dt,dt+lt,cmp);lt++;}ans[i]=ans[i-1]+sumt;now=nowt;rt=now+1;}else{ans[i]=ans[i-1]+dt[0].a;pop_heap(dt,dt+lt,cmp);lt--;}}else{ans[i]=ans[i-1]+dt[0].a;pop_heap(dt,dt+lt,cmp);lt--;}}/*for(inti=0;iw;i++)coutdl[i].a;coutendl;for(inti=0;in-w-1;i++)coutdr[i].a;*/for(inti=1;i=n;i++)coutans[i]endl;}2017.07.28试题分析BYETheEND温馨提示：先理解题目在看题解。