差别

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

--- 2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 15:28]
mountvoom [比赛]
+++ 2020-2021:teams:alchemist:weekly_digest_9 [2020/08/07 17:05] (当前版本)
hardict [龙鹏宇 Hardict]
@@ 行 3: / 行 3: @@
 ===== 比赛简记 =====
+.08.01 2020牛客暑期多校训练营（第七场） ''pro 5/6/10 rank 27/???''
+.08.03 2020牛客暑期多校训练营（第八场） ''pro 4/5/11 rank 42/???''
+.08.06 2020-2021 BUAA ICPC Team Supplementary Training 02 ''pro 6/6/10 rank 4/???''
 ===== Max.D. =====
-==== 专题 ====
+==== 专题 ====
+复习了一下LCT
 ==== 比赛 ====
+本周暂无
 ==== 题目 ====
+[[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 =====
@@ 行 15: / 行 28: @@
 ==== 专题 ====
+无
 ==== 比赛 ====
+一场atcoder(全是板子题)
 ==== 题目 ====
+Gym - 101234D - Forest Game
 ===== MountVoom =====
@@ 行 29: / 行 45: @@
 ==== 题目 ====
+无
 ====== 个人总结 ======
 ===== 陈铭煊 Max.D. =====
+多练习，跟上队友思路。
 ===== 龙鹏宇 Hardict =====
+需要更新板子，多读题
 ===== 肖思炀 MountVoom =====
+感觉有些浮躁，希望能静下心来，做题的时候更加集中一些。
 ====== 本周推荐 ======
 ===== 陈铭煊 Max.D. =====
+===来源：===
-=== 来源： ===
+[[https://ac.nowcoder.com/acm/contest/5672/C|牛客2020多校第七场 C. A National Pandemic]]
-=== 标签： ===
+一道动态点分治题，后来又学到了一种树链剖分的做法，两个$\log$居然跑得比前者还要快。
-=== 题意： ===
+===标签：===
-=== 题解： ===
+动态点分治 树链剖分 树上距离的化简
+===题意：===
+$T$组数据，每组给出$n$个点组成的树，每个点有初始权值$F(x)=0$，以及$m$个操作，操作分三种：
+  - 给出点$x$和$w$，为所有点增加权值$w-dist(x,i)$，$dist(x,i)$表示$x$和$i$的树上距离；
+  - 更新点$x$处的权值为$\min(F(x),0)$;
+  - 查询某个$F(x)$。
+$1\le T\le 5,1\le n,m\le 5 \times 10^4,0\le w\le 10000$。需要对操作$3$进行回答。
+===题解：===
+看到这种树上距离有关的更新，很容易想到了动态点分治，可惜没学到家，比赛时还仔细回忆了半天细节，最后还没写出来。
+基本思路是，构造点分树，点分树上每个点实际上代表了一个树上连通区域，记录三个值$S,dp,ddp$，$S[i]$代表点分树上节点$i$的子树中，操作$1$被执行的总次数；$dp[i]$表示点分树上子树$i$中每个点到$i$父亲$pa[i]$的距离之和（如果$i$为根，取$pa[i]=i$），$ddp[i]$表示点分树上子树$i$中每个点到$i$的距离之和。这三个值都可以在点分树上不断走根的过程中求出。
+这个时候我们如果想知道操作$1$为$F(x)$带来的总的$dist$之和，可以从$x$开始，向上这样累加：
+<code cpp>
+    int x=u;
+    while (pa[u]) {
+        ans += ddp[pa[u]] - dp[u] + Dis(pa[u], x) * (S[pa[u]] - S[u]);
+        u = pa[u];
+    }
+</code>
+每次累加的值实际上是$pa[u]$的非$u$点分子树到$x$的总贡献，这个值由两部分组成，一部分是$pa[u]$在$u$这棵子树外的所有点，到达$pa[u]$产生的贡献和，也就是$ddp[pa[u]]-dp[u]$，另一部分就是$x$到$pa[u]$这段路径长度产生的贡献——所有这些点都要走过这一段路。
+注意一下，$ddp$的值不一定等于儿子$dp$值的和哦。另外$Dis$函数可以用$\mathrm{RMQ}$的方法求，这样就是真正$O(m\log n)$效率了。
+现在既然距离的贡献都解决了，其他就很容易了，操作$2$额外记忆一个$delta$即可。
+其实要是明白透彻了，实现起来也不难。
+第二种方法就显得很巧妙了：
+对于操作$1$，我们考虑一次修改对$y$来说会增加$w-dis(x,y)$。$W-dis(x,y)=w-(dep(x)+dep(y)-2*dep(lca))=w-dep(x)-dep(y)+2*dep(lca)$，所以，对于每次1操作，我们将其到根上所有点的$cnt+=2$，询问的时候那部分就是求它到根的权值和。所以，树上路径加，路径查询，用树链剖分，再用数据结构来区间加，区间求和即可。
+不得不说，这个式子很是传神。
+===评论：===
+好题
-=== 评论： ===
 ===== 龙鹏宇 Hardict =====
 === 来源： ===
+[[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 =====
 === 来源： ===
+[[https://ac.nowcoder.com/acm/contest/5673/A|牛客第八场 A. All-Star Game]]
 === 标签： ===
+线段树分治，并查集
 === 题意： ===
+球迷j愿意观看球员i的比赛需要满足：j是i的粉丝或者j和j'都是i'的粉丝且j'是i的粉丝。
+选择最少的球员进全明星赛，使得所有球迷都愿意观看。且有q次粉丝关系的修改，x是y的粉丝变为不是，x不是y的粉丝变为是，每次修改都会询问。
 === 题解： ===
+把球员和粉丝相连，答案即为(n个球员的连通分量个数)- (孤立球员个数)，如果有球迷的度为0，则答案为-1。
+把每个关系存在的时间划分成线段树上的log个区间，线段树每个节点维护了在这段时间存活的所有边，最后遍历一次线段树即可，因为回溯时需要删边，所以需要用启发式合并的并查集。
+最终复杂度为$O(n \log^2 n)$
 === 评论： ===
+比赛做得太慢了以至于没有时间写这道题...

CVBB ACM Team

用户工具

站点工具

差别

页面工具