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

Problem - 1382B - Codeforces

题意：

有 n 堆石头，其中第 i 堆有 a 块石头。 两个人玩游戏，轮流移走石头。 在一次移动中，玩家可以从第一个非空堆（具有最小索引的堆，至少有一块石头）中取出正数的石头。 第一个不能移动的玩家（因为所有的牌都是空的）输掉比赛。 如果两个玩家都发挥最佳，则确定游戏的获胜者。

思路：

对于公平组合游戏，一般以必败态作为突破口

所谓必败态，就是处于这个状态的先手必败，先手只有一种必败的决策，即必败状态只有一条出边

对于这道题，必败态就是只剩下一个石子，这样必败态的先手只有一种决策：取一个石子

对于每一堆石子堆，其中n个石子，先手都可以拿走n-1个石子，然后让状态变成必败态

然而有一种情况需要特判，就是当一堆石子一开始只有一个石子时，相当于两个玩家的状态互换了

因此需要统计有几堆石子只有一个石子，如果堆数是奇数，则是先手赢，否则是后手赢

还需要特判全是1的情况：如果堆数是奇数，则是后手赢，否则是先手赢

Code：

#include 
using namespace std;
const int mxn=1e5+10;
int n,cnt=0;
int a[mxn];
void solve(){
    cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(a[i]==1) cnt++;
        else break;
    }
    if(cnt==n){
        if(cnt%2==1) puts("First");
        else puts("Second");
    }
    else if(cnt%2==1) puts("Second");
    else puts("First");
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

总结：

对于公平组合游戏，一般以必败态作为突破口

所谓必败态，就是处于这个状态的先手必败，先手只有一种必败的决策，即必败状态只有一条出边