排名比想像高好多 不錯
https://i.imgur.com/v8lsPjg.png
Q1:
暴力模擬
Q2:
暴力模擬
Q3:
我的解:)
https://i.imgur.com/KZRk8zd.png
看到 1 <= n <= 10, 1 <= k <= 9 就想偷吃步打表
因為總共只有 90 種輸入
我可以提前算好 即使我的演算法可能要算個好幾分鐘才算得出來也沒關係
n <= 10, 長度10以內的回文只有 <= 10^5 種
我們可以遍歷他們、檢查 mod 1~9 是不是 0、再算出有多少排列組合
加到相應的 ANS[n][k]
中間可以寫得很隨便反正最後求得出 90 個答案就好 :)
後來結束前突然想到 萬一有人跟我一樣打表我會不會被判抄襲之類的
所以補傳了求 ANS 的程式
發現還是會過 不會 TLE, 所以是我多慮了
Q4:
第一個觀察: power 是來浪費你注意力的
可以直接求 ceil(health[i]/power)，出題人這樣很 low
再來，可以發現最後總時間是固定的，重點是殺怪順序
假設 health[] 和 damage[] 已經照最後的順序排好了 則受到的總傷害是
health[0] * damage[0] + (health[0] + health[1]) * damage[1] + ...
可以發現，假如存在 i，使得
health[i] * damage[i+1] > health[i+1] * damage[i]
則互換會更好，而這正好和比較 health[i] / damage[i] 等價
所以可以直接照 health[i] / damage[i] 來 sort 就是答案了