差别

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

--- 2020-2021:teams:hotpot:200801-200807 [2020/08/07 16:08]
misakatao 更新
+++ 2020-2021:teams:hotpot:200801-200807 [2020/08/07 16:24] (当前版本)
misakatao 更新
@@ 行 16: / 行 16: @@
 =====比赛=====
+.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:433''
 =====题目=====
@@ 行 28: / 行 30: @@
 =====比赛=====
+.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:281''
 =====题目=====
@@ 行 40: / 行 44: @@
 =====比赛=====
+.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:103''
 =====题目=====
@@ 行 50: / 行 56: @@
 题目大意：
+在树上，支持以下三种操作：
-数据范围：
+、选定一个点 $i$，别的点 $j$ 的价值都加上 $w[i]-dis(i,j)$。
-解题思路：
+、选定一个点，它的价值值为 $min(价值，0)$。
-推荐理由：
+、询问某点的价值。
+数据范围：$1 \le n(点数)、m(询问数) \le 5e4$
+解题思路：经过分析后我们可以发现，一次$1$操作，对于任何一个点来说，权值的变化都是 $w-dep[x]-dep[p]+2*dep[k]$ (k是对于任何一个点来说从选定点 $x$ 到根的路径上最近的祖先).对于 $w-dep[x]$ 来说，所有点都是一样的，用一个全局的 $sum$ 来记录就可以。对于 $dep[p]$ 这部分同理记录次数，$2*dep[k]$ 这部分则需要利用树链剖分每次从 $x$ 到根每个点都$+1$，最后查询点时查询到根路径上的和来得到，对于二操作，我们单开一个新数组来记录操作对原值的影响就可以了。
+推荐理由：树链剖分一类比较经典的有关深度的操作。
 陶吟翔：
-题目大意：
+题目大意：有$n$个球员和$m$个粉丝，每个粉丝有可能是多个球员的粉丝，如果一个粉丝是某个球员$i$的粉丝或者他粉的球员的粉丝中有球员$i$的粉丝，那么他就回去看球员$i$的比赛，现在要选择若干个球员使得所有粉丝都来看比赛，问最少选几个，并且有$q$次询问，每次更改一个粉丝和球员的关系
-数据范围：
+数据范围：$1 \le n,m,q \le 2 \times 10^5$，粉丝和球员的粉丝关系$\le 5 \times 10^5$
-解题思路：
+解题思路：单独一个状态的问题可以通过并查集解决，然后题目还有$q$次询问，是比较经典的动态图连通块个数判断，只需要把所有的边按照出现时间挂在时间线段树上，然后从根往叶子走，经过的边加入即可，为了可以回溯，需要用可以撤销的并查集，并查集部分需要像一般的按秩合并并查集一样维护点个数，还需要维护粉丝的个数来方便答案的统计。对于边出现在哪些区间上，我们可以用map来记录每一个粉丝和球员的对应关系上一次从哪里开始，因为修改每次只会影响一对关系，所以每次只会有一对关系出现或消失，最后我们再把所有的关系遍历然后插入到线段树即可，由于题目保证了所有关系的和不会超过$5 \times 10^5$，修改不会超过$2 \times 10^5$，所以总体的复杂度不会有问题
-推荐理由：
+推荐理由：题目本身较为复杂，做题者需要进行模型的对应和转换将其看出其本质的动态图连通性问题，考察了做题者的模型观察能力，除此之外，时间线段树+可撤销并查集/动态树是处理动态图连通性的基本方法，本题考查这种方法也是考察了做题者的知识广度
 郭衍培：

CVBB ACM Team

用户工具

站点工具

差别

页面工具