题目大意
有若干堆石子，每一次需要从一堆石子中拿走一些，然后如果愿意的话，再从这堆石子中拿一些分给其它任意堆。不能操作的人就输了。
同时，石子只能移到非空堆，一旦某堆变为 0，它就无法继续操作了。
题目分析
一、游戏规则
每次操作分两步：
移除：从某堆中拿走至少 1 个石子
分配（可选）：将该堆剩余的石子任意分配到其他仍有石子的堆中
关键约束：石子只能移到非空堆，一旦某堆变为 0，它就没法操作了
二、从小规模开始分析
n = 1（单堆）
无法分配（没有别的非空堆），退化为了普通取石子游戏。操作者可取走 1~全部。
SG 值就是石子数：SG(x) = x。当 x > 0 时 SG ≠ 0，先手必胜。
n = 2（两堆）
从这个分析里面我们可以推导出解题的关键：
如果两堆相等 (a, a)：后手采用对称策略——无论先手对哪堆做什么（移除 r 个、移 m 个到另一堆），后手在另一堆执行完全相同操作。只要两堆相等，后手总能维持相等，直到把先手逼入 (1,1)，最终先手必败。因此 SG(a, a) = 0，是必败态。
如果两堆不等 (a, b)，a < b：先手只需从较大堆移除 (b−a) 个，不分配，状态变为 (a, a)——把 必败态 丢给后手。因此 SG(a, b) ≠ 0，是 必胜态。
三、SG 函数表格（n = 2）
我们来手动推导小值的 SG 值，设 a ≤ b（?是懒得算了）：
a \ b | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | – | 0 | 3 | 4 | 5 | 6 |
2 | – | – | 0 | 1 | ? | ? |
3 | – | – | – | 0 | ? | ? |
4 | – | – | – | – | 0 | ? |
5 | – | – | – | – | – | 0 |
示例：SG(1,2) 的可达 SG 集合 = {SG(0,2)=2, SG(1,1)=0, SG(2,0)=2, SG(1,0)=1} = {0,1,2} → mex = 3
SG(2,3) 的可达 SG 集合 = {SG(1,3)=4, SG(0,4)=4, SG(0,3)=3, SG(2,2)=0, SG(3,1)=4, SG(4,0)=4, SG(2,1)=3, SG(3,0)=3, SG(2,0)=2} = {0,2,3,4} → mex = 1
由此我们可以发现一个规律：对角线全为 0（比败态），其余非零（必胜态）。
四、推广到任意 n
定理（必败态的条件）：
先手必败 ⇔ n 为偶数，且将所有石子堆排序后，可以两两配对相等
（即 a₁ = a₂, a₃ = a₄, …, aₙ₋₁ = aₙ）
证明概要：
局面类型 | 策略 |
|---|---|
奇数堆 | 先手选最多的堆，将其搬空并分配石子，使剩余偶数堆两两配对，丢给后手一个必败态 |
偶数堆但不全配对 | 先手选最多的堆，将其削减到与最少堆相等，用差值去补齐其他未配对堆，同样构造必败态 |
偶数堆全配对 | 先手无论怎么操作都必然破坏配对，后手可恢复配对，最终先手耗尽 |
n 的奇偶 | 配对情况 | SG | 胜负 |
|---|---|---|---|
奇数 | — | ≠ 0 | Alice 胜 |
偶数 | 不能两两配对 | ≠ 0 | Alice 胜 |
偶数 | 能两两配对 | = 0 | Bob 胜 |
六、算法实现思路
然后根据上面的规律我们可以得出这个正解思路：
1. 读入 n
2. 读入 n 个石子数，存入数组 a[]
3. 对 a 排序
4. 如果 n 是奇数 → 输出 1（Alice 胜）
5. 如果 n 是偶数：
检查是否所有 a[2i-1] == a[2i]（i=1..n/2）
若全等 → 输出 0（Bob 胜）
否则 → 输出 1（Alice 胜）
AC代码
#include <bits/stdc++.h>
#define ll long long
#define qwq ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 20;
int n;
int a[N];
int main() {
qwq;
while (cin >> n && n) {
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n % 2) cout << "1\n";
else {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == -114514) {
cnt++;
continue;
}
for (int j = 1; j <= n; ++j) {
if (i == j || a[j] == -114514) continue;
if (a[i] == a[j]) {
cnt++;
a[i] = a[j]= -114514;
break;
}
}
}
if (cnt == n) cout << "0\n";
else cout << "1\n";
}
}
return 0;
}