题解：P17135 [KOI 2026 #1] 剪刀石头布
题解：P17135 [KOI 2026 #1] 剪刀石头布
这道题我们可以把剪刀、石头、布想象成一个食物链中的三个点，剪刀的“天敌”是石头，“猎物”是布，同理可得石头和剪刀的天敌和猎物。
又因为剪刀的猎物是剪刀天敌的天敌，所以我们可以得出在以下几个情况中，剪刀可以胜：
- 在一个排列中，若只有剪刀和布，则拿剪刀的人都一定可以胜，拿布的人一定输。例如：
:::align{center}
SSPPSPS :::
- 在一个排列中，若剪刀的左边有石头而右边没有，且左边有布，则拿剪刀的人可以胜利。例如：
:::align{center}
RPPSPSP :::
- 在一个排列中，若剪刀的右边有石头而左边没有，且右边有布，则拿剪刀的人可以胜利。例如：
:::align{center}
SSPRRP :::
- 在一个排列中，若剪刀的左边和右边都有石头，但是左右边都有布，则拿剪刀的人可以胜利。例如：
:::align{center}
RPPRRSSPSRRP ::: 同时，我们不必考虑剪刀、石头、布三者之间的位置关系，因为如果是
SRSP 这种情况，可以让石头战胜它右边的剪刀，再让布战胜石头，最后再让左边的剪刀战胜布就行了。
可以用一个数组a 记录当前区间左边和右边各个区间种类的数量，方便判断左右的区间以记录是否可以胜利。
因为若两张相同的卡片比赛，则谁都可以胜利，所以可以把每个连续的持有相同卡片的人记录到数组c 中，在记录每一个区间是否可以胜利，再遍历一遍所有人的卡片，看在哪一个区间里，若这个区间里人可以胜利输出1 ，不可以胜利则输出0 。
代码
#include <bits/stdc++.h>
using namespace std;
int n , cnt;
string s;
char c[200005] = {'1'};
int a[5][5];
int ans[200005];
int main()
{
cin >> n;
cin >> s;
for(int i = 0; i < n; i++)
{
if(s[i] != c[cnt])
{
cnt ++;
c[cnt] = s[i];//记录每一个持有相同卡片的区间
if(s[i] == 'S')
{
a[1][0] ++;
}
else if(s[i] == 'R')
{
a[1][1] ++;
}
else
{
a[1][2] ++;
}
//记录左右的区间种类，0为左边，1为右边
//第一个区间在最左边，所以只有右边的区间
}
}
for(int i = 1; i <= cnt; i++)
{
if(c[i] == 'S')
{
if(a[0][1] == 0 && a[1][1] == 0) ans[i] = 1;
else if(a[0][1] == 0 && a[1][2] != 0) ans[i] = 1;
else if(a[0][2] != 0 && a[1][1] == 0) ans[i] = 1;
else if(a[0][2] != 0 && a[1][2] != 0) ans[i] = 1;
a[0][0] ++;
a[1][0] --;//区间左移
}
if(c[i] == 'R')
{
if(a[0][2] == 0 && a[1][2] == 0) ans[i] = 1;
else if(a[0][2] == 0 && a[1][0] != 0) ans[i] = 1;
else if(a[0][0] != 0 && a[1][2] == 0) ans[i] = 1;
else if(a[0][0] != 0 && a[1][0] != 0) ans[i] = 1;
a[0][1] ++;
a[1][1] --;
}
if(c[i] == 'P')
{
if(a[0][0] == 0 && a[1][0] == 0) ans[i] = 1;
else if(a[0][0] == 0 && a[1][1] != 0) ans[i] = 1;
else if(a[0][1] != 0 && a[1][0] == 0) ans[i] = 1;
else if(a[0][1] != 0 && a[1][1] != 0) ans[i] = 1;
a[0][2] ++;
a[1][2] --;
}//判断每个区间是否可以胜利
}
for(int i = 0 , op = 1; i < n; i++)
{
if(s[i] != c[op]) op ++;
if(ans[op]) cout << "1";
else cout << "0";//判断是否可以胜利
}
return 0;
}完结撒花！