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

NOIP2015普及组复赛题解,NOIP2015普及组C+,-2-,第1题“金币”简述,国王将金币作为工资，发放给忠诚的骑士。第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。请计算前K天里，骑士一共获得了多少金币。对于全部数据，1K10000。【分析】K的规模比较少，直接用模拟，一天一天发金币。N天发N枚金币，N递增1，剩余天数K-N预计时间15-25分钟,-3-,参考程序C+,#includeusingnamespacestd;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天的按实际天数发放coutnm;longi,j;charch;for(i=0;ich;/输入数据if(ch=*),dij=-1;/用-1表示地雷longl1,l2;for(l1=-1;l1=1;l1+)for(l2=-1;l2=1;l2+)if(di+l1j+l2!=-1)di+l1j+l2+;/边上八个位置的格子不是雷则数值加1for(i=1;i=n;i+)for(j=1;j=m;j+)if(dij=-1)cout*;elsecoutdij;coutendl;/输出return0;,-7-,第3题“求和”简述,一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色colori（用1，m当中的一个整数表示），并且写了一个数字numberi。定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：x,y,z都是整数,xynumberi;for(i=1;icolori;for(y=1;y=1sum%=10007;j+;coutsumendl;return0;,-10-,确定解题思路,观察题意可以得知，如果第i位和第j位同色，那么就一定能够组成一个三元组，并且三元组的价值完全与中间那个数无关。那么，我们就用一个数组存储同奇偶性的同色方块，用n表示数值，i和j表示坐标。那么价值就是(ni+nj)*(i+j)每组的数的下标用a1an表示，数值用n1nk表示，用sum表示数值之和。答案就是(n1+n2)*(a1+a2)+。如果这样做就是O(n2/m)的算法。（估计能过60分）转换公式(a1*n1+a2*n2+ak*nk)*(n-2)+(a1+a2+ak)*(n1+n2+nk)O(n)的时间复杂度,-11-,数据结构,SIZE=100005数组大小intcolorSIZE;格子的颜色值intnumSIZE;，格子上的数值intsum2SIZE;相同颜色分奇偶求和intd2SIZE;相同颜色的数量，分奇偶统计数据输入量较多，使用scanf();,-12-,参考程序,#includeusingnamespacestd;constintSIZE=100005,mod=10007;intn,m;intcolorSIZE;intnumSIZE;intsum2SIZE;intd2SIZE;intans=0;intmain()scanf(%d%d,sumi%2colori=(sumi%2colori+numi)%mod;di%2colori+;for(i=1;i=dt0.a)for(intj=rt;jnowt;j+)dtlt-1=dtj;push_heap(dt,dt+lt,cmp);lt+;ansi=ansi-1+sumt;now=nowt;rt=now+1;elseansi=ansi-1+dt0.a;pop_heap(dt,dt+lt,cmp);lt-;elseansi=ansi-1+dt0.a;pop_heap(dt,dt+lt,cmp);lt-;/*for(inti=0;iw;i+)coutdli.a;coutendl;f