排名比想像高好多 不错
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 就是答案了