B. Sequential Nim
题目链接-B. Sequential Nim
题目大意
给 n n n 堆石子的数量，两人轮流从最左端的非空堆中取任意数量 ( > 0 ) (>0) (>0)的石子，无法再取者输，假设两人都会采取最佳策略，判断谁会赢
解题思路
- 因为每堆石子只有 a i = 1 a_i=1 ai=1和 a i > 1 a_i>1 ai>1这两种情况，当 a i = 1 a_i=1 ai=1时是没有决策权的，该该堆只能一次取完，而当 a i > 1 a_i>1 ai>1时，可以选择一次拿完，让对手拿下一堆或者拿走 a i − 1 a_i-1 ai−1个，让对手只能拿该堆剩下的一个
- 所以我们可以得出，第一次拿到数量大于 1 1 1 的石子堆的人是该场赢家，因为他可以通过取 a i − 1 a_i-1 ai−1个或全部取完来迫使对方进入自己的节奏，具有该场的总决策权
- 我们需要特判一下每堆石子都只有 1 1 1个的情况，这种情况需要判断 n n n的奇偶性来确定是谁先无法再取
- 具体操作见代码
附上代码
#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