2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite
M. Rock-Paper-Scissors Pyramid
思路：这题推了好久，队友用递归写的。赛后我写这个题的时候，确实难推，用到了单调栈的思想。
考虑对于一个阶的三角形推出第阶的三角形，考虑它的本质是什么？考虑当阶变成第阶的时候，新增加的一个元素需要和原三角形最后一列的所有元素进行比较。如果下面行新元素赢了，就在上面方式新元素，否则放上原本上一行的旧元素。那么我们考虑维护三角形的最后一行。
如果当前新的元素打败了旧的元素，我们就把旧的元素掉，直到不能打败或栈为空。之后再把这个新元素入栈。最后的答案就是栈底的元素啦。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int sz = s.size();
s = "?"+s;
for(int i = 1; i <= sz; i++)
{
if(s[i]=='R')a[i] = 1;
else if(s[i]=='S')a[i] = 2;
else a[i] = 3;
}
stack<int>st;
st.push(a[1]);
for(int i = 2; i <= sz; i++)
{
int nxt = a[i];
while(!st.empty())
{
int now = st.top();
if(nxt==1)
{
if(now==2||now==1)st.pop();
else break;
}
else if(nxt==2)
{
if(now==3||now==2)st.pop();
else break;
}
else if(nxt==3)
{
if(now==1||now==3)st.pop();
else break;
}
}
st.push(nxt);
}
int ans = 0;
while(!st.empty())
{
ans = st.top();
st.pop();
}
if(ans==1)cout<<"R\n";
else if(ans==2)cout<<"S\n";
else cout<<"P\n";
}
return 0;
}
|
