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

2017. 07. 28 试题分析 NOIP2015普及组复赛题解 NOIP2015普及组C++ - * - 第1题 “金币”简述 国王将金币作为工资，发放给忠诚的骑士。 第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天，每天收到四枚金币，以此类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。 请计算前K天里，骑士一共获得了多少金币。 对于全部数据，1≤K≤10000。 【分析】K的规模比较少，直接用模拟，一天一天发金币。 N天发N枚金币，N递增1，剩余天数K-N 预计时间15-25分钟 - * - 参考程序 C++ #include iostream 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; } - * - 第2题 “扫雷游戏”简述 扫雷游戏是一款十分经典的单机小游戏。 在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。 玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。 注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下八个方向上与之直接相邻的格子。 - * - 确定解题思路 模拟题，对每个格子进行标记。 如果是雷，标记为-1，并把对应八个格子中不是雷的格子的数值递增1。 注意字符的读入 二维数组存放数据。 - * - 参考程序 #include iostream using namespace std; int main() { long d[102][102]; long n,m; cinnm; long i,j; char ch; 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++) { cinch;//输入数据 if (ch==*) { d[i][j]=-1;//用-1表示地雷 long l1,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*; else coutd[i][j]; coutendl; }//输出 return 0; } - * - 第3题 “求和”简述 一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色colori（用[1，m]当中的一个整数表示），并且写了一个数字numberi。 定义一种特殊的三元组：(x, y, z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件： x, y, z都是整数, xyz ,y?x=z?y colorx = colorz 满足上述条件的三元组的分数规定为(x+z)?(numberx+numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10,007 所得的余数即可。 - * - 暴力算法（预计分数40分，有点少） 根据条件1：x, y, z都是整数, xyz ,y?x=z?y 确定y为外层循环，y从1-n， 确定内层循环x=1z=n 根据条件2 colorx = colorz判断是否要计算 每次计算结束10007取模 - * - 参考程序（40分超时） #include iostream using namespace std; int const maxn=100005; int main() { int i,y,n,m,number[maxn],color[maxn]