menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[折半搜索]TopCoder【EllysRPS】题解
apps TopCoder
local_offer 查看标签
comment 0 条评论

题目概述

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

解题报告

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

示例程序

#include<map>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=20,maxm=100;
const int fl[3][3]={{0,-1,1},{1,0,-1},{-1,1,0}};//0 R|1 P|2 S

class EllysRPS{
    vector<string> a;int n,m;LL ans;int ID[256];
    vector<int> now;map<vector<int>,int> ha;
    void Dfs(int L,int R,int f){
        if (L>R) {f>0?ha[now]++:ans+=(LL)ha[now];return;}
        for (int i=0;i<3;i++){
            for (int j=0;j<m;j++) now[j]+=f*fl[i][ID[(int)a[j][L]]];
            Dfs(L+1,R,f);
            for (int j=0;j<m;j++) now[j]-=f*fl[i][ID[(int)a[j][L]]];
        }
    }
public:
    LL getCount(vector<string> s){
        a=s;m=a.size();n=a[0].length();ID[(int)'R']=0;ID[(int)'P']=1;ID[(int)'S']=2;
        ans=0;now.resize(m);Dfs(0,n/2-1,1);Dfs(n/2,n-1,-1);return ans;
    }
};
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up