题解 | #小红删树#

小红玩树

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 那么就小紫赢比赛

全部评论

相关推荐

昨天 08:58
已编辑
门头沟学院 Java
ttl: 3.19一面晚上过3.20二面3.23oc3.25offerbase:末9有一段中小厂实习一面面经:(总体时长一个小时二十分钟左右没什么八股,主要都是问项目和场景题1.实习(问了有四十分钟,感觉面试官很看重实习这一块,一直在拷打,问到后面我都要疯了,好在准备得比较充分1️⃣用的是什么中间件,有参与技术选型吗,实习的项目里为什么选这个RabbitMQ而不是kafka,为什么不用RocketMQ,为什么放弃异步,自己的项目里面使用的是kafka,那你觉得项目和实习的中间件选型有差异的原因是什么,他们之间的区别在哪里,底层的原因知道吗(高柱到这里已经快疯了,但是硬着头皮答完了,主要是从一致性吞吐量和框架的契合度答,面试官说答得挺好的,应该是没什么问题,这一块就问了快半个小时,到这里我已经快疯了2️⃣项目怎么对接上下游3️⃣介绍项目的难点重点4️⃣微服务(高柱实习是单体项目没涉及这一块5️⃣Redis的使用2.项目:1️⃣智能客服是怎么应用在项目里的(langchain4j➕rag➕functioncalling)2️⃣RAG了解多少3️⃣文本向量化的难点是什么,了解哪些大模型的知识(我一点不懂,纯瞎扯,但貌似扯对了4️⃣对ai的态度是什么,aicoding相关5️⃣怎么保证多节点下Caffeine缓存里面数据都是一致的(答的是短ttl,面试官不是很满意,但是我确实不太懂这个怎么保证,后来查了还是不懂怎么保证6️⃣Redis的使用,和你的实习项目的使用有区别吗,还有一些引申问题3.八股(含量不高,就是走个过场1️⃣进程的内存布局2️⃣Redis三剑客3️⃣微服务相关知识(高柱已经忘得差不多了…勉强答上来4️⃣JVM5️⃣线程状态6️⃣线程安全,在你的实习项目里怎么保证线程安全的(又绕回来了4.智商题找异常球5.手撕:1️⃣五道sql,不难2️⃣力扣不重叠的滑动窗口数组,贪心➕双指针秒了强度拉满了这个一面,高柱到后面人都是傻的二面面经:(就半个小时实习拷打,简历上写了几点就问了几点,问完就结束了,无手撕
查看19道真题和解析
点赞 评论 收藏
分享
在笔试的大西瓜很矫健:校招数分不用想了,这经历和学历都不够用,大厂更别想,初筛都过不了,说点不好听的小厂数分都进不去(小厂也是假数分),要两个对口实习+3个项目(或者3+2),而且要有含金量才能补一点你的学历劣势。 建议刷实习,社招找数分,校招看运气,能入行业就行,可以运营转数分
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务