晋城一中信息学奥赛3月月赛题解

网友投稿 2019-03-24 12:33

"成绩"题解

第一题,2017NOIP普及组第一题,赤裸裸的打卡题。

让我们先看一下原题。

https://cdn.china-scratch.com/timg/190326/12333119E-0.jpg

读完题后,我们发现出奇的水。A,B,C都是10的倍数,也就是说不存在小数,也就不用考虑float和double的问题。

               ×20%  ×30%  ×50%

也就是    ×0.2     ×0.3     ×0.5   -->会用到强制类型转换

        ×20/100  ×30/100  ×50/100  -->不会用到强制类型转换

接着输出就可以了。

代码如下:

https://cdn.china-scratch.com/timg/190326/1233312J0-1.jpg

这道题帅气的结束了呢!

https://cdn.china-scratch.com/timg/190326/123331G45-2.jpg

"ISBN号码"题解

https://cdn.china-scratch.com/timg/190326/1233324941-3.jpg

第二题也没有想象的那么难,其实也只是一个计算加比对的过程,但是这道题细节决定成败!

先看原题:

https://cdn.china-scratch.com/timg/190326/1233324091-4.jpg

读完题后,发现在一个ISBN号码中,一共有9个需要计算的数字,1个需要判断的数字。这道题的重点在于怎样求出正确的识别码。

那我们只需要把他们一个一个乘起来不就结束了?

也就是:

  for i = 0 -> 10    [ 注意数组下标从0开始 ]

      识别码 += ( ( int )( a [ i ] - '0' ) * ( ++ tot ) )

/* 其中( int )( a [ i ] - '0' )是将一个字符转换为一个数,    还是手动强制类型转换比较好,免得出现一些不可      描述的错误。 

   tot 是用来从1乘到9的,因为其中有符号 ' - ' 所以循      环时不能使用 i 去乘。*/

最后   识别码%=11   即可。

 - - - - - - - - - - / 手 动 分 割 线 / - - - - - - - - - -

代码如下:

https://cdn.china-scratch.com/timg/190326/1233334K0-5.jpg

第二题也华丽的结束啦!

"火柴棒等式"题解

这道题也非常简单,但是细节方面需要注意!

[ PS:我是第一个AC的哦! ]

我们先来看原题:

https://cdn.china-scratch.com/timg/190326/123333D36-6.jpg

看起来无从下手,其实只需要暴力,再加点技巧即可。

加号和等于号各需要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

}

以下是代码:

https://cdn.china-scratch.com/timg/190326/1233344S8-7.jpghttps://cdn.china-scratch.com/timg/190326/123331G45-2.jpg

"采药"题解

https://cdn.china-scratch.com/timg/190326/1233324941-3.jpg

这道题,其实还没有上一道题难,赤裸裸的01背包问题,没有任何难点,是模板。

先看原题:

https://cdn.china-scratch.com/timg/190326/1233345204-10.jpg

这道题我不讲,只作分析和AC代码。

在题中背包总容量是   采药的时间

在题中n件物品的费用是  采每株药所需的时间

在题中n件物品的价值是  每株药的价值

递推式   f [ j ] = max ( f [ j ] , f [ j - w [ i ] ] + c [ i ] )

你要是不会01背包,请查看:

https://blog.csdn.net/weixin_39059738/article/details/79924049  

注:此处为转载,版权属于原作者,一切利益归原作者所有。

以下是代码:

https://cdn.china-scratch.com/timg/190326/1233342Y7-11.jpg

"八数码问题"题解

啊,我先来吐波槽,一个裸的bfs题,我竟然没做出来?!

后续因为要写题解再做的时候,一遍AC。。。

先让我来炫耀一波:

https://cdn.china-scratch.com/timg/190326/123335J93-12.jpg

以下是原题,唯一和比赛不同的是没有了-1的判断和输入处理比较麻烦。之后,我会讲洛谷上这道题。最后,有差异的地方,我会提醒大家一下。

https://cdn.china-scratch.com/timg/190326/1233352G5-13.jpg

我在看完之后一脸懵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即可

-----------/分割线/-----------

最后放上超长代码!

https://cdn.china-scratch.com/timg/190326/1233354506-14.jpghttps://cdn.china-scratch.com/timg/190326/12333C219-15.jpghttps://cdn.china-scratch.com/timg/190326/12333B912-16.jpghttps://cdn.china-scratch.com/timg/190326/12333M626-17.jpghttps://cdn.china-scratch.com/timg/190326/123331G45-2.jpg

--end--

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