模拟赛9.4

点击跳转

#include <iostream>
#include <string>
using namespace std;

int dfs1(int R,int P,int S)//石头，布，剪刀
{
    if( R < 0 || P < 0 || S < 0 ) return -1;//有一类人数为负数即无解
    if( R==0 && P==0 && S==0 ) return -1;//没有人参加比赛也无解
    if( R==1 && P==0 && S==0 ) return 0;//石头赢
    if( R==0 && P==1 && S==0 ) return 1;//布赢
    if( R==0 && P==0 && S==1 ) return 2;//剪刀赢
    return dfs1( (R-P+S)>>1,(R+P-S)>>1,(-R+P+S)>>1 );//递归(>>1:位运算,即除以2)
}

string dfs2(int t,int p) 
{
    if( p==1 )//当参赛只有2人时
    {
        if( t==0 ) return "RS";//石头赢
        else if( t==1 ) return "PR";//布赢
        else return "PS";//剪刀赢
    }
    
    if( t==0 )//当石头赢时（参赛者2人以上）
    {
        //既然这把是石头赢了，那这一局肯定是石头和剪刀的对决
        //那么上一局对决的两组肯定是：石头和剪刀，剪刀和布，才可能得到这一局的石头和剪刀
        string s1 = dfs2(2,p>>1);//递归，上一把是剪刀和布的对决，剪刀胜利
        string s2 = dfs2(0,p>>1);//递归，上一把是石头和剪刀的对决，石头胜利
        if( s1.compare(s2)>0 ) return s2+s1;//要求输出字典序最小的
        else return s1+s2;
    }
    else if( t==1 )//当布赢时（参赛者2人以上）
    {
        //既然这把是布赢了，那这一局肯定是布和石头的对决
        //那么上一局对决的两组肯定是：布和石头，石头和剪刀，才可能得到这一局的布和石头
        string s1 = dfs2(1,p>>1);//递归，上一把是布和石头的对决，布胜利
        string s2 = dfs2(0,p>>1);//递归，上一把是石头和剪刀的对决，石头胜利
        if( s1.compare(s2)>0 ) return s2+s1;//要求输出字典序最小的
        else return s1+s2;
    }
    else//当剪刀赢时（参赛者2人以上）
    {
        //既然这把是剪刀赢了，那这一局肯定是剪刀和布的对决
        //那么上一局对决的两组肯定是：剪刀和布，布和石头，才可能得到这一局的剪刀和布
        string s1 = dfs2(1,p>>1);//递归，上一把是布和石头的对决，布胜利
        string s2 = dfs2(2,p>>1);//递归，上一把是剪刀和布的对决，剪刀胜利
        if( s1.compare(s2)>0 ) return s2+s1;//要求输出字典序最小的
        else return s1+s2;
    }
}

int main()
{
    int R,P,S;//石头，布，剪刀
    cin >> R >> P >> S;
    int t = dfs1(R,P,S);
    if( t==-1 )
    {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }
    string s = dfs2( t,(R+P+S)>>1 );//反向思考，根据结果还原每一轮。人数都是每一轮除以2
    cout << s << endl;
}

t2
点击跳转
t3
点击跳转