Codeforces #658 B: Sequential Nim

题目链接

题目大意

有$n$堆石头,每堆石头都有一定数量。两人轮流从最前面一堆取至少一块(只能在当前堆),取走最后一块的人赢,问均为最优策略时的胜出者。

解法

(我们定义走当前这步操作的人为先手,剩下一人为后手

我们先从最简单的一堆来说,先手赢。在最开始那一堆前面加一堆时,就出现了两种情况:

  • 新加的$a>1$,则先手胜(拿到只剩一颗让对手拿),然后就回到了一堆的必胜状态
  • 新加的$a=1$,则先手败(没有选择只能拿一颗),然后对手到了一堆的必胜状态

所以我们现在在原有的情况左边加上任意堆我们都能够推算出其胜负:对于一个已知胜负的局面前面加上一堆,若加的这堆大于一,则拿这堆的必胜,若加上这堆为一,状态反转(因为显示只能取1,可理解为交换下一堆的先后手)。

换句话说,对于任意不为1且我先手的堆,即代表我有主动权,假如下堆的先手会赢,我就取到只剩一个,否则我就取完。

所以我们只需找第一堆不为1的石子的位置即可,但如果全是1得特判。

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,a,cnt=0;
		bool flag=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a);
			if(!flag)
				if(a==1)
					++cnt;
				else
					flag=1;
		}
		if(cnt==n)
			printf(!(cnt%2) ? "Second\n" : "First\n");
		else printf(cnt%2 ? "Second\n" : "First\n");
	}
}
暂无评论

发送评论 编辑评论


上一篇