1 条题解

  • 0
    @ 2024-11-10 20:49:02

    ​ 首先理解一下题意:场上共有 nn 个随从, 施放法术 "亵渎""亵渎" 时,对场上所有随从造成一点伤害, 如果有随从的血量降低至 00 点,其立即死亡, 若其为初始在场上的的随从,则召唤两个血量为 hih_i 的随从加入场上, 然后再次施放法术。

    ​ 题意不难理解,就是找到数组中第一个没有出现过的非负自然数,简单来说,即为找数组的 mexmex (从 11 开始), 关键在于如何处理 "亡语""亡语" 召唤的随从。

    ​ 由于召唤的随从是后来加入的战场,这就等价于召唤的随从一开始就具有额外的把他召唤出来的随从的血量 hih_i ,所以我们把所有召唤的随从的血量加上把他召唤出来的随从的血量 hi+Hih_i+H_i,与初始随从的血量 hih_i 共同存入一个数组

    ​ 那么现在只需要求出该数组的 mexmex ,求区间 mexmex 的时间复杂度为 O(n)O(n) : 遍历一遍数组,记录所有出现的数,遍历记录表,即可求出 mexmex 。特别的,我们需要注意:由于数组最多只有 21062*10^6 个数, 求得的 mexmex 必然小于 21062*10^6 ,所以遍历数组时,遇到大于 21062*10^6 的数,我们不做记录。

    ​ 求出 mexmex 后我们就有了最终状态,再遍历一边数组求出血量和即可。

    ​ 由于每个测试点还有 TT 组测试数据, 所以最终的时间复杂度为 O(Tn) O(Tn)

    • 1

    信息

    ID
    224
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    152
    已通过
    9
    上传者