"成绩"题解

第一题，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