xzm2019

北京理工大学2020年蓝桥杯校内选拔赛题解
A. 猴子摘桃按题意倒推即可答案:22B. 数学家穷举-5000~5000内所有数字,需要进行1e12次枚举。但是...
扫描右侧二维码阅读全文
23
2019/11

北京理工大学2020年蓝桥杯校内选拔赛题解

A. 猴子摘桃

按题意倒推即可

答案:22

B. 数学家

穷举-5000~5000内所有数字,需要进行1e12次枚举。

但是,容易想到,要让三个绝对值很大的数的三次方之和等于一个小数,这三个数必然不可能符号全相同。

因此,对于第一个数,只枚举-5000~0,第二个数只枚举0~5000,第三个数枚举-5000~5000,这样就将枚举次数缩小到了1/4.

一个更好的优化策略是先枚举第一,第二个数,计算它们的三次方之和,储存到map里,然后再枚举第三个数,将第三个数求立方后,在map里寻找有无和此数相加得到答案的,此时运算次数降到了$(5000 \times 5000)+10000 \times log(5000\times 5000) \approx 2.5e7 $

答案:-1972,-4126,4271

C. 死亡游戏

此题面原本来自于一道概率dp,但是比原来那道简单得多。只需要观察到,老虎必然是一对一对死亡,那么,奇数个老虎的情况下,最终必然会剩下一只老虎与人匹配上,因此人不可能活下来。
有能力的同学,可以思考一下,编写一个程序,计算老虎数量为偶数的情况下,人活到游戏结束的概率。

答案:0.000000

D. 逆元问题

可以暴力求解,也可以用费马小定理求解,也可以用扩展gcd求解。

答案:703240518

E. NP完全问题

本题的数据共有30个,完全暴力枚举,运算次数是$2^{30} \approx 1e9 $ ,考虑到大常数,这个解法很勉强。

正解的思想是折半,先枚举前15个物品取或不取,将它们存放进map里,再枚举后15个物品,在map中寻找相加能够得到所求答案的方案,运算次数是$ 2^{15}+2^{15}\times log(2^{15}) \approx 5e5 $

本题保证答案唯一,因为数据是用背包密码算法体系的思想生成的,如上暴力求解答案的过程实际上就是暴力破解密码的过程,尝试将上述数据逐个求它们在模140737488355337意义下的逆元,看看能不能找到一些有趣的性质。

答案:110010000011111110101001001001

F. 火星救援

经简单计算分析可知,题目叫我们求的是$s*(1+\frac{1}{2}+\cdots+\frac{1}{n})$。由于运算次数较多,后面的部分可以算预处理前缀和解决。

G. 龙龙的数字游戏

其实是一个简单的计数问题,只需要考虑每次新加一个数的贡献的即可。分三类情况讨论

  • 加入$0$:乘积为$0$的区间个数加上当前总个数
  • 加入正数/负数:乘积为$0$的区间个数加上上一个$0$及之前的部分。只需要统计上个$0$以后的区间后缀积的正负个数对应加上即可。

H. Liang The Mighty

由冗长的题面分析可知,题目需要求$n^2$的距离里求第$p\%$的距离。直接求解可以得到$50\%$的分数,使用nth-element将复杂度降到$O(n^2)$即可通过此题。

I. 传球游戏

不难注意到关系只有3个,一共只有8种可能。暴力枚举8个情况,计算出对应的方案数,和输入进行对比判定。

另解:$k=1$时特判,$k>=2$时取出每个人做两轮游戏后球回到自己手里的方案,这相当于该点的度数。据此可唯一确定一种连边方案,只做一次判定即可。

J. strawberrry and geometry

其实就是两个圆交一个简单多边形的面积并问题……QQ图片20191123212849.jpg

Last modification:November 23rd, 2019 at 09:29 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment