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

Author Avatar
ZigZagK 2018年4月24日 16:52
remove_red_eye 24

题目概述

你要跟一共 \(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)\)

示例程序

本文链接:https://zigzagk.top/2018/04/24/topcoderellysrps
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。