题目链接:https://codeforces.com/contest/1382/problem/B
解题思路:
假设a1>1。如果移除第一堆就赢了,玩家1会这样做。否则,玩家1可以在第一堆中只留下一块石头,迫使玩家2移除它,让玩家1处于获胜位置。否则,如果a1=1,则强制移除第一个桩。
因此,无论哪一个玩家拿到第一堆多石的胜利。也就是说,k是最大数,使得a1=⋯=ak=1。如果k是偶数,第一个玩家将获胜。否则,第二个玩家将获胜。唯一的例外是所有的桩都只有一块石头。在这种情况下,第一个玩家在k为奇数时获胜。
复杂性是O(n)
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cin>>t; while(t--) { ll n; cin>>n; ll a[n],j=0; for( ll i=0;i<n;i++) cin>>a[i]; for(j=0;j<n-1;j++) { if(a[j]!=1) break; } j%2==0?cout<<"First\n":cout<<"Second\n"; } return 0; }