Sequential Nim

题目大意

有$n$堆石子，每堆$a_i$个
两人按顺序从第$1 \sim n$堆取出$1 \sim a_i$个石子
最先取完的人获胜，若每个人都采取最优方案，求赢家

Time: 1000 ms
Memory: 262144 kB

解题思路及分析

博弈论

结论：

1. 当a序列都为1时，若n为奇数，先手必赢，否则后手必赢
2. 当a序列不都为1时，偶数个前缀1后手必赢，奇数个前缀1先手必赢
   
   

$1$是最特殊的元素，如果当前堆只有$1$个石子，那么玩家别无选择，下一个玩家从新的一堆开始，如果下一堆石子个数在$1$个以上，那么玩家可以选择拿走$a_i - 1$个，剩余1个继续让刚刚的玩家处于劣势

1. 如果没有$1$，那么先手是必赢的，因为只要重复上述过程，直到最后一堆自己取完就可以赢了
2. 如果只有前缀$1$，且为偶数堆，经过偶数轮操作，当$1$被取完后，此时玩家1仍处于先手，剩余部分没有$1$，回到了第一种状态，先手赢；如果前缀$1$为偶数堆，取完前缀1后玩家2处于先手，即后手赢；
3. 考虑后缀$1$. 实际上后缀1的奇偶并不影响结果，看一组例子

• $[3, 1, 1] \overset{2}{\rightarrow} [1, 1, 1]$
  接只有1的奇数情况，先手赢
  
• $[3, 1, 1, 1] \overset{3}{\rightarrow} [1, 1, 1]$
  同上

由此可知，后缀$1$不会影响结果故可以忽略后缀的$1$

4. 考虑中间的$1$. 实际上中间的$1$同样不会影响结果，由第3种情况可以知道，第一个拿到非$1$石子的人可以控制自己后面拿到哪一堆，同样，他可以控制自己是否拿到中间最后一堆是$1$的石子，也就可以决定自己的输赢
如果不能理解自己可以举几组石子试试，注意拿石子之后尽量归到上面几种子问题的情况

综上述推理，不难得到上面的结论

AC代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    int n, a[100005];
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 1)
            {
                cnt++;
            }
            else 
            {
                break;
            }
        }
        if (cnt == n)   cnt++;  
        // 由于是否都为1的情况和前缀1的情况相反,故这里给cnt++,统一输出格式
        printf(cnt & 1 ? "Second\n" : "First\n");
    }
    return 0;
}