题解 | #小红删树#
小红玩树
https://ac.nowcoder.com/acm/contest/121952/E
关于这个题,我一开始脑袋是很混乱的,因为这个本质上是一个博弈的问题,而博弈的问题则注重于思维,而非模拟的过程,所以我们做博弈主要的就是顾全大局即可,而不是专注于模拟,因为如果去模拟那些细枝末节只会让你越理越乱。
这个题主要就是一步,求最短路径这个题的题干的重点是在边权为1,如果边权为1就可以大胆用bfs了,因为bfs从根本上认为第一次到达的点就是最短路,这个结论只在边权为1的时候成立,所以题目给出这样的条件就是bfs了。
这里主播给大家归纳一下最短路分别的适合条件;
最短路分别有
bfs: 如果边权为1,无论是单源还是多源都是非常适合的,单源o(n+m) 多源(n*(n+m))
仅仅用了一个类似on方的复杂度
bellman-ford: 单源复杂度是o(nm)多源复杂度是(nn*m)适用于 点较多边较少的情况,这几乎也是最全能的一个公式了,比如Dijkstra算法只适用于边全为非负的情况,同时这个算法也是主播认为实现起来最简单的一个算法了。
Dijkstra: 可以说是求单源最短路径最快的一个方法了, 但是这个算法有很大的局限性,这个算法的建立在于一个数学结论的支撑,一旦题有些变式就很容易导致这个数学结论不成立,所以还是有一些局限性的。
整体的复杂度是o(mlogn) 多源最短路径复杂度是(nmlogn) 这个强烈适用于这样的一个数据 比如n为10000,m为10000
Floyd: 这个可以说是求多源路径的一个好方法,其复杂度是o(nnn)适用于n比较小m很大的这样一类数据
解题
回到这味着一个这是一个连通无向图,所以叶子节点判断非常容易,用刢接表储存图之后,只需要判断其对应vector数组里面size是不是1即可。
于是叶子节点的我们进行判断是否
disb[leaf]>=disa[leaf]*2//前面是b到节点距离,后面是a到节点距离,这个式子由来大家举个例子就可以得出
如果这个条件成立那么肯定是小红赢直接break就好 如果一直没有break 那么就小紫赢比赛
查看19道真题和解析
