关注
拓扑排序+GTO博弈论。
所谓的基环树指的是:在一棵树的基础上加上一个环。
以后大家看到这种:每个人都会按照最优策略进行选择,最后判断谁会获胜。这种字眼的时候,基本就可以确定是一个GTO(博弈论)的题目。基本的做题思路就是找到一个规律可以直接得出结论的。
对于这道题,有一个显而易见的结论,如果x在环中,那么无论如何删点都不可能删的掉,因此必然是Draw。
如果点不在环中呢?
我们可以考虑在删除x点之前(包括x),有多少个节点是可以删除的?假设这个值是cnt。
如果cnt是偶数的话,那么Xiaoyo作为先选取的一方,一定是无法删除这个点的。因为双方的操作是对称的。
反之,则是Pyrmont获胜。
因此大题思路与拓扑排序类似,不断地将度数为1的节点加入队列,记录在删除x节点之前最多可以访问的节点数(包括x节点)。最后判断x的奇偶性即可。
需要注意的是
如果x节点是在环中的,那么我们永远无法遍历到这个节点,此时必然是Draw。
如果x节点的度数初始值就是1,那么此时Xiaoyo获胜。
C++
查看原帖
点赞 3
相关推荐
牛客85811352...:测开问这么简单?
查看8道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# xx岗简历求拷打 #
1821次浏览 22人参与
# 金三银四,你有感觉到吗 #
687587次浏览 6071人参与
# 有转正机会的小厂实习值得去吗? #
2646次浏览 37人参与
# 携程求职进展汇总 #
874587次浏览 5679人参与
# 你最讨厌面试被问什么 #
3856次浏览 46人参与
# 哪些公司开春招了? #
28864次浏览 192人参与
# 秋招踩过的“雷”,希望你别再踩 #
187036次浏览 1693人参与
# 机械制造2024笔面经 #
1540340次浏览 13005人参与
# 毕业季等于分手季吗 #
54449次浏览 649人参与
# 牛客租房专区 #
157249次浏览 1775人参与
# 26届的你,投了哪些公司? #
256361次浏览 1686人参与
# 文科生还参加今年的春招吗 #
13013次浏览 98人参与
# 找实习多的是你不知道的事 #
1805337次浏览 20691人参与
# 反问环节如何提问 #
132010次浏览 2702人参与
# 大家每天通勤多久? #
86783次浏览 851人参与
# 记录实习开销 #
187861次浏览 986人参与
# 校招笔试 #
417529次浏览 2797人参与
# 找工作中的小确幸 #
81485次浏览 451人参与
# 正在实习的你,几点下班 #
300331次浏览 2225人参与
# 如何缓解入职前的焦虑 #
261283次浏览 1466人参与
凡岛公司福利 782人发布