2020-2021:teams:farmer_john:2020牛客暑期多校第九场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第九场 [2020/08/21 15:32] jjleo [题意] |
2020-2021:teams:farmer_john:2020牛客暑期多校第九场 [2020/10/07 21:25] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第九场====== |
| [[https://ac.nowcoder.com/acm/contest/5674|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5674|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 27: | 行 27: | ||
| 给定一棵$n$个点的树，$i$号点上有$i$号人，第$i$条边只能允许$[l_i,r_i]$的人通过，每个人可以强行走$k_i$次不允许走的边，问$i$号人能到达点的个数。$(2 \le n \le 10^5, 0 \le k_i \le 1)$ | 给定一棵$n$个点的树，$i$号点上有$i$号人，第$i$条边只能允许$[l_i,r_i]$的人通过，每个人可以强行走$k_i$次不允许走的边，问$i$号人能到达点的个数。$(2 \le n \le 10^5, 0 \le k_i \le 1)$ | ||
| ====题解==== | ====题解==== | ||
| + | 首先dfs一次确定所有点的父亲以及深度。接下来上线段树分治，启发式合并维护一个比较特殊的并查集，每个并查集里面是一个连通块，除了常规的fa和siz，还要维护连通块最浅点以及所有“儿子”的siz之和。最后答案如果$k_i=0$则直接返回siz否则返回siz加上最浅点父亲所在连通块大小以及所有儿子的siz之和。可以发现这几个东西都是可以撤销的，细节比较多，一定要注意每个量的具体含义以及操作的顺序。 | ||
| =====E.===== | =====E.===== | ||
| **solved by 2sozx** | **solved by 2sozx** | ||
| 行 36: | 行 37: | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个序列，每个数有一种颜色，现在选出任意个数使得这个序列中拥有全部颜色且选出元素的最大值与最小值的差值最小。 | ||
| ====题解==== | ====题解==== | ||
| + | 滑动窗口滑就完事了。 | ||
| =====G.===== | =====G.===== | ||
| **upsolved by** | **upsolved by** | ||
| 行 62: | 行 65: | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个$n \times m$的$01$矩阵，求有多少个子矩阵满足四边都是$1$，中间部分$01$数量相差不超过$1$，且长宽均大于$1$。$(n,m \le 500)$ | ||
| ====题解==== | ====题解==== | ||
| + | 考虑枚举两列，保证两列都是$1$的情况下（否则清空），维护一下全$1$行及其前缀和，从上往下扫一遍即可。 | ||
| =====K.===== | =====K.===== | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一棵树，两个人各在一个节点，前者以$2m/s$追后者，后者以$1m/s$速度逃离，每条边长度为$1m$，问最晚多久才被抓。 | ||
| ====题解==== | ====题解==== | ||
| + | 以追人那个人为根dfs，枚举最后逃到哪个点，算一下距离讨论是否合法即可。 | ||
| =====L.===== | =====L.===== | ||
| **upsolved by ** | **upsolved by ** | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第九场.1597995134.txt.gz · 最后更改: 2020/08/21 15:32 由 jjleo
