2020-2021:teams:alchemist:weekly_digest_3

差别

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

到此差别页面的链接

--- 2020-2021:teams:alchemist:weekly_digest_3 [2020/05/22 18:49]
maxdumbledore [陈铭煊 Max.D.]
+++ 2020-2021:teams:alchemist:weekly_digest_3 [2020/05/24 21:14] (当前版本)
mountvoom [肖思炀 MountVoom]
@@ 行 2: / 行 2: @@
 ====== 个人总结 ======
 ===== 陈铭煊 Max.D. =====
-来推荐一道方法很神仙的题目，[[https://ac.nowcoder.com/acm/contest/5555/B|链接]]
+这一周的话主要打了两场牛客的比赛，其余的话没有学习知识
-比赛当场想破脑袋都没相出来，结果是利用了数据产生的随机性+容斥原理。
 ===== 龙鹏宇 Hardict =====
@@ 行 10: / 行 8: @@
 ===== 肖思炀 MountVoom =====
+这个人已经死在计网实验了
 ====== 本周推荐 ======
 ===== 陈铭煊 Max.D. =====
+来推荐一道方法很神仙的题目，[[https://ac.nowcoder.com/acm/contest/5555/B|链接]]
+比赛当场想破脑袋都没相出来，结果是利用了数据产生的随机性+容斥原理。
 ===== 龙鹏宇 Hardict =====
+**一道点分治**
-===== 肖思炀 MountVoom =====
+[[https://www.luogu.com.cn/problem/P3085|链接]]
+计数时没有用一般的容斥,而是直接计数
+**题意**
+一棵树,树上每条边黑或白色,统计有多少个$(u,v),s.t: \exists t \neq u,v,t在(u,v)简单路径上,且(u,t),(t,v)分别黑白平衡$。黑白平衡是指黑白数量边个数相同
+**题解**
+如果考虑$(u,v)$单独黑白平衡,令$边权值:黑:1;白:-1$;黑白平衡即$dis(u,v)=0$
+即为简单的点分治计数问题
+但根据题目条件,说明以$r$为子树搜索时,$(x,y)$黑白平衡说明$dis(r,x)=-dis(r,y),\exists z 为x或y的祖先,s.t:dis(r,x/y)=dis(r,z)$
+这其实可以在点分治搜索时判断对应点的$z$是否存在,但容斥计数会出现一定的问题
+这题需要考虑全局:
+$f[d][0/1]:表示正在搜索子树距离根距离为d且z存在/不存在的点的个数\\\\
+g[d][0/1]:表示之前搜索过距离根距离为d且z存在/不存在的点的个数$
+显然$f[d][0]与g[-d][1]组合,f[d][1]与g[-d][0/1]组合$
+===== 肖思炀 MountVoom =====
+考完计网再补，走了

2020-2021/teams/alchemist/weekly_digest_3.1590144598.txt.gz · 最后更改: 2020/05/22 18:49 由 maxdumbledore