欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

Codeforces Round #658 (Div. 2) B. Sequential Nim

程序员文章站 2022-03-04 21:27:10
B. Sequential Nim题目链接-B. Sequential Nim题目大意给 nnn 堆石子的数量,两人轮流从最左端的非空堆中取任意数量(>0)(>0)(>0)的石子,无法再取者输,假设两人都会采取最佳策略,判断谁会赢解题思路因为每堆石子只有ai=1a_i=1ai​=1和ai>1a_i>1ai​>1这两种情况,当ai=1a_i=1ai​=1时是没有决策权的,该该堆只能一次取完,而当ai>1a_i>1ai​>1时,可以选择一次...

B. Sequential Nim

题目链接-B. Sequential Nim
Codeforces Round #658 (Div. 2) B. Sequential Nim
Codeforces Round #658 (Div. 2) B. Sequential Nim
Codeforces Round #658 (Div. 2) B. Sequential Nim
题目大意
nn 堆石子的数量,两人轮流从最左端的非空堆中取任意数量(>0)(>0)的石子,无法再取者输,假设两人都会采取最佳策略,判断谁会赢

解题思路

  • 因为每堆石子只有ai=1a_i=1ai>1a_i>1这两种情况,当ai=1a_i=1时是没有决策权的,该该堆只能一次取完,而当ai>1a_i>1时,可以选择一次拿完,让对手拿下一堆或者拿走ai1a_i-1个,让对手只能拿该堆剩下的一个
  • 所以我们可以得出,第一次拿到数量大于 11 的石子堆的人是该场赢家,因为他可以通过取ai1a_i-1个或全部取完来迫使对方进入自己的节奏,具有该场的总决策权
  • 我们需要特判一下每堆石子都只有11个的情况,这种情况需要判断nn的奇偶性来确定是谁先无法再取
  • 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=1e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		bool ass=0;
		int n,cnt=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==1&&!ass) cnt++;
			else ass=1;
		}
		if(!ass)
			cout<<(n&1?"First":"Second")<<endl;
		else
			cout<<(cnt&1?"Second":"First")<<endl; 
	}
	return 0;
}

本文地址:https://blog.csdn.net/Fiveneves/article/details/107523254