U471725题解

zhujianheng · 2025-09-02 18:59:32 · 个人记录

这题比较简单，难度大约普及-到普及/提高-。这题涉及到的就是数学期望。

针对 20\% 的数据：

大暴力，时间复杂度 O(nmk)。

针对 40\% 的数据：

大暴力带点常数优化，时间复杂度依然 O(nmk)。

针对 60\% 的数据：

注意到每次射箭的期望得分是相同的，时间复杂度 O(nm)。

或者推出数学式子但是没想到期望得分相同，时间复杂度 O(k)。

针对 100\% 的数据：