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

· · 题解

题目传送门：P17135 [KOI 2026 #1] 剪刀石头布

题目分析

首先我们对于每个人单独考虑，那么肯定要把他左边消到只剩一个，然后把右边也消到只剩一个（不剩也行）。

由于剪刀石头布是循环同构的，所以我们假设当前人是布，那么消到最后要求他左边和右边都不能是剪刀。

不难发现左边右边可以分别考虑，我们单独讨论一边。

第一种情况：左边根本没有剪刀。这是显然的。

第二种情况：左边有石头，把剪刀消掉了。

我们有结论：只要左边存在石头，那一定能把所有剪刀都消掉。

证明：考虑让剪刀在左边大杀四方，一路杀到最近的石头前。由于除了石头都能杀，所以一定是能杀过去的。然后再被石头吃掉，这样养蛊就行了。

左边右边分别养一个蛊，最后都被布吃掉。

代码实现

接下来就很简单了。用一个前缀、一个后缀维护有没有石头/剪刀/布，按上面的判断即可。即（还是以布为例）：左边没有剪刀或左边有石头，右边没有剪刀或右边有石头，两类取与即可。

#include<iostream>
using namespace std;
constexpr int N=200005;
int n;
string s;
bool f[N][3],g[N][3];
int main(){
    cin>>n>>s;
    for(char &i:s){
        if(i=='R')i=0;
        if(i=='S')i=1;
        if(i=='P')i=2;
    }
    for(int i=0;i<n;i++)f[i][s[i]]=g[i][s[i]]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<3;j++)f[i][j]|=f[i-1][j];
    for(int i=n-2;i>=0;i--)
        for(int j=0;j<3;j++)g[i][j]|=g[i+1][j];
    for(int i=0;i<n;i++)
        cout<<((!f[i][(s[i]+2)%3]||f[i][(s[i]+1)%3])&&(!g[i][(s[i]+2)%3]||g[i][(s[i]+1)%3]));
    return 0;
}

AC 记录。