【题解】ZROI 2021提高组十连测day2 比赛

题目链接（正睿）

题目大意

有$2^n$个人玩剪掉石头布，每次第$1$个人和第$2$个，第$3$个和第$4$个……会决出谁是胜者，然后晋级下一轮变成第$1,2,3...$个人。经过$n$轮后最后会决出一个胜者。

这$2^n$个人每次出拳都固定，其中有$r$个石头，$p$个布，$s$个剪刀。给出一组出拳方案，用R来表示石头，P来表示布，S来表示剪刀。使得任意一轮比赛都不存在出拳相同的人，且字典序最小。

$n\le 15$

分析

考虑最底下需要多少个rp，多少个rs，多少个ps。

$$rp=\frac{p+r-s}{2}\\ rs=\frac{r+s-p}{2}\\ ps=\frac{p+s-r}{2}$$

之后，我们将每一轮的结果算出，就变成了$n-1$的子问题，用循环求解即可，复杂度$O(n)$。

实现

利用string的加法递推即可

#include<bits/stdc++.h>

using namespace std;
int r, p, s, t, n;
string st[7];

int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int main() {
    t = read();
    while (t--) {
        r = read(), p = read(), s = read();
        n = r + p + s;
        if (abs(r - p) > 1 || abs(r - s) > 1 || abs(p - s) > 1) {
            printf("-1\n");
            continue;
        }
        st[1] = 'S', st[2] = 'R', st[3] = 'P';
        for (int i = 2; i <= n; i *= 2) {
            if (st[1] < st[2]) st[4] = st[1] + st[2];
            else st[4] = st[2] + st[1];
            if (st[1] < st[3]) st[5] = st[1] + st[3];
            else st[5] = st[3] + st[1];
            if (st[2] < st[3]) st[6] = st[2] + st[3];
            else st[6] = st[3] + st[2];
            st[3] = st[6], st[2] = st[5], st[1] = st[4];
        }
        if (r == p && s > p) cout << st[1] << endl;
        else if (r == s && r > p) cout << st[1] << endl;
        else if (p == s) cout << st[2] << endl;
        else cout << st[3] << endl;
    }
    return 0;
}