2020-2021:teams:running_chicken:2020_summer_week5_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:running_chicken:2020_summer_week5_report [2020/08/14 14:56] chenjiyuan3 [题目] |
2020-2021:teams:running_chicken:2020_summer_week5_report [2020/08/18 17:58] (当前版本) yyxzhj |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| 2020牛客暑期多校训练营（第四场）CJY E/J XX G ZRX **I** | 2020牛客暑期多校训练营（第四场）CJY E/J XX G ZRX **I** | ||
| - | 2020牛客暑期多校训练营（第五场）CJY G/J ZRX A/H | + | 2020牛客暑期多校训练营（第五场）CJY G/J ZRX **A**/**H** |
| - | 2020牛客暑期多校训练营（第六场）CJY D XX I ZRX F | + | 2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D |
| - | 2020牛客暑期多校训练营（第七场）CJY E XX F ZRX A/C | + | 2020牛客暑期多校训练营（第七场）CJY E XX **F** ZRX A/**C** |
| - | 2020牛客暑期多校训练营（第八场）CJY D XX J ZRX B/C | + | 2020牛客暑期多校训练营（第八场）CJY **D** XX J ZRX B/C |
| - | 2020牛客暑期多校训练营（第九场）CJY **H** XX G ZRX L | + | 2020牛客暑期多校训练营（第九场）CJY **H** XX **G** ZRX L |
| - | 2020牛客暑期多校训练营（第十场）CJY G/H XX B/**D** ZRX F | + | 2020牛客暑期多校训练营（第十场）CJY G/**H** XX B/**D** ZRX F |
| 2020加赛1 CJY A/E XX B/C ZRX D | 2020加赛1 CJY A/E XX B/C ZRX D | ||
| 行 37: | 行 37: | ||
| 2020加赛2 CJY E | 2020加赛2 CJY E | ||
| - | 2015ICPC北京 CJY **C** XX D ZRX E (BFH) | + | 2015ICPC北京 CJY **C** XX **D** ZRX E (BFH) |
| =====CJY===== | =====CJY===== | ||
| 行 49: | 行 49: | ||
| ====题目==== | ====题目==== | ||
| - | 2015ICPC Beijing C | + | 2015ICPC Beijing C D |
| - | 2020牛客多校训练营（第八场）A | + | 2020牛客多校训练营（第九场）D H |
| - | 2019台大选拔赛 B/C | ||
| =====ZRX===== | =====ZRX===== | ||
| 行 123: | 行 122: | ||
| =====cjy===== | =====cjy===== | ||
| - | + | 2020牛客多校训练营（第九场）D | |
| - | 2020牛客多校训练营（第八场）A | + | |
| **题意** | **题意** | ||
| - | 有n个粉丝，m个球员，每个球员都有若干粉丝，一个粉丝会看另外一个球员的比赛，要不是他说这个球员的粉丝，要不是它喜欢的球员有粉丝会 | + | 有一棵树，n个点，每一条边只能是编号在$[L_i,R_i]$内的人通过，问每个人在通过不超过$K_i$($K_i\leq1$)条自己不能通过的边所能到达的点的数量。 |
| - | + | ||
| - | 看这个球员的比赛，求最少选几个球员就可以使所有人都去看比赛。 | + | |
| **思路**： | **思路**： | ||
| - | 显然这个是和连通块有关的问题，如果有一个粉丝是孤立的连通块，那么答案就是-1，否则答案就是连通块个数减去孤立孤立球员的个数。 | + | 容易想到用线段树维护加边，这样就转化成在线段树dfs，用可撤销并查集来维护连通块的一个问题。 |
| + | |||
| + | 当然K=0就已经完美解决了，我们发现K=1时要求的是这个连通块往外一步的点的个数，第一反应是去维护这个值，发现做不到，于是我们意识到 | ||
| + | |||
| + | 要利用树的性质。 | ||
| + | |||
| + | 考虑每个联通块维护除根节点向上以外的所有不属于这个连通块的一部点的数量，发现这个是可以维护的，只要维护每个连通块的最高节点就好 | ||
| - | 维护图联通块的方法，采用LCT，或者离线可撤销并查集。对询问建线段树，把加边删边看成区间加边，然后把边放在线段树上，对这个线段树跑 | + | 了。 |
| - | dfs用可撤销并查集维护连通性。 | + | 再利用栈去维护修改操作就可了。 |
| **评论**： | **评论**： | ||
| - | 做法比较神奇，这个是从对询问操作的考虑入手的。 | + | 可撤销并查集是一个好东西，就看你会不会用。 |
| =====XX===== | =====XX===== | ||
2020-2021/teams/running_chicken/2020_summer_week5_report.1597388160.txt.gz · 最后更改: 2020/08/14 14:56 由 chenjiyuan3
