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

qianyuzhe · 2026-07-26 11:04:59 · 题解

题意简述

给定石头剪刀布序列，每次删去相邻两个元素的败者，若相同则随便删。对于每个位置判断其能否最终留下。

题目分析

考虑判断位置 x 能否留下，不妨设其为石头。若其左边没有布，显然可以删掉左边。否则我们需要删掉左边的布，而只有剪刀可以删掉布。

我们猜测，此时只要左边有剪刀就能删掉布。考虑对于左边的每个布，我们让其不断击败两侧的石头；然后对于左边的每个剪刀，我们让其不断击败两侧的布，那么左边只剩下剪刀和石头，成立。

右边同理，x 为剪刀或布同理。用前后缀和维护，时空复杂度均为线性。

代码

#include<bits/stdc++.h>
#define f(x) (x=='S'?'R':x=='R'?'P':'S')
#define g(x) (x=='S'?'P':x=='R'?'S':'R')
using namespace std;
int n,i;
string a;
bool l[200005][99],r[200005][99];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>a;
    for(i=1;i<=n;i++)for(auto j:{'S','R','P'})l[i][j]=l[i-1][j]|a[i-1]==j;
    for(i=n;i;i--)for(auto j:{'S','R','P'})r[i][j]=r[i+1][j]|a[i-1]==j;
    for(i=1;i<=n;i++)cout<<!(l[i][f(a[i-1])]&!l[i][g(a[i-1])]|r[i][f(a[i-1])]&!r[i][g(a[i-1])]);
}