2020-2021:teams:running_chicken:2020_summer_week3_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week3_report [2020/07/31 16:18] chenjiyuan3 [比赛] |
2020-2021:teams:running_chicken:2020_summer_week3_report [2020/08/07 21:47] (当前版本) selia [todolist（补题）] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| =====todolist（补题）===== | =====todolist（补题）===== | ||
| - | Codeforces Round #659 zrx A/D xx B/E cjy C/F | + | Codeforces Round #659 zrx A/D xx **B**/**E** cjy C/F |
| - | 2020牛客暑期多校训练营（第五场）zrx A/H xx K cjy G/J | + | 2020牛客暑期多校训练营（第五场）zrx A/H xx **K** cjy G/J |
| 2020牛客暑期多校训练营（第六场）zrx E xx I cjy **A**/F | 2020牛客暑期多校训练营（第六场）zrx E xx I cjy **A**/F | ||
| - | Codeforces Educational Round #92 xx E zrx F cjy G | + | Codeforces Educational Round #92 xx **E** zrx F cjy G |
| Codeforces Round #660 cjy C zrx D xx E | Codeforces Round #660 cjy C zrx D xx E | ||
| 行 30: | 行 30: | ||
| ====题目==== | ====题目==== | ||
| + | 2020牛客暑期多校训练营（第六场）A | ||
| =====ZRX===== | =====ZRX===== | ||
| 行 73: | 行 74: | ||
| =====cjy===== | =====cjy===== | ||
| + | |||
| + | African Sort | ||
| **题意** | **题意** | ||
| + | |||
| + | 给你一个排列，你每次可以选择一个下标集合，并把这个集合的元素随机排列，代价是这个集合的大小，求把原序列变成递增序列的期望代价。 | ||
| **思路**： | **思路**： | ||
| + | |||
| + | 首先把代价转换为每一个元素被选择的次数。有一个推论对于一个n元环，随机一次后，每个元素所在环的大小等概率分散在1-n。因此最优策略应 | ||
| + | |||
| + | 该是原排列中的每一个小环分别进行操作。操作代价可以通过之前的推论进行预处理。 | ||
| + | |||
| **评论**： | **评论**： | ||
| + | 这个题的思维度大，很有意思。 | ||
| =====XX===== | =====XX===== | ||
2020-2021/teams/running_chicken/2020_summer_week3_report.1596183533.txt.gz · 最后更改: 2020/07/31 16:18 由 chenjiyuan3
