题目翻译
有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。两人轮流取石子，每次只能取编号最小且有石子的堆。每次可在一堆石子中取走若干个（至少取 $1$ 个），当一个人没有石子可取时，他就输了。
现在给出每堆石子的数量，假设两人都采取最优策略，问最后是先手 (First) 胜利还是后手 (Second) 胜利。
最优解
考虑几种特殊情形
- 只有一堆，先手直接取完获胜
- 只有两堆，并且第一堆石子数 $a_1 > 1$，先手可取 $a_1 - 1$ 个，后手只能取剩下一个，先手再把第二堆直接取完获胜。这种策略可应用于 $a_1,a_2,...,a_{n-1} > 1$
- 只有两堆，并且 $a_1 = 1$，先手只能取完第一堆，后手直接取完第二堆获胜。推广到 $a_1, a_2, ..., a_{n-1} = 1$，此时先手没有主动权，输赢由石子数为 $1$ 的前缀堆数决定，偶数个先手赢，奇数个后手赢
- 如果所有堆都只有一颗石子，输赢由石子堆数决定，偶数堆后手赢，奇数堆先手赢
考虑一般情形
$$ \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$
- 由特殊情形 $2, 3$ 的分析可知，如果中间没有 $1$，$k_0$ 决定输赢
- 如果中间有 $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$
考虑对状态转移做优化
$SG(i, 0) = SG(i+1, a_{i+1})$，因为它们都对应第 $i$ 堆已取完，第 $i+1$ 堆还未取，记 $x = SG(i, 0)$
- 若 $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$
- 若 $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;
}如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。