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

《NOIP2015普及组复赛测试题讲解(c++版本).ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、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++#includ

2、eusingnamespacestd;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<

3、格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。-5-确定解题思路模拟题，对每个格子进行标记。如果是雷，标记为-1，并把对应八个格子中不是雷的格子的数值递增1。注意字符的读入二维数组存放数据。-6-参考程序#includeusingnamespacestd;intmain(){longd[102][102];longn,m;cin>>n>>m;longi,j;charch;for(i=0;i<=n;i++){for(j=0

4、;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<

5、;cout<

6、0,007所得的余数即可。-8-暴力算法（预计分数40分，有点少）根据条件1：x,y,z都是整数,x=1&&z<=n根据条件2colorx=colorz判断是否要计算每次计算结束10007取模-9-参考程序（40分超时）#includeusingnamespacestd;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

7、=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<