2020-2021:teams:farmer_john:week_17
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_17 [2020/08/28 16:15] jjleo [JJLeo] |
2020-2021:teams:farmer_john:week_17 [2020/08/28 17:46] (当前版本) 2sozx [2sozx] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ====2sozx==== | ====2sozx==== | ||
| - | ===题目名称=== | + | ===CF895E Eyes Closed=== |
| - | * 分类： | + | * 分类：线段树，概率 |
| - | * 题意： | + | * 题意：给定一个长度为 $n$ 的数列，每次选择两个不相交区间，在两个区间中各任意选择一个数，交换两个数的位置，每次询问询问一个区间的和的期望。 |
| - | * 题解： | + | * 题解：考虑左侧区间长度为 $L_1$, 右侧区间长度为 $L_2$ ,左侧区间期望和为 $E(L_1)$ ，则删除一个数之后的期望和应为 $\frac{(L_1 - 1)E(L_1)}{L_1}$，考虑右侧选择一个数 $a_i$ 对左侧区间的贡献为 $\frac{\sum_{i \in L_2} a_i}{L_2} = \frac{E(L_2)}{L_2}$ ,考虑对于左侧子区间的影响应该考虑对左侧区间每个位置的贡献为 $\frac{E(L_2)}{L_2 L_1}$ 即可，线段树区间加区间乘维护即可。 |
| - | * comment： | + | * comment：概率巧妙使用，把每位的值转化成区间的和的期望， |
| ====Bazoka13==== | ====Bazoka13==== | ||
| - | ===题目名称=== | + | ===CF151E Smart Cheater=== |
| - | * 分类： | + | * 分类：数据结构 |
| - | * 题意： | + | * 题意：有$n$个车站，每个车站权值为$w_i$，$a$到$b$的车价为$w_b-w_a$，售票员可以选择一个区间$l~r$车票免费，但是第$i$到$i+1$个车站有$p_i$的概率有人查票，如果一个乘客查到逃票，罚款$c$，最大化售票员的收益期望 |
| - | * 题解： | + | * 题解：收益的期望是线性的，那么我们就可以对每个人单独考虑。对于第$i$个人，乘车区间为$l_i-r_i$，单人的期望就很容易写出来，票价/2-$p_l-p_r$的和*$c$/100，预处理出来概率的前缀和的话，就可以将期望分成$a_r+b_l$的形式，然后c[l,r]就可以用来表示期望，线段树维护一哈，然后就可以跑出来了 |
| - | * comment： | + | * comment：English太弱了导致半天没读懂题，， |
| ====JJLeo=== | ====JJLeo=== | ||
| ===CF809E Surprise me!=== | ===CF809E Surprise me!=== | ||
| 行 34: | 行 34: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 小学期摸了 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 摸了 | ||
| ===== Bazoka13 ===== | ===== Bazoka13 ===== | ||
| - | ==== 比赛 ==== | + | 小学期，摸s |
| - | + | ||
| - | ====题目==== | + | |
| ===== JJLeo ===== | ===== JJLeo ===== | ||
| + | 结膜炎复发，gg。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
2020-2021/teams/farmer_john/week_17.1598602540.txt.gz · 最后更改: 2020/08/28 16:15 由 jjleo
