题解：P13198 [GCJ 2016 #2] Rather Perplexing Showdown

· · 题解

题意简述

告诉你比赛轮数与分别出石头、剪刀和布的人数，问是否存在一个手势序列，使得最终决出冠军且匹配输入。

题目分析

我们来考虑逆向思维，如果我们没有诞生冠军，那么我们生成的序列也一定与输入不匹配。

相比模拟最后一轮的手势来推导冠军，复杂度太过恐怖，怎么办？

还是逆向思维，直接枚举出冠军的手势，然后我们可以得出上一轮的两人手势，这就说明整个序列是可以推导出来的！然后对每个推导出的手势继续推导等，也就是结尾往开头的推导，所以，当推到最开始一轮时，这一轮的序列就可能是正解。

最后我们只要把序列和输入比较就行啦，如果存在至少一个符合的序列，则输出最小字典序且符合的答案，否则就按题目要求输出。

完整代码

#include<bits/stdc++.h>
using namespace std;
int t,n,r,p,s;
string a[10];

//递归生成序列
string dfs(string x,int s){
    if(s==n)
        return x;
    string R=dfs("R",s+1),P=dfs("P",s+1),S=dfs("S",s+1);
    if(x=="R")
        return min(R,S)+max(R,S);
    if(x=="P")
        return min(P,R)+max(P,R);
    if(x=="S")
        return min(S,P)+max(S,P);
    //题目要求最小字典序 因此需要把字典序小的放在前面
}

//验证序列是否匹配输入 
bool check(string x){
    int rr=0,pp=0,ss=0;
    //注意区分！这里的三个变量表示字符串中对应字符的个数 
    for(int i=0;i<x.size();i++)
        if(x[i]=='R')
            rr++;
        else if(x[i]=='P')
            pp++;
        else
            ss++;
    if(rr==r&&pp==p&&ss==s)
        return 1;
    return 0;
}

int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>n>>r>>p>>s;
        a[1]=dfs("R",0),a[2]=dfs("P",0),a[3]=dfs("S",0);
        sort(a+1,a+4);
        //为保证最小字典序 应当先进行字典序排序 
        cout<<"Case #"<<i<<": ";
        for(int j=1;j<=4;j++)
            if(j<4&&check(a[j])){
                cout<<a[j];
                break;
            }else if(j==4)
                cout<<"IMPOSSIBLE";
        cout<<endl;
    }
    return 0;
}

时间复杂度 O(3^n)，可以放心的通过。

补充：本文使用人工智能仅进行了代码排版，核心思路、文章内容及原代码均由本人完成。