2020-2021:teams:hotpot:200516-200522
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200516-200522 [2020/05/22 18:00] 喝西北风 |
2020-2021:teams:hotpot:200516-200522 [2020/05/22 18:27] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| ====专题==== | ====专题==== | ||
| - | ====个人练习==== | + | [[带花树|带花树]] |
| =====陶吟翔===== | =====陶吟翔===== | ||
| 行 20: | 行 20: | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | [[杜教筛|杜教筛]] | ||
| =====本周推荐===== | =====本周推荐===== | ||
| - | 陶吟翔：EducationalCodeforcesRound 76 - E | + | ===陶吟翔：=== |
| + | |||
| + | EducationalCodeforcesRound 76 - E | ||
| 题目大意：三个人在打ACM比赛，一共有$N$道题从$1$到$N$标号，每个人拿到了一些题目。现在他们三个希望第一个人拿到题目的一个前缀，第三个人拿到题目的一个后缀，第二个人拿到了剩下的。也就是说，第一个人拿到了题目$1$到$k$，第三个人拿到了题目$p$到$N$，其中$p \ge k$，当然也可以有一个人或两个人没有拿到题目。现在一次操作可以把某一道题从一个人移动到另一个人处，问最少操作多少次可以满足要求。 | 题目大意：三个人在打ACM比赛，一共有$N$道题从$1$到$N$标号，每个人拿到了一些题目。现在他们三个希望第一个人拿到题目的一个前缀，第三个人拿到题目的一个后缀，第二个人拿到了剩下的。也就是说，第一个人拿到了题目$1$到$k$，第三个人拿到了题目$p$到$N$，其中$p \ge k$，当然也可以有一个人或两个人没有拿到题目。现在一次操作可以把某一道题从一个人移动到另一个人处，问最少操作多少次可以满足要求。 | ||
| 行 29: | 行 33: | ||
| 解题思路：首先每个人拿到的题目编号是乱序的，我们可以先排序。然后我们的要求是第一个人的最大标号小于第二个人的最小标号，第二个人的最大标号小于第三个人的最小标号。由于要最小化操作的次数，所以我们要找到最长的满足条件的序列，然后调整剩余的题目。显然一个单调递增的子序列是满足条件的，而我们显然对于每一个位置不对的题目都只用一次操作就可以放到正确的位置，所以我们直接求出整体的最长上升子序列，然后答案就是用$N$减去它。 | 解题思路：首先每个人拿到的题目编号是乱序的，我们可以先排序。然后我们的要求是第一个人的最大标号小于第二个人的最小标号，第二个人的最大标号小于第三个人的最小标号。由于要最小化操作的次数，所以我们要找到最长的满足条件的序列，然后调整剩余的题目。显然一个单调递增的子序列是满足条件的，而我们显然对于每一个位置不对的题目都只用一次操作就可以放到正确的位置，所以我们直接求出整体的最长上升子序列，然后答案就是用$N$减去它。 | ||
| - | 林星涵： | + | ===林星涵：=== |
| + | |||
| + | [[带花树|带花树]] | ||
| + | |||
| + | ===郭衍培：=== | ||
| - | 郭衍培： | + | [[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.1590141603.txt.gz · 最后更改: 2020/05/22 18:00 由 喝西北风
