9-28 新生赛预热赛 题解

  • 2019-09-28
  • 252
  • 0
  • 0

A – a+b的问题(T组输入)

 

B – 图灵的密码

最简单粗暴的方法:

或者

好孩子不要这么写。

超级好孩子可以写的比这个还短。

C – 绝对素数

会判素数就可以了。基本的语言基础。

 

D – 面朝大海 春暖花开 [ 数据加强版 ]

看数据范围:1 <= n, m <= 100000。

如果是朴素模拟(在这里就是写二重循环,时间复杂度O(n^2)),最坏的情况下需要操作1e10次,必T。(一般 1e8 就是极限了)

时间复杂度是什么?大O是什么?-> https://blog.csdn.net/so_geili/article/details/53353593

这个题,实际上仍然可以用模拟来做,但是肯定不能用for循环++来模拟了,我们可以用计算的方法。

对于一组最终在[ l , r ]上查询的数据一次在[c , d] 上的区间种花,有4种情况会出现:

(画画图就知道了)

然后计算端点值的差即可。

此算法空间复杂度、时间复杂度均为O(n),需要2n个int,离线算法。此算法适用于1350,上述代码也可AC1350。

也可以用前缀和做,快糙猛。

 

也可以用st/bit做,不过没啥必要,小题大做了。还慢

不贴代码了,贴了你们也看不懂,看的懂的都不用贴。

E – 整数划分的空间优化问题

很简单的动态规划,二维优化为一维。

为什么不能朴素DFS?->有大量的重复计算,会超时。

动态规划是什么?-> 百度谷歌

如果语言基础还有不足,或基础算法还没有接触过,建议先跳过。

优化前可写为二维DP,优化后一维。原题有点卡常 傻逼行为,时间放宽至2s。

可参考 http://www.voidcn.com/article/p-nwdvvcjj-ng.html

不要在意这种C++写法。

 

F – Relative Molecular Mass

trie,外加简单的一些类表达式处理。

无非繁琐了一点,难度实际上不高。

代码有点丑。

 

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

评论

还没有任何评论,你来说两句吧