【题解】牛客练习赛2

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 Contest
观察符合题目要求的队A、B在三场比赛中的先后顺序会出现怎么样的情况。
无非两种,A>B出现两场,A<B出现一场; A>B出现一场,A<B出现两场; 分别观察第一场比赛、第二场比赛; 第一场比赛、第三场比赛; 第二场比赛、第三场比赛; 这三组比赛中A和B的顺序,如果在某一场比赛中A>B且另一场比赛中A<B,答案加一;
这个可以用逆序对做。
最后发现无论是哪种情况,合法的方案都会被加两次;
所以最后答案除以2就可以了。

T2 River
这种题目的通解就是二分导数计算时间然后看看总时间符不符合题目要求。
求导过程如下:
图片说明
图片说明

T3 Alliances
先看看一个帮派和一个点的最短距离是什么。
一个帮派会形成一棵树。这棵树的根节点是帮派中所有点的LCA。
如果首都在LCA上面或者LCA不在首都上面,那么答案就是LCA与首都的距离。
否则就找到帮派中DFS序在首都附近的两个点。前面一个后面一个,求LCA,答案为LCA与首都的距离取min。
看完了一个帮派的情况,再看看一个联盟的情况。
一个联盟实质上是做了一样的事情。
我从每个帮派中选一个点作为其代表点。那么联盟就可以用这些点来表示。重复一遍上面的过程,再与每个帮派的ans取min,即为答案。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论
453799454
点赞 回复 分享
发布于 2020-02-03 16:36

相关推荐

点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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