《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,温馨提示: 先理解题目在看题解。,