2020-2021:teams:alchemist:weekly_digest_9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 15:45] maxdumbledore [专题] |
2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 17:05] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 比赛简记 ===== | ===== 比赛简记 ===== | ||
| + | 2020.08.01 2020牛客暑期多校训练营（第七场） ''pro 5/6/10 rank 27/???'' | ||
| + | |||
| + | 2020.08.03 2020牛客暑期多校训练营（第八场） ''pro 4/5/11 rank 42/???'' | ||
| + | |||
| + | 2020.08.06 2020-2021 BUAA ICPC Team Supplementary Training 02 ''pro 6/6/10 rank 4/???'' | ||
| ===== Max.D. ===== | ===== Max.D. ===== | ||
| 行 11: | 行 16: | ||
| 本周暂无 | 本周暂无 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| - | 本周暂无 | + | [[https://ac.nowcoder.com/acm/contest/5673/A|牛客第八场 A. All-Star Game]] |
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/888/E|去年牛客第八场 E. Explorer]] | ||
| + | |||
| + | 两道都是一种类型的题目，无向图维护连通性，模板题还可以参考LOJ 121（去年不补题，欠下的一年之后还qwq）。 | ||
| + | |||
| + | 离线之后，可持久并查集（线段树分治，xsy下面有提到）和LCT都可以做，后者效率稍慢。 | ||
| ===== Hardict ===== | ===== Hardict ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 一场atcoder(全是板子题) | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | Gym - 101234D - Forest Game | ||
| ===== MountVoom ===== | ===== MountVoom ===== | ||
| 行 37: | 行 52: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | 需要更新板子，多读题 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| 行 100: | 行 116: | ||
| === 来源： === | === 来源： === | ||
| + | |||
| + | [[https://codeforces.com/gym/101234/problem/D|Codeforces Gym 101234D Forest Game]] | ||
| === 标签： === | === 标签： === | ||
| + | |||
| + | 期望，点分治，FFT | ||
| === 题意： === | === 题意： === | ||
| + | |||
| + | 给定一棵树，每次随机选一个未被选过点，获得改点目前联通块大小的分数，并删除该点 | ||
| + | |||
| + | 求期望分数 | ||
| === 题解： === | === 题解： === | ||
| + | |||
| + | 考虑$u,v$两点,其至多提供一次贡献,当且仅当$u \leftrightarrow v$路径存在,且此次选取$u,v$两点之一 | ||
| + | |||
| + | $dis(u,v)=dis$,则贡献为$\frac{2}{dis+1}$ | ||
| + | |||
| + | 再考虑单点还有一个贡献，则答案为$n+\sum_{i=1}^{n-1}cnt[i]\frac{2}{i+1},cnt[i]为树中路径长度为i的个数$ | ||
| + | |||
| + | 考虑点分治进行统计，可以利用FFT进行优化 | ||
| + | |||
| + | 具体操作是，定根下，构造一个关于每种$depth$个数的生成函数，然后做卷积 | ||
| + | |||
| + | 然后就可以利用容斥$O(N\log^{2}{N})$求解 | ||
| + | |||
| + | 但需要注意，因为FFT计算过多，可以预处理每次FFT的置换以及单位根值进行优化 | ||
| === 评论： === | === 评论： === | ||
| + | |||
| + | 多次计算FFT时可以牺牲一定空间预处理一些值优化时间 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
2020-2021/teams/alchemist/weekly_digest_9.1596786326.txt.gz · 最后更改: 2020/08/07 15:45 由 maxdumbledore
