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

题目大意

有一个

01

环（黑白棋子环），知更鸟和星期日轮流取棋子，知更鸟可以取连续的

1

，星期日可以取连续的

0

，谁先取完谁获胜，问谁最终会获胜。

思路

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

然后进行分类讨论：

全为 $0$ 或 $1$ ，及 $n$ 个棋子都一样，简单判断即可。
$0$ 和 $1$ 各有一个块，那么先手必胜，即知更鸟获胜。
$0$ 和 $1$ 各自块数 $>1$ ，那么每当有一方取走了一整个块，另一方的块数也会减 $1$ ，这样做显然不是最优的（因为你的步骤帮助你的对手和你做了相同的事），而且当仅剩 $0$ 或 $1$ 各一个块时，此时取的一方必胜。所以最优策略是每次尽量不减少块数，可以想到每次只取 $1$ 个，拖时间到对手开始减少块数，等各只剩一个块时坐收渔翁之利。所以比较 $1$ 和 $0$ 的个数，当 $1$ 更多时知更鸟获胜， $0$ 更多时星期日获胜，相等时也是星期日获胜（因为知更鸟先取）。

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

CPP

#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;
}

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

文章操作

题目大意

思路

相关推荐

评论

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