专栏文章

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

FFinner_forgeter
P14059题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minriivi
此快照首次捕获于
2025/12/02 07:10
3 个月前
此快照最后确认于
2025/12/02 07:10
3 个月前
查看原文

P14059题解

首先，我是一个知更鸟厨。
题意描述： 给出一个圈，包含若干个 0101 串，每次从中删去一个或多个元素，问两个聪明绝顶的人谁会赢。
思路： 博弈论问题，如果思路搞懂的话代码是很好写的。首先，如果只有一个串的话，那么直接判断谁输谁赢，如果有两个串的话知更鸟小姐一定会赢（直接选取为 11 的串），其他情况另作考虑：在有多个串时，统计双方的棋子的个数，不难得出，当知更鸟的棋子数大于星期日的棋子数时，知更鸟是赢家，反之亦可证明星期日会赢。当双方棋子数相等时，星期日会赢，证明如下： 先手拿几颗，后手就跟着拿几颗，最后剩下的一定是后手的棋子。
既然明白了思路，那么代码就可以写了。
AC代码：
CPP
#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
}
另外给出两个易错点：一是这是一个环，二是要注意：这是棋子数！

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...