2020-2021:teams:hotpot:200516-200522
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200516-200522 [2020/05/22 18:01] misakatao 更新 |
2020-2021:teams:hotpot:200516-200522 [2020/05/22 18:27] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| ====专题==== | ====专题==== | ||
| - | ====个人练习==== | + | [[带花树|带花树]] |
| =====陶吟翔===== | =====陶吟翔===== | ||
| 行 20: | 行 20: | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | [[杜教筛|杜教筛]] | ||
| =====本周推荐===== | =====本周推荐===== | ||
| 行 32: | 行 34: | ||
| ===林星涵：=== | ===林星涵：=== | ||
| + | |||
| + | [[带花树|带花树]] | ||
| ===郭衍培：=== | ===郭衍培：=== | ||
| + | |||
| + | [[http://codeforces.com/contest/464/problem/D|题目链接]] | ||
| 题目大意：一个人一开始有k种武器，均为1级。打n个怪。每打死一个怪，就会等几率地掉落一种武器（掉落每种武器的几率都是1/k）。设掉落的这种武器当前等级为t，则掉落的武器等级为[1,t+1]的随机数。每次这个人留下该种类等级较高的，并卖掉等级较低的。等级为t的武器卖t元。问这个人打完n个怪后的钱数的期望。输出只需要和答案相差$10^{-6}$以内即正确。（$n\le 10^5，k\le 100$） | 题目大意：一个人一开始有k种武器，均为1级。打n个怪。每打死一个怪，就会等几率地掉落一种武器（掉落每种武器的几率都是1/k）。设掉落的这种武器当前等级为t，则掉落的武器等级为[1,t+1]的随机数。每次这个人留下该种类等级较高的，并卖掉等级较低的。等级为t的武器卖t元。问这个人打完n个怪后的钱数的期望。输出只需要和答案相差$10^{-6}$以内即正确。（$n\le 10^5，k\le 100$） | ||
| 解题思路：每种武器都可以分开看。即，假设只有一种武器，打死一个怪后有1/k的几率掉落一件武器。最后只需要将答案乘k。这道题很容易想到dp。dp[i][j]表示武器初始等级为j，用它打i个怪后的期望收益。显然有$dp[i+1][j]=\frac{k-1}{k}dp[i][j]+\frac{1}{k}(\frac{1}{j+1}(dp[i][j+1]+j)+\frac{j}{j+1}(dp[i][j]+\frac{j+1}{2}))$，时间复杂度$O(n^2)$，过不了。接下来的优化就是最神奇的地方。因为输出只需要和答案差距在$10^{-6}$以内。可以证明，产生大于500级的武器的几率非常低，远低于$10^{-16}$。所以，不需要考虑产生大于500级武器的情况。时间复杂度$O(500n)$。 | 解题思路：每种武器都可以分开看。即，假设只有一种武器，打死一个怪后有1/k的几率掉落一件武器。最后只需要将答案乘k。这道题很容易想到dp。dp[i][j]表示武器初始等级为j，用它打i个怪后的期望收益。显然有$dp[i+1][j]=\frac{k-1}{k}dp[i][j]+\frac{1}{k}(\frac{1}{j+1}(dp[i][j+1]+j)+\frac{j}{j+1}(dp[i][j]+\frac{j+1}{2}))$，时间复杂度$O(n^2)$，过不了。接下来的优化就是最神奇的地方。因为输出只需要和答案差距在$10^{-6}$以内。可以证明，产生大于500级的武器的几率非常低，远低于$10^{-16}$。所以，不需要考虑产生大于500级武器的情况。时间复杂度$O(500n)$。 | ||
2020-2021/teams/hotpot/200516-200522.1590141711.txt.gz · 最后更改: 2020/05/22 18:01 由 misakatao
