NOIP2015年普与组复赛试题讲解(c++版本)_第1页
NOIP2015年普与组复赛试题讲解(c++版本)_第2页
NOIP2015年普与组复赛试题讲解(c++版本)_第3页
NOIP2015年普与组复赛试题讲解(c++版本)_第4页
NOIP2015年普与组复赛试题讲解(c++版本)_第5页
已阅读5页,还剩13页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

NOIP2015年普与组复赛试题讲解(c++版本)第一页,共18页。NOIP2015

普及组复赛题解NOIP2015普及组C++第二页,共18页。第1题“金币”简述国王将金币作为工资,发放给忠诚的骑士。第一天骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天,每天收到四枚金币,以此类推;这种工资发放模式会一直延续下去,当连续N天收到N枚金币后,骑士会在之后的N+1天,每天收到N+1枚金币。请计算前K天里,骑士一共获得了多少金币。对于全部数据,1≤K≤10000。【分析】K的规模比较少,直接用模拟,一天一天发金币。N天发N枚金币,N递增1,剩余天数K-N预计时间15-25分钟3第三页,共18页。参考程序C++#include<iostream>usingnamespacestd;intmain(){ longk,n=1,sum=0; cin>>k; while(n<=k) { sum+=n*n;//N个金币发N天

k=k-n;//剩余天数

n=n+1;//接下来发的金币数量和天数

} sum+=k*n;//剩余不足N天的按实际天数发放

cout<<sum; return0;

}4第四页,共18页。第2题“扫雷游戏”简述扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。注:一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。5第五页,共18页。确定解题思路模拟题,对每个格子进行标记。如果是雷,标记为-1,并把对应八个格子中不是雷的格子的数值递增1。注意字符的读入二维数组存放数据。6第六页,共18页。参考程序#include<iostream>usingnamespacestd;intmain(){ longd[102][102]; longn,m; cin>>n>>m; 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++) { cin>>ch;//输入数据

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<<'*'; elsecout<<d[i][j]; cout<<endl; }//输出

return0;} 7第七页,共18页。第3题“求和”简述一条狭长的纸带被均匀划分出了n个格子,格子编号从1到n。每个格子上都染了一种颜色colori(用[1,m]当中的一个整数表示),并且写了一个数字numberi。定义一种特殊的三元组:(x,y,z),其中x,y,z都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:x,y,z都是整数,x<y<z,y−x=z−ycolorx=colorz满足上述条件的三元组的分数规定为(x+z)∗(numberx+numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以10,007所得的余数即可。8第八页,共18页。暴力算法(预计分数40分,有点少)根据条件1:x,y,z都是整数,x<y<z,y−x=z−y确定y为外层循环,y从1-n,确定内层循环x>=1&&z<=n根据条件2colorx=colorz判断是否要计算每次计算结束10007取模9第九页,共18页。参考程序(40分超时)#include<iostream>usingnamespacestd;intconstmaxn=100005;intmain(){ inti,y,n,m,number[maxn],color[maxn],sum=0; cin>>n>>m; for(i=1;i<=n;i++) cin>>number[i]; for(i=1;i<=n;i++) cin>>color[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++; } } cout<<sum<<endl; return0;} 10第十页,共18页。确定解题思路观察题意可以得知,如果第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第十一页,共18页。数据结构SIZE=100005数组大小intcolor[SIZE];格子的颜色值intnum[SIZE];,格子上的数值intsum[2][SIZE];相同颜色分奇偶求和intd[2][SIZE];相同颜色的数量,分奇偶统计数据输入量较多,使用scanf();12第十二页,共18页。参考程序#include<cstdio>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第十三页,共18页。第4题“推销员”简述阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住户。螺丝街一共有N家住户,第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相等。阿明会从入口进入,依次向螺丝街的X家住户推销产品,然后再原路走出去。阿明每走1米就会积累1点疲劳值,向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂,他想知道,对于不同的X,在不走多余的路的前提下,他最多可以积累多少点疲劳值。14第十四页,共18页。确定解题思路每一次的最优解必然包含了上一次的最优解,也就是说只要知道这一轮的最大疲劳值就行了。而这一次的最大疲劳值也就是找最大能多消耗的疲劳值。(贪心算法)分成两部分:一部分的距离小于已经到达的最远距离,另一部分大于可以到达的最远距离。15第十五页,共18页。数据结构小于最远距离的部分,它们的疲劳增加值就是各个点的疲劳值,所以用最大堆存储,疲劳值最大的在最前。位置大于最远距离远的点的依次搜索找到最大值(距离两倍+疲劳值),与最大堆的堆顶比较。如果在左侧最大堆中,POP_HEAP如果在右侧,将当前最远距离前的所有点PUSH_HEAP。代码写得有点长,大家将就着看,可以复制到DEV-C++中查看。16第十六页,共18页。参考程序

#include<iostream>#include<cstdio>#include<algorithm>#include<string>usingnamespacestd;intconstmaxn=100005;structdata{ intx,s,a;//序号,距离,疲劳值};datadt[maxn];intn,ans[maxn],lt,rt,now;boolcmp(datad1,datad2){ returnd1.a<d2.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;j<nowt;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); l

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论