题意
给定 \(N\) 个背包，其中第 \(i\) 个背包中有 \(a_i\) 个石子。同时还有 \(N\) 个盘子，初始时盘子中没有石子。
两人轮流执行下列操作：
- 若存在背包中还有石子，选择一个非空背包和盘子，将背包中的石子放入盘子中，注意这里对盘子没有要求；
- 若不存在背包中还有石子，选择一个非空盘子，将盘子中的石子至少取走一个，至多取完该盘子中的全部石子。
最后无法进行操作的人判负。
当两人采取最优策略时，求先手必胜还是后手必胜。
- \(1 \le T \le 10^5\)
- \(1 \le N \le 10^5\)
- \(1 \le a_i \le 10^9\)
- \(\sum N \le 10^5\)
题解
首先可以发现这个游戏可以划分为两个阶段：
- 阶段一：所有背包中的石子都被取完；
- 阶段二：所有盘子中的石子都被取完。
后者是 \(\tt{Nim}\) 和游戏，我们有结论：
设 \(x_i\) 表示第 \(i\) 个盘子上的石子数量，那么这个游戏的先手必胜当且仅当 \(\bigoplus x_i \neq 0\)，其中 \(\bigoplus x_i\) 表示 \(x_1 \oplus x_2 \oplus \cdots \oplus x_N\)。
发现第二部分的先手与 \(N\) 的奇偶性有关，因此我们可以按 \(N\) 的奇偶性分类讨论。
-
若 \(N\) 为奇数，那么后手的目标是使得 \(\bigoplus x_i \neq 0\)，发现其可以执行如下操作：
每次选取石子数量最多的背包，将其中的石子放至石子数量最多的盘子上。
可以发现在流程结束后中，一定存在一个盘子使得其之上的石子数量一定大于其余任何一个盘子，因此后手可以保证 \(\bigoplus x_i \neq 0\)，使得先手必败。
-
若 \(N\) 为奇数，那么后手的目标是使得 \(\bigoplus x_i =0\)，发现若对于每个 \(n\)，均有 \(\sum\limits_{i = 1}^{N}\left[a_i = n\right]\) 为偶数，即 \(a_i\) 按值成对出现，那么后手只需要模仿先手的操作便可以使得 \(\bigoplus x_i =0\)。反之先手可以通过执行如下操作取得胜利：
每次选取石子数量最多的背包，将其中的石子放至石子数量最多的盘子上。
可以发现在流程结束后中，一定存在一个盘子使得其之上的石子数量一定大于其余任何一个盘子，因此先手可以保证 \(\bigoplus x_i \neq 0\)，使得先手必胜。
时间复杂度为 \(\mathcal{O}(N \log N)\)，空间复杂度为 \(\mathcal{O}(N)\)，可以通过。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
bool check(ValueVector A) {
std::sort(A.begin(), A.end());
if (A.size() & 1)
return true;
for (valueType i = 1; i < A.size(); i += 2)
if (A[i] != A[i - 1])
return false;
return true;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
ValueVector A(N);
for (auto &iter : A)
std::cin >> iter;
std::cout << (check(A) ? "Second" : "First") << std::endl;
}
return 0;
}