2022 CCPC 绵阳 M

2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite

M. Rock-Paper-Scissors Pyramid

思路：这题推了好久，队友用递归写的。赛后我写这个题的时候，确实难推，用到了单调栈的思想。

考虑对于一个\(P_{n-1}\)阶的三角形推出第\(P_{n}\)阶的三角形，考虑它的本质是什么？考虑当\(n-1\)阶变成第\(n\)阶的时候，新增加的一个元素需要和原三角形最后一列的所有元素进行比较。如果下面行新元素赢了，就在上面方式新元素，否则放上原本上一行的旧元素。那么我们考虑维护三角形的最后一行。

如果当前新的元素打败了旧的元素，我们就把旧的元素\(pop\)掉，直到不能打败或栈为空。之后再把这个新元素入栈。最后的答案就是栈底的元素啦。

// AC one more times
// nndbk
#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;
        //1石头 2剪刀 3布
        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;
}