2020.10.08【普及组】模拟赛C组总结

TOP

T1 蚂蚁(20)

题目大意:有一根杆子,上面有一些蚂蚁,蚂蚁到达杆子边缘就会掉下去。求最少全部掉下去的时间和最多时间。
这题不知道怎么错了,和正解一模一样,重新打就对了。思路:因为蚂蚁相撞绝对不是最优的,所以只需要考虑同时往一边走或两边走的时间就行了。

T2 max(0)

题目大意:把一个数拆分成几个数的和,使这几个数乘积最大。
这题和正解差了一点点。思路:为了乘积最大化,必须差最小。所以从小到大,从2开始递增枚举,直到多出来再从后往前加。

T3 围攻(100)

题目大意:让你构造一个长度为 n n n的01串,求没有两个1相邻的串的方案数。
这题有三种做法:

  1. dp,因为dp可以优化成倍增形式,所以不会超时。
  2. 矩阵乘法。这题简单的打表就能判断出这是个斐波那契数列,矩阵乘法就可以优化时间复杂度。
  3. 玄学剪枝优化。我们发现,虽然 n < = 1 0 18 n \small<=10^{18} n<=1018,但是它有一个模数100000007。于是,根据模数,我们可以考虑找循环节。接着,找到循环节后,因为循环节太大,我们必须要用 r e g i s t e r register register来优化循环部分,而参与计算的所有变量都要用 r e g i s t e r register register,否则必然超时。(本人测过, l o n g l o n g 1.6 s longlong1.6s longlong1.6s r e g i s t e r i n t 1.1 s register int1.1s registerint1.1s

T4 取物游戏(0)

题目大意:有一个游戏,里面有初始分数和最终分数,让你在满足初始分数最大情况下输出最终分数,有相同的初始分数则结束游戏。
这题考试打了个暴力,结果没分……
正解还待消化……

完成情况

  • T1
  • T2
  • T3
  • T4
    原文作者:icehomegre
    原文地址: https://blog.csdn.net/qq_42989972/article/details/108963312
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞