• <small id="ck0wk"><meter id="ck0wk"><menuitem id="ck0wk"></menuitem></meter></small>

  • <big id="ck0wk"></big>

  • 鍍金池/ 問答/人工智能  C++  網絡安全  HTML/ 一道hihocoder的編程題

    一道hihocoder的編程題

    題目如下

    時間限制:20000ms
    單點時限:1000ms
    內存限制:256MB

    描述

    有n個怪物,第i個怪物的血量是ai,設這n個怪物組成的集合為T。

    現在你有一個技能,發動一次需要花費一個金幣,當技能發動后,所有存活的怪物的血量都會-1,當怪物血量降為0后視為被消滅。

    特別的,如果這次發動的技能后有至少一只怪物死亡,你都將獲得一個金幣的獎勵。

    令f(S)為消滅集合S中的怪物總共需要付出幾個金幣,即花費的金幣數量減去獲得的獎勵金幣數量。

    求∑S?T f(S),答案對109+7取模。
    輸入

    第一行一個正整數n。

    第二行n個正整數ai,表示第i個怪物的血量。

    1 ≤ n ≤ 105,1 ≤ ai ≤ 109
    輸出

    輸出一個非負整數,表示答案。
    樣例輸入

    2
    1 2
    

    樣例輸出

    1
    
    

    我理解的思路
    付出的金幣數量=技能的發動數量-獎勵的金幣數量。
    技能的發動數量為:生命值最高的怪的生命值。
    獎勵的金幣數量為:不同的生命值數量。
    令g(S)表示集合S的生命值的最大值,h(S)表示集合S中不同生命值的數量,則f(S)=g(S)-h(S)。

    我的疑惑
    一個具體集合的金幣數量的計算很簡單,但是如何高效的枚舉每個集合(每個集合怪物的最大生命值,以及小于最大生命值的怪物的構成),并且進行計算

    clipboard.png

    clipboard.png
    這張圖片的第二點和第三點不太理解

    最后我希望有具體可行的代碼可以參考
    附上題目鏈接鏈接

    回答
    編輯回答
    扯機薄

    就是普通的排列組合,別想多了。

    • 第二點:最大生命值為$w$,那么

      • $x$個生命值為$w$的里面至少要選一個:$2^x-1$
      • $y$個生命值小于$w$的有沒有都行:$2^y$
    • 第三點:包含生命值$w$,那么

      • $n-y$個生命值大于$w$的有沒有都行:$2^{n-y}$
      • $y$個生命值小于$w$的有沒有都行:$2^y$

    至于它為什么$2^y$都要減$1$,想了一下,覺得意義不明。倒是$2^x$不減$1$肯定有問題。

    2018年4月18日 11:18
    編輯回答
    苦妄

    把a1~an 按生命值分類 排序 得到k個集合 b1~bk
    g(s)的和等于

    gs = 0 
    for bi in list<b> 
        w = b集合的生命值
        count = (2^len(bi)-1)*2^len(b1,...bi-1)
        // count代表最大生命值為w的所有集合的數量, 其中每個集合都需要 w 個金幣
        gs += w * count
    

    h(s)的和等于

    hs = 0
    for bi in list<b>
        w = b集合的生命值
        count = (2^len(bi)-1)*2^(len(b1,...bi-1)+len(bi+1,...bk))
        // count代表所有集合里包含生命值為w的集合的數量, 其中每個集合都會在殺死w時都會獎勵 1 個金幣
        hs += count
        
    2018年9月8日 00:55
    男生女生一起差差差带痛声,插曲的痛的视频30分钟,男生和女生在一起差差的视频