ZigZagK

Never give up fighting!

[折半搜索]TopCoder【EllysRPS】题解

题目概述

你要跟一共 \(m\) 个人玩剪刀石头布的游戏,其中 R(Rock) 胜 S(Scissors)、S(Scissors) 胜 P(Paper)、P(Paper) 胜 R(Rock)。如果出同样的算平局。你与一个人共玩 \(n\) 局,胜的 局数多的人胜出,如果胜的局数相同就打成平手。你现在知道了这 \(m\) 个人在每局分别会出什么,你想要确定一个出拳的序列,使得在与 这 \(m\) 个人的游戏中都能打成平手。输出满足条件的序列数。

解题报告

\(O(3^{n}m)\) 会炸掉,然后我们就会发现折半搜索就行了……效率 \(O(3^{n\over 2}m)\)

示例程序

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]