题目链接（正睿）
题目大意
有\(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的加法递推即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #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;
}
|