"成绩"题解 第一题，2017NOIP普及组第一题，赤裸裸的打卡题。 让我们先看一下原题。 读完题后，我们发现出奇的水。A,B,C都是10的倍数，也就是说不存在小数，也就不用考虑float和double的问题。                ×20%  ×30%  ×50% 也就是    ×0.2     ×0.3     ×0.5   -->会用到强制类型转换         ×20/100  ×30/100  ×50/100  -->不会用到强制类型转换 接着输出就可以了。 代码如下： 这道题帅气的结束了呢！ "ISBN号码"题解 第二题也没有想象的那么难，其实也只是一个计算加比对的过程，但是这道题细节决定成败！ 先看原题： 读完题后，发现在一个ISBN号码中，一共有9个需要计算的数字，1个需要判断的数字。这道题的重点在于怎样求出正确的识别码。 那我们只需要把他们一个一个乘起来不就结束了？ 也就是：   for i = 0 -> 10    [ 注意数组下标从0开始 ]       识别码 += ( ( int )( a [ i ] - '0' ) * ( ++ tot ) ) /* 其中( int )( a [ i ] - '0' )是将一个字符转换为一个数，    还是手动强制类型转换比较好，免得出现一些不可      描述的错误。     tot 是用来从1乘到9的，因为其中有符号 ' - ' 所以循      环时不能使用 i 去乘。*/ 最后   识别码%=11   即可。  - - - - - - - - - - / 手 动 分 割 线 / - - - - - - - - - - 代码如下： 第二题也华丽的结束啦！ "火柴棒等式"题解 这道题也非常简单，但是细节方面需要注意！ [ PS:我是第一个AC的哦！ ] 我们先来看原题： 看起来无从下手，其实只需要暴力，再加点技巧即可。 加号和等于号各需要2根火柴棒，所以我们再输入n后，要   n-=4;  这样，我们只需要模拟数字即可。 - - - - - / THE FIRST QUESTION / - - - - - 那怎么去暴力枚举数字呢？  FOR !!! 两层for循环。因为最多会有24根火柴棒，所以最多能拼成1111+111=111 我们只需要模拟到1111即可，这样做的复杂度是 O( 1111^2 )  绝对不会超时。 - - - - - / THE SECOND QUESTION / - - - - - 为什么是两层for循环呢？ 假如说A+B=C,我们只需要模拟A和B，再加出C，判断火柴棒是否用完就可以了。 for i = 0 -> 1111     for j = 0 -> 1111         k=i+j         if ( i所用的火柴棒 + j所用的火柴棒 + k所用的火柴棒 == n /* 这时的n已经减去加号和等于号了 */ )               ans++ 核心代码写完了，剩下的就是怎么求i,j,k所用的火柴棒和输出了。 - - - - - / THE THIRD QUESTION / - - - - - 如何求i,j,k所用的火柴棒？ 首先，我们要预处理一下，说白了就是打表，打出0-9数字需要多少火柴棒。 c[10] = { 6 , 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 } 那么，单个数字sum所对应的火柴棒就是c [ sum ] 我们只需要将一位一位的数字求出来即可。 /* 设i是我们需要分解的数 */ int ans = 0 ; while ( i > 0 ){     ans += c [ i %10 ]     i /= 10 } 以下是代码： "采药"题解 这道题，其实还没有上一道题难，赤裸裸的01背包问题，没有任何难点，是模板。 先看原题： 这道题我不讲，只作分析和AC代码。 在题中背包总容量是   采药的时间 在题中n件物品的费用是  采每株药所需的时间 在题中n件物品的价值是  每株药的价值 递推式   f [ j ] = max ( f [ j ] , f [ j - w [ i ] ] + c [ i ] ) 你要是不会01背包，请查看： https://blog.csdn.net/weixin_39059738/article/details/79924049   注：此处为转载，版权属于原作者，一切利益归原作者所有。 以下是代码： "八数码问题"题解 啊，我先来吐波槽，一个裸的bfs题，我竟然没做出来？！ 后续因为要写题解再做的时候，一遍AC。。。 先让我来炫耀一波： 以下是原题，唯一和比赛不同的是没有了-1的判断和输入处理比较麻烦。之后，我会讲洛谷上这道题。最后，有差异的地方，我会提醒大家一下。 我在看完之后一脸懵X ( 小朋们，不能说脏话 ) ，甚至尝试用DP做，我都不知道我怎么想的。。。 好，我们正式开始讲解！ 这道题，没必要用什么康拓压缩，虽然它也很简单。就是一个BFS，搜到目标状态就结束，输出答案。那么，这道题就做完了。 细节--1：关于存储 我们没必要用什么一个变量去存图【康拓压缩】，我们每次也可以传一张地图过去。 struct qwe{     int x0 , y0;   //0的坐标     int a [ 4 ] [ 4 ] ;   //存地图     int ans ;  //存已经换了多少次，即答案 } bfs队列可以用：  queue < qwe >  q;  //定义一个qwe型的队列 存储路径可以用map:   map < int , bool >  m;  //具体用法，后面会详细讲 细节--2：关于路径记录 那我们怎样判断某一状态是否出现过了呢？我们肯定不能用一个  a[][][][][][][][][]  去存储（但是好像也是可行的），得想出一个高效率的方法，用map!  也就是一一对应的方法。举个栗子就明白了： 若我们想把 1 3 4 5 0 2 6 7 8 标记为已经走过 就可以这样写： m [ 134502678 /* 把9个数合到一起 */ ] = true 查询就是  if ( m [ 134502678 ] == false ) { ... } 这样，我们就完成了路径记录！【解决了核心问题！】 细节--3：路径记录的延伸问题 既然要把9个数变成1个数，那么一定要有个算法，我们用的是二维数组，那怎么办呢？ for(long long i=1;i<=3;i++){     for(long long j=1;j<=3;j++){         ans += ( av.a[ i ][ j ] *pow( 10 , ( ( i - 1 ) * 3 + j ) ) );     } } PS:不要把av想歪了！av的意思是：all_values 在其中( ( i - 1 ) * 3 )求出是在第几阶也就是0,3,6中的一阶 然后再加上 j 。   不明白的人可以带一组值。 比如   av.a[2][3]=5 那么就是：( 2 - 1 ) * 3 + 3 = 6 它的实际位置是： * * * | * * 5 | * * * 细节--4：状态复制问题 我们在while中，会弹出队首。如果我们每次都修改这个弹出值，会涉及到回溯问题，而这个题回溯起来会比较麻烦，所以我们把弹出值复制到 av 中，无论怎么修改 av 最后只需要再用弹出值覆盖一次即可。 我们要复制一个qwe到另一个qwe中。 av.x0=b.x0;av.y0=b.y0;     //复制'0'的坐标 av.ans=b.ans;   //复制答案 for(long long i=1;i<=3;i++){     for(long long j=1;j<=3;j++){         av.a[i][j]=b.a[i][j];   //复制地图     } } 细节--5：预处理 我们在移动'0'时，涉及到x,y的变化，所以，要做一个预处理，在最预处理的时候，数组名千万不要手残打成next，天哪，next是一个关键字，天知道上次月赛我被这玩意坑成啥样。做预处理时，要细心，别算错了，不然整个程序就崩了。 const long long ne[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; ne[i][0]指的是x的变化 ne[i][1]指的是y的变化 细节--6：输入【在原题中是3*3矩阵，所以不考虑】 它输入的是一个无空格的字符串。 所以怎样把这个字符串转换为我们所需要的3*3数组，也是一个难题。 for(long long i=0;i<(long long)(strlen(in_data));i++){     long long x,y;     av.a[x=(long long)(i/3)+1][y=i%3+1]=(long long) (in_data[i]-'0');     //坐标求法上面已经讲过，逆用即可     if(av.a[x][y]==0){       //发现'0'的位置         av.x0=x;         av.y0=y;     } } 还有一个重点，strlen()的返回类型是 unsigned int，而我们的i是 int ，所以注意强制类型转换。 细节--7：原题中的无解情况 只需要判断  队头的ans是否>5000即可 -----------/分割线/----------- 最后放上超长代码！

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com