newcoder F石头剪刀布（DFS + 思维）题解

newcoder F石头剪刀布（DFS + 思维）题解

题意：
wzms 今年举办了一场剪刀石头布大赛，bleaves 被选为负责人。

比赛共有 2n 个人参加， 分为 n 轮，
在每轮中，第 1 位选手和第 2 位选手对战，胜者作为新的第 1 位选手，
第 3 位和第 4 位对战，胜者作为新的第 2 位选手，以此类推。

bleaves 调查得知，每个人都有其偏爱决策，每个人在每一次对战中都会使用他的偏爱决策。

如果一次对战的双方的偏爱决策相同，那么这次对战就永远不会结束，所以 bleaves 不希望这种情况发生。

现在 bleaves 知道了每个人的偏爱决策，但她不知道如何安排初始的次序，使得上面的情况不会发生，你能帮帮她吗？

全部的输入数据满足：R+P+S=2n ，1≤n≤20

链接：https://ac.nowcoder.com/acm/contest/332/F

来源：牛客网

思路：正向思考好像有点难度，那么就反向思考。

只要确定了最终胜出的人，那么前面的都能推出来了，那么就从最后往前递归，然后从末尾往前按字典序排序递归回来。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn = ( << ) + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

int R, P, S, cnt;

int r, p, s;

char ans[maxn];

void dfs(char x, int L, int R){

    if(L == R){

        ans[L] = x;

        if(x == 'R') r++;

        else if(x == 'P') p++;

        else if(x == 'S') s++;

        return;

    }

    int m = (L + R) >> ;

    if(x == 'R'){

        dfs('R', L, m);

        dfs('S', m + , R);

    }

    else if(x == 'P'){

        dfs('P', L, m);

        dfs('R', m + , R);

    }

    else if(x == 'S'){

        dfs('S', L, m);

        dfs('P', m + , R);

    }

    bool swapp = false;

    for(int i = L; i <= m; i++){

        if(ans[i] < ans[m + i - L + ]) break;

        if(ans[i] > ans[m + i - L + ]){

            swapp = true;

            break;

        }

    }

    if(swapp){

        for(int i = L; i <= m; i++){

            swap(ans[i], ans[m + i - L + ]);

        }

    }

}

int main(){

    scanf("%d%d%d", &R, &P, &S);  //r p s

    cnt = R + P + S;

    bool flag = false;

    for(int i = ; i < ; i++){

        r = p = s = ;

        if(i == ){

            dfs('R', , cnt);

        }

        else if(i == ){

            dfs('P', , cnt);

        }

        else if(i == ){

            dfs('S', , cnt);

        }

        if(R == r && P == p && S == s){

            flag = true;

            break;

        }

    }

    ans[cnt + ] = '\0';

    if(flag) printf("%s\n", ans + );

    else printf("IMPOSSIBLE\n");

    return ;

}