笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「水」CF768D Jon and Orbs

posted on 2020-05-28 19:41:51 | under 题解 |

首先 $dp$ 不难想,感觉这个 dp 十分 naive 不知道为什么 CF 的评分会很高,奇了怪了。

然后需要知道的是,为什么天数大部分人开的都是 $1e4$?这个可以算一波。由于概率 $p$ 发生的事件期望 $\dfrac{1}{p}$ 次实验会发生,那么不难知道凑齐所有的期望天数就是。

$$ \sum_{i=1}^{n}\frac{n}{n-i+1} $$

那么也就是调和级数 $n\cdot H(n)$,是 $O(n\ln n)$ 级别的,所以开 $1000\cdot \ln 1000$ 就好了。