《noip2015年普与组复赛试题讲解(c++版本)》由会员分享，可在线阅读，更多相关《noip2015年普与组复赛试题讲解(c++版本)（17页珍藏版）》请在金锄头文库上搜索。
1、NOIP2015 普及组复赛题解,NOIP2015普及组C+,- 2 -,第1题 “金币”简述,国王将金币作为工资，发放给忠诚的骑士。 第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。 请计算前K天里，骑士一共获得了多少金币。 对于全部数据，1K10000。 【分析】K的规模比较少，直接用模拟，一天一天发金币。 N天发N枚金币，N递增1，剩余天数K-N 预计时间15-25分钟,- 3 -
2、,参考程序 C+,#include using namespace std; int main() long k,n=1,sum=0; cink; while (n=k) sum+=n*n;/N个金币发N天 k=k-n;/剩余天数 n=n+1;/接下来发的金币数量和天数 sum+=k*n;/剩余不足N天的按实际天数发放 coutsum; return 0; ,- 4 -,第2题 “扫雷游戏”简述,扫雷游戏是一款十分经典的单机小游戏。 在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。 玩家翻开一个非地雷格时，该格将会出现一个数字提示周围格子中有多少个是地
3、雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。 注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。,- 5 -,确定解题思路,模拟题，对每个格子进行标记。 如果是雷，标记为-1，并把对应八个格子中不是雷的格子的数值递增1。 注意字符的读入 二维数组存放数据。,- 6 -,参考程序,#include using namespace std; int main() long d102102; long n,m; cinnm; long i,j; char
4、ch; for(i=0;ich;/输入数据 if (ch=*), dij=-1;/用-1表示地雷 long l1,l2; for(l1=-1;l1=1;l1+) for(l2=-1;l2=1;l2+) if(di+l1j+l2!=-1) di+l1j+l2+; /边上八个位置的格子不是雷则数值加1 for(i=1;i=n;i+) for(j=1;j=m;j+) if( dij=-1) cout*; else coutdij; coutendl; /输出 return 0; ,- 7 -,第3题 “求和”简述,一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色col
5、ori（用1，m当中的一个整数表示），并且写了一个数字numberi。 定义一种特殊的三元组：(x, y, z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： x, y, z都是整数, xyz ,yx=zy colorx = colorz 满足上述条件的三元组的分数规定为(x+z)(numberx+numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10,007 所得的余数即可。,- 8 -,暴力算法（预计分数40分，有点少）,根据条件1：x, y, z都是整数, x=1&z=n 根据条件2 col
6、orx = colorz判断是否要计算 每次计算结束10007取模,- 9 -,参考程序（40分超时）,#include using namespace std; int const maxn=100005; int main() int i,y,n,m,numbermaxn,colormaxn,sum=0; cinnm; for( i=1;inumberi; for( i=1;icolori; for(y=1;y=1&y+j=n) ,if(colory-j=colory+j) sum+=2*y*(numbery-j+numbery+j); sum%=10007; j+; coutsumend
7、l; return 0; ,- 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 -,数据结
8、构,SIZE=100005 数组大小 int colorSIZE; 格子的颜色值 int numSIZE; ，格子上的数值 int sum2SIZE; 相同颜色分奇偶求和 int d2SIZE; 相同颜色的数量，分奇偶统计 数据输入量较多，使用scanf();,- 12 -,参考程序,#include using namespace std; const int SIZE=100005,mod=10007; int n,m; int colorSIZE; int numSIZE; int sum2SIZE; int d2SIZE; int ans=0; int main() scanf(“%d
9、%d“,sumi%2colori= (sumi%2colori+numi)%mod; di%2colori+; for(i=1;i=n;i+) ans=(ans+ sumi%2colori*i%mod+ (di%2colori-2)%mod*numi%mod*i%mod)%mod; printf(“%dn“,ans); return 0; ,- 13 -,第4题 “推销员”简述,阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 N 家住户，第 i 家住户到入口的距离为 Si 米。由于同一栋房子里可以有多家住
10、户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 X 家住户推销产品，然后再原路走出去。 阿明每走 1 米就会积累 1 点疲劳值，向第 i 家住户推销产品会积累 Ai 点疲劳值。阿明是工作狂，他想知道，对于不同的 X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。,- 14 -,确定解题思路,每一次的最优解必然包含了上一次的最优解，也就是说只要知道这一轮的最大疲劳值就行了。而这一次的最大疲劳值也就是找最大能多消耗的疲劳值。(贪心算法) 分成两部分：一部分的距离小于已经到达的最远距离，另一部分大于可以到达的最远距离。,- 15 -,数据结构,小于最远距离的部分，它们
11、的疲劳增加值就是各个点的疲劳值，所以用最大堆存储，疲劳值最大的在最前。 位置大于最远距离远的点的依次搜索找到最大值（距离两倍+疲劳值），与最大堆的堆顶比较。 如果在左侧最大堆中，POP_HEAP 如果在右侧，将当前最远距离前的所有点PUSH_HEAP。 代码写得有点长，大家将就着看，可以复制到DEV-C+中查看。,- 16 -,参考程序,#include #include #include #include using namespace std; int const maxn=100005; struct data int x,s,a;/序号，距离，疲劳值 ; data dtmaxn; in
12、t n,ansmaxn,lt,rt,now; bool cmp(data d1, data d2) return d1.a=sumt) sumt=t,nowt=j; if(sumt=dt0.a) for(int j=rt;jnowt;j+) dtlt-1=dtj; push_heap(dt,dt+lt,cmp); lt+; ansi=ansi-1+sumt; now=nowt; rt=now+1; else ansi=ansi-1+dt0.a; pop_heap(dt,dt+lt,cmp); lt-; else ansi=ansi-1+dt0.a; pop_heap(dt,dt+lt,cmp); lt-; /*for(int i=0;iw;i+) coutdli.a“ “; coutendl; for(int i=0;in-w-1;i+) coutdri.a“ “;*/ for(int i=1;i=n;i+) coutansiendl; ,BYE,The END,温馨提示： 先理解题目在看题解。,
