2020-2021:teams:acm_life_from_zero:5.16-5.22

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:acm_life_from_zero:5.16-5.22 [2020/05/16 09:51]
lak 创建
+++ 2020-2021:teams:acm_life_from_zero:5.16-5.22 [2020/06/06 14:28] (当前版本)
lak [李元恺]
@@ 行 1: / 行 1: @@
-====== 组队训练 ======
+======= 2020/05/16-2020/05/22周报 =======
-比赛一场 待定
+====== 团队训练 ======
+.5.20 [[2018-2019 ACM-ICPC, Asia Nanjing Regional Contest]]
 ====== 个人训练======
-===== 李元恺 =====
+====== 李元恺 ======
+摸了一周
+====== 姜维翰 ======
+===== 专题 =====
+没有专题
+===== 比赛 =====
+没有比赛
+===== 题目 =====
+====== 袁熙 ======
+===== 专题 =====
+没有专题
+===== 比赛 =====
+没有比赛
+===== 题目 =====
+补补题：[[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.1589593864.txt.gz · 最后更改: 2020/05/16 09:51 由 lak