题解：P17135 [KOI 2026 #1] 剪刀石头布

guoyuqi102 · 2026-08-09 15:55:24 · 题解

题目分析

原题传送

以左边为例，分三种情况讨论：

左侧所有卡片都与当前卡片相同：此时，可以指定当前的人在与左侧相邻的人对决时一直获胜，从而消灭左侧所有人。

左侧存在一张被当前卡片克制的卡片：例如，当前卡片为石头，左侧存在剪刀。当前的人可以先不参与对决，等待左侧的剪刀将其他卡片全部消灭后（除石头外），再与其对决并获胜。

当前的人位于左边界，即左侧没有人，条件自然满足。

若以上三种情况都不满足，当前的人最终一定会失败。

右边思路一样，就不过多解释。

操作实现

不难想到，维护前缀和数组，然后做上面的操作即可。

代码展示

/*
R:1
S:2
P:3
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n;
int a[N][5];
string s;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s;
    if(s[0]=='R') a[0][1]=1;
    if(s[0]=='S') a[0][2]=1;
    if(s[0]=='P') a[0][3]=1;
    for(int i=1;i<n;i++){
        if(s[i]=='R'){
            a[i][1]=a[i-1][1]+1;
            a[i][2]=a[i-1][2];
            a[i][3]=a[i-1][3];
        }
        if(s[i]=='S'){
            a[i][2]=a[i-1][2]+1;
            a[i][1]=a[i-1][1];
            a[i][3]=a[i-1][3];
        }
        if(s[i]=='P'){
            a[i][3]=a[i-1][3]+1;
            a[i][1]=a[i-1][1];
            a[i][2]=a[i-1][2];
        }
    }
    for(int i=0;i<n;i++){
        if(s[i]=='R'){
            if((i==0||a[i][1]==i+1||a[i][2])&&(i==n-1||a[n-1][1]-a[i][1]==n-i-1||(a[n-1][2]-a[i][2]))){
                cout<<1;
            }
            else cout<<0;
        }
        if(s[i]=='S'){
            if((i==0||a[i][2]==i+1||a[i][3])&&(i==n-1||a[n-1][2]-a[i][2]==n-i-1||(a[n-1][3]-a[i][3]))){
                cout<<1;
            }
            else cout<<0;
        }
        if(s[i]=='P'){
            if((i==0||a[i][3]==i+1||a[i][1])&&(i==n-1||a[n-1][3]-a[i][3]==n-i-1||(a[n-1][1]-a[i][1]))){
                cout<<1;
            }
            else cout<<0;
        }
    }
    return 0;
}