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

__EternalLife__ · 2026-08-09 18:35:09 · 题解

超级无敌巨大水题。

考虑当前位置 p 左边的人持有的卡片。

容易想到，当位置为 i\in [1,p-1] 的卡片都被克制时，则 p 可以把左边所有人打败。

然后在其中加入一个克制 A_p 的卡片。根据石头剪刀布的尿性，我们知道，克制 A_p 的卡片一定被 A_p 克制的卡片克制，则这个克制 A_p 的卡片一定会被打败。

所以，只要左边有一个 A_p 克制的卡片，则一定可以把克制 A_p 的卡片消掉。

但是，如果左边是克制 A_p 的和与 A_p 相同的混杂而成的（即没有 A_p 克制的卡片），则一定不能获胜。而左边全是与 A_p 相同的一定可以获胜。

综上，如果左边是克制 A_p 的和与 A_p 相同的卡片，且不全是与 A_p 相同的卡片，则 p 可以获胜。

右边同理。暴力枚举判断是 O(n^2) 的，用前缀和记录一下区间石头、剪刀、布的数量可以做到 O(n)。 :::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+10;
int preR[maxn],preS[maxn],preP[maxn];
int n;
string s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>s; s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='R') preR[i]=1;
        else if(s[i]=='P') preP[i]=1;
        else preS[i]=1;
    }
    for(int i=1;i<=n;i++) preS[i]+=preS[i-1],preR[i]+=preR[i-1],preP[i]+=preP[i-1];
    for(int i=1;i<=n;i++){
        if(s[i]=='R'){
            if(i>1){
                if(preP[i-1]+preR[i-1]==i-1&&preR[i-1]!=i-1){
                    cout<<'0'; continue;
                }
            }
            if(i<n){
                if(preP[n]-preP[i]+preR[n]-preR[i]==n-i&&preR[n]-preR[i]!=n-i){
                    cout<<'0'; continue;
                }
            }
            cout<<'1';
        }
        else if(s[i]=='P'){
            if(i>1){
                if(preS[i-1]+preP[i-1]==i-1&&preP[i-1]!=i-1){
                    cout<<'0'; continue;
                }
            }
            if(i<n){
                if(preS[n]-preS[i]+preP[n]-preP[i]==n-i&&preP[n]-preP[i]!=n-i){
                    cout<<'0'; continue;
                }
            }
            cout<<'1';
        }
        else{
            if(i>1){
                if(preR[i-1]+preS[i-1]==i-1&&preS[i-1]!=i-1){
                    cout<<'0'; continue;
                }
            }
            if(i<n){
                if(preR[n]-preR[i]+preS[n]-preS[i]==n-i&&preS[n]-preS[i]!=n-i){
                    cout<<'0'; continue;
                }
            }
            cout<<'1';
        }
    }
    return 0;
}

:::