2020-2021:teams:acm_life_from_zero:5.16-5.22
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:5.16-5.22 [2020/05/21 19:35] lak [团队训练] |
2020-2021:teams:acm_life_from_zero:5.16-5.22 [2020/06/06 14:28] (当前版本) lak [李元恺] |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 2020.5.20 [[2018-2019 ACM-ICPC, Asia Nanjing Regional Contest]] | 2020.5.20 [[2018-2019 ACM-ICPC, Asia Nanjing Regional Contest]] | ||
| + | ====== 个人训练====== | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| - | ===== 专题 ===== | + | 摸了一周 |
| - | 没有专题 | + | |
| - | ===== 比赛 ===== | + | |
| - | 没有比赛 | + | |
| - | ===== 题目 ===== | + | |
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| ===== 专题 ===== | ===== 专题 ===== | ||
| 行 24: | 行 20: | ||
| 没有比赛 | 没有比赛 | ||
| ===== 题目 ===== | ===== 题目 ===== | ||
| + | 补补题：[[http://codeforces.com/contest/1303/problem/G|题目链接]] | ||
| + | |||
| + | 题意：求$n(1.5*10^5)$个点的树上路径$p_1 ... p_k$使这些点的权值$a_1 ... a_k$的加权和$\sum_{i=1}^k ia_i$最大 | ||
| + | |||
| + | 题目涉及到路径，可以考虑点分，点分时记录 | ||
| + | |||
| + | 考虑从某一点出发的所有路径，对其中任一条路径u，记$s1=\sum_{i=1}^k a_i,s2=\sum_{i=1}^k ia_i$, | ||
| + | |||
| + | 则其他无公共点的路径v与他组成的路径的加权和可以表示为$S=s2_v+s2_u+s1_u*l_v/s1_v*l_u (路径出发的方向影响)，l为路径长度$ | ||
| + | |||
| + | 所以对u，需要找到使S最大的路径v。 | ||
| + | |||
| + | 看到上述公式表达式类似直线，可以考虑点分后用凸包或李超线段树来维护表达式对应的直线；上述量可以在点分治中记录，复杂度O(nlogn^2)) | ||
| + | |||
| + | 代码：咕咕中orz | ||
| + | |||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| - | ===== 李元恺 ===== | + | |
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| ===== 袁熙 ===== | ===== 袁熙 ===== | ||
| + | 同本周题目：cf1303G[[http://codeforces.com/contest/1303/problem/G|题目链接]] | ||
| - | ====== 个人训练====== | ||
| - | ===== 李元恺 ===== | ||
2020-2021/teams/acm_life_from_zero/5.16-5.22.1590060945.txt.gz · 最后更改: 2020/05/21 19:35 由 lak
