题解：P14059 【MX-X21-T4】[IAMOI R5] 使一颗心免于哀伤

liminghao666 · 2025-09-29 09:58:28 · 题解

题目

题目大意

有一个 01 环（黑白棋子环），知更鸟和星期日轮流取棋子，知更鸟可以取连续的 1 ，星期日可以取连续的 0 ，谁先取完谁获胜，问谁最终会获胜。

思路

首先很容易证明，只要都有 0 和 1 ，它们各自的连续段数是相同的。

然后进行分类讨论：

1. 全为 0 或 1 ，及 n 个棋子都一样，简单判断即可。

思路有了，代码就简单了。

#include<bits/stdc++.h>
using namespace std;
int t,n,a[100005];
char s;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int num0=0,num1=0;//计算0和1个数
        for(int i=1;i<=n;i++)
        {
            cin>>s;
            a[i]=s-'0';
            if(a[i]) num1++;
            else num0++;
        }
        int p=0;//计算0和1各自的块数（总块数/2）。
        for(int i=2;i<=n;i++)
        {
            if(a[i]&&a[i-1]==0) p++;
        }
        if(a[n]==0&&a[1]==1) p++;
        if(!num0) cout<<"Sunday\n";//全为1
        else if(!num1) cout<<"Robin\n";//全为0
        else if(p==1) cout<<"Robin\n";//0和1各只有1个块
        else if(num1>num0) cout<<"Robin\n";//1的个数多，知更鸟获胜。
        else cout<<"Sunday\n";//0的个数小于等于1，星期日获胜。
    }
    return 0;
}