2020-2021:teams:hotpot:200801-200807
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200801-200807 [2020/08/07 16:17] lotk |
2020-2021:teams:hotpot:200801-200807 [2020/08/07 16:24] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| =====比赛===== | =====比赛===== | ||
| + | 2020.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:281'' | ||
| =====题目===== | =====题目===== | ||
| 行 45: | 行 45: | ||
| =====比赛===== | =====比赛===== | ||
| - | 2020.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:281'' | + | 2020.8.2 [[abc174|Atcoder Beginner Contest 174]] ''prob:6/6/6'' ''rank:103'' |
| =====题目===== | =====题目===== | ||
| 行 72: | 行 72: | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：有$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$，所以总体的复杂度不会有问题 |
| - | 推荐理由： | + | 推荐理由：题目本身较为复杂，做题者需要进行模型的对应和转换将其看出其本质的动态图连通性问题，考察了做题者的模型观察能力，除此之外，时间线段树+可撤销并查集/动态树是处理动态图连通性的基本方法，本题考查这种方法也是考察了做题者的知识广度 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200801-200807.1596788272.txt.gz · 最后更改: 2020/08/07 16:17 由 lotk
