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

Finner_forgeter · 2025-09-28 20:55:34 · 题解

P14059题解

首先，我是一个知更鸟厨。

题意描述： 给出一个圈，包含若干个 01 串，每次从中删去一个或多个元素，问两个聪明绝顶的人谁会赢。

思路： 博弈论问题，如果思路搞懂的话代码是很好写的。首先，如果只有一个串的话，那么直接判断谁输谁赢，如果有两个串的话知更鸟小姐一定会赢（直接选取为 1 的串），其他情况另作考虑：在有多个串时，统计双方的棋子的个数，不难得出，当知更鸟的棋子数大于星期日的棋子数时，知更鸟是赢家，反之亦可证明星期日会赢。当双方棋子数相等时，星期日会赢，证明如下： 先手拿几颗，后手就跟着拿几颗，最后剩下的一定是后手的棋子。

既然明白了思路，那么代码就可以写了。

AC代码：

#include<bits/stdc++.h>
#define finner_forgeter return
#define love 0
#define Robin ;
using namespace std;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int sister=0,brother=0,s=0;
        char a[100005];
        memset(a,'#',sizeof(a));
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]=='1')
            sister++;
            else brother++;
            if(a[i]==a[i-1])
            continue;
            s++;
        }if(a[1]==a[n]&&s>1)s--;
        if(s==1){
            if(sister)cout<<"Sunday";
            else cout<<"Robin";
        }else if(s==2){
            cout<<"Robin";
        }else{
            if(sister>brother)cout<<"Robin";
            else if(sister<brother)cout<<"Sunday";
            else {
                cout<<"Sunday";
            }
        }cout<<endl;
    }finner_forgeter love Robin
}

另外给出两个易错点：一是这是一个环，二是要注意：这是棋子数！