2020-2021:teams:farmer_john:week_17
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_17 [2020/08/28 12:47] 2sozx 创建 |
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!=== |
| - | * 分类： | + | * 分类：莫比乌斯反演，虚树。 |
| - | * 题意： | + | * 题意：给出一棵$n(2 \le n \le 2 \times 10^5)$个节点的树，边权为$1$。给定一个$1$到$n$的排列$a_i$，设$\operatorname{dist}(i,j)$为树上两点间距离，求$$\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n} \varphi(a_i \cdot a_j) \operatorname{dist}(i,j)\pmod{10^9+7}$$ |
| - | * 题解： | + | * 题解：因为$a_i$是$1$到$n$的排列，所以我们可以设$p_{a_i}=i$。同时有以下结论$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 因此扔掉前面的分母$n(n-1)$，原式转化为$$\sum_{i=1}^{n}\sum_{j=1}^{n} \frac{\varphi(i)\varphi(j)\gcd(i,j)\operatorname{dist}(p_i, p_j)}{\varphi(\gcd(i,j))} $$ 开始反演，枚举$d=\gcd(i,j)$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) [\gcd(i,j)=1] $$ 套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) \sum_{p|\gcd(i,j)}\mu(p)$$ 枚举$p$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \mu(p) \sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{dp} \right\rfloor} \varphi(idp)\varphi(jdp)\operatorname{dist}(p_{idp}, p_{jdp})$$ 枚举$T=dp$ $$=\sum_{T=1}^{n} \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT}) \sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 设$$f(T)=\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT})$$ $$g(T)=\sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 则原式转化为$$\sum_{T=1}^{n}f(T)g(T)$$ 其中$g(T)$可以在$O(n \log n)$的时间求出，考虑$f(T)$，本质相当于给$p_i$点一个权值$\varphi(i)$，然后把所有下标为$T$的倍数点$p_i$拿出来建虚树，dp跑一遍将每条边的长度乘以两侧节点权值和即可，总结点数是$O(n \log n)$的，因此总复杂度为$O(n \log n)$。 |
| - | * comment： | + | * comment：梦幻联动，双厨狂喜。 |
| =====个人训练===== | =====个人训练===== | ||
| ===== 2sozx ===== | ===== 2sozx ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 小学期摸了 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 摸了 | ||
| ===== Bazoka13 ===== | ===== Bazoka13 ===== | ||
| - | ==== 比赛 ==== | + | 小学期，摸s |
| - | + | ||
| - | ====题目==== | + | |
| ===== JJLeo ===== | ===== JJLeo ===== | ||
| + | 结膜炎复发，gg。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
2020-2021/teams/farmer_john/week_17.1598590034.txt.gz · 最后更改: 2020/08/28 12:47 由 2sozx
