题目翻译

原题链接

有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。两人轮流取石子，每次只能取编号最小且有石子的堆。每次可在一堆石子中取走若干个（至少取 $1$ 个），当一个人没有石子可取时，他就输了。

现在给出每堆石子的数量，假设两人都采取最优策略，问最后是先手 (First) 胜利还是后手 (Second) 胜利。

最优解

考虑几种特殊情形

1. 只有一堆，先手直接取完获胜
2. 只有两堆，并且第一堆石子数 $a_1 > 1$，先手可取 $a_1 - 1$ 个，后手只能取剩下一个，先手再把第二堆直接取完获胜。这种策略可应用于 $a_1,a_2,...,a_{n-1} > 1$
3. 只有两堆，并且 $a_1 = 1$，先手只能取完第一堆，后手直接取完第二堆获胜。推广到 $a_1, a_2, ..., a_{n-1} = 1$，此时先手没有主动权，输赢由石子数为 $1$ 的前缀堆数决定，偶数个先手赢，奇数个后手赢
4. 如果所有堆都只有一颗石子，输赢由石子堆数决定，偶数堆后手赢，奇数堆先手赢

考虑一般情形

$$ \underbrace{1, 1, ..., 1}_{k_0},\ \overbrace{a_{k_0+1},a_{k_0+2},...,a_{k_0+x_0}}^{x_0},\ \underbrace{ \underbrace{1, 1, ..., 1}_{k_1},\ \overbrace{a_{k_0+x_0+k_1+1},a_{k_0+x_0+k_1+2},...,a_{k_0+x_0+k_1+x_1}}^{x_1},\ ..., }_{repeat} a_n $$

其中未标 $1$ 的石子堆数大于 $1$

1. 由特殊情形 $2, 3$ 的分析可知，如果中间没有 $1$，$k_0$ 决定输赢
2. 如果中间有 $1$，不妨假设先手首先取 $a_{k_0+1}$，考虑他是否有策略保证自己先取 $a_{k_0+x_0+k_1+1}$。答案是肯定的，他只要根据 $k_1$ 的奇偶性决定是否取完 $a_{k_0+x_0}$

由此可见，$k_0$ 决定主动权归属，并且获得方可将主动权一直保持下去，直到自己一次性取完 $a_n$。所以可直接求前缀 $1$ 的个数

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 5;
int t, n, a[N];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; i++) cin >> a[i];

        int k = 0;
        while(k < n && a[k] == 1) k++;
        cout << ((k == n) ^ (k & 1) ? "Second" : "First") << "\n";
    }

    return 0;
}

SG 函数做法

定义 $SG(i, j)$ 为前 $i - 1$ 堆已取完，第 $i$ 堆还剩 $j$ 颗的状态。该状态的后继状态为前 $i - 1$ 堆已取完，第 $i$ 堆还剩 $k$ 颗，$k \in [0, j)$，则

$$ SG(i,j) = mex\{SG(i, 0), SG(i, 1), ..., SG(i, j-1)\} $$

由于是从后往前递推，初始状态为 $SG(n, j) = j$

考虑对状态转移做优化

1. $SG(i, 0) = SG(i+1, a_{i+1})$，因为它们都对应第 $i$ 堆已取完，第 $i+1$ 堆还未取，记 $x = SG(i, 0)$

   1. 若 $x >= a_i$，已知 $SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i-1$ 项，根据 $mex$ 规则，$0,1,...,a_i-2$ 依次是它们的值，所以 $SG(i, a_i) = a_i - 1$
   2. 若 $x < a_i$，$SG(i, 0), SG(i, 1), SG(i, 2),...,SG(i, a_i-1)$ 共 $a_i$ 项，会不重不漏取完 $0,1,...,a_i-1$，所以 $SG(i, a_i) = a_i$

我们只需求 $SG(i, a_i)$，所以可以去掉第二维。由于是顺序取石子，能操作的有向图只有一张，所以必胜态是 $SG(1, a_1) \neq 0$

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

const int N = 1e5 + 5;
int t, n, a[N], sg[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        sg[n] = a[n];
        for(int i = n - 1; i; i--)
            sg[i] = sg[i + 1] >= a[i] ? a[i] - 1 : a[i];
        
        cout << (sg[1] ? "First" : "Second") << "\n";
    }

    return 0;
}