蓝桥杯校内模拟赛口胡题解

今天学车,没时间做这个模拟赛了,不过今天下午有老哥给了题,也想看看题目是什么样的。这个题说实话不算太难。

emm不太想写代码了,所以把简单的思路说一下吧,所以叫口胡题解。如果有错误还烦请指出QAQ

第一题

问一万以内最大的质数,暴力筛即可。从2开始,外层循环枚举要判断的数字,内层循环把它的倍数全都打标记为false。比如2是质数,那么2的倍数一定不是质数,那些数字全部标上false,然后看3,4..一直到一万。看看筛到的质数最大是几就行。答案是9973。

如果数据量更大,可以使用欧拉筛。

第二题

问111 1001 1101+11 1110 1001等于多少,甚至可以用windows自带的计算器算。手算也可以。答案是1011 1000 0110。

第三题

2019个有区别的球中选3个球放在一个盘子里,问有多少种选法。

简单的组合数学。答案是C(2019,3) = 2019×2018×2017/(1×2×3) = 1369657969‬。

第四题

一棵包含有2019个结点的树,最多包含多少个叶结点?

这个题我傻了半天然后发现是个弱智题。题目没说是二叉树!我反复确认了,题目没说这是二叉树!

那最多的情况就是一个根,2018个叶子,也就是最多包含2018个叶结点。

如果这是二叉树的话那才考的算有点水平。这种情况下这么做:

设二叉树中叶结点数量为n0,度为1的结点数量为n1,度为2的结点数量为n2,由二叉树的性质n0 = n2 + 1,又因为二叉树只由叶节点,度为1的结点和度为2的结点构成,所以有n0 + n1 + n2 = 2019,联立这俩方程可以得到2n2 + n1 = 2018,即n2 = (2018 - n1) / 2。题目要叶结点数量最多,那么显然n2要取最大值,观察右式可知n1取0时n2可以取得最大值,得出答案为1009。

第五题

给定正整数n,问在[1,n]区间里没有数位相同的数有多少,n<=1e6。

数据量不算大,暴力枚举每一个数字,进行分离数位操作,判断位数有相同则不计数,否则计数+1。

判断位数相同不难,开个数组,每次分离出一个数位就在对应位上记录一下。每次有一个新的位数准备加入时看有没有记录,有则肯定是位数有相同,无则给它记录,然后继续。

第六题

输入一个单词,输出这个单词中第一个出现的元音字母(a,e,i,o,u)。单词长度不超过100。

直接从头开始找,找到第一个元音就输出。

第七题

给定整数m,给定数列a1..an,如果数列里任意两个数的和为m的倍数,则称它们为一个倍数对。给定一个数列和m,问数列中有多少个倍数对。n,m<=1000。

这个数据量没有难度。直接暴力枚举数列中任意两个数字,注意枚举完(i,j)后不要再枚举(j,i)了,然后乘积对m取模,如果是0则就是m的倍数,计数。

大数据量做法还没想出来。

第八题

有n行m列的空地,有一些位置种了草,每一个月后草会向上下左右的空地延伸,问k个月后空地的情况是怎样的。读入就是空地的初始情况二维数组和k。数据最大1000。

直接BFS就可以。读入空地后先把所有的已经有草的坐标记下来,然后对每个坐标进行深度为k的bfs,当无法进行搜索时直接退出。最后输出草的情况就行。记得注意边界,别让搜索出了界。

第九题

构造一个n行m列的螺旋矩阵,比如一个3行3列的螺旋矩阵长这样:

1 2 3

8 9 4

7 6 5

然后问这个矩阵中第r行c列的元素值是多少。

其实可以不构造完就能知道答案。这个螺旋矩阵从左上角出发,先向右,走到右边界向下,走到下边界向左,走到左边界向上,走到上边界向右。边界是已经填了的数字和数组边界。就这样一直填下去,直到当前的填数位置是(r,c)就可以输出答案。

第十题

有n个节目,从中选取m个节目进行演出,每个节目都有一个好看程度,要选取前m个最好看的节目进行演出。n个节目的演出顺序不能改变。n最大1e5。

简单的结构体排序。成员有两个,一个好看度,一个顺序。顺序就是读入时循环中的i,好看度是读进去的。首先按好看度从大到小排序,取前m个元素,再对这m个元素按顺序从小到大排序,然后按顺序输出好看度。

打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2018-2020 Shawn Zhou
  • Powered by Hexo Theme Ayer
  • PV: UV:

感谢打赏~

支付宝
微信