SG函数

在有向无环图上，有多个棋子，双方轮流操作，每次选择一枚棋子移动，谁无法移动谁就输了。
对于每个点计算SG值，SG值为所有能走到的点的mex。

mex(S)表示S集合中没出现过的最小的自然数。

这类题目往往需要通过暴力求出SG值，之后再找规律

Anti-SG

将取石子游戏的谁取最后一个赢，改为谁取最后一个输。

检查是否有一堆石子个数大于1，
如果有，和之前的版本一样，异或为0，先手必败，异或非0，先手必胜。
如果没有，和之前的版本相反，异或为0，先手必胜，异或非0，先手必败。

取石子游戏（Nim博弈）

https://en.wikipedia.org/wiki/Nim

$n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，不能不取，无法操作的输。

这是一个经典问题，如果所有 $a_i$ 的异或是 $0$ ，那么先手必败，否则先手必胜。
可以简单的理解为，必胜策略就是保证自己操作之后，所有 $a_i$ 的异或为 $0$ ，对手的操作必然破坏这性质，自己需要再进行一次操作使得所有 $a_i$ 异或为零。

P2197 【模板】nim游戏

所有石子个数 xor
如果结果非0，先手必胜
如果结果是0，先手必败game

hdu 3590
这是一个错题。

上面这个 $5$ 个点的数据，先手必败，但是标程会输出先手必胜。

SG值为0也可以操作

hdu 3197
hdu 3094
砍树游戏，每个点的SG值等于所有孩子节点的SG值加一的异或。

题目描述

Alice 和 Bob 在玩游戏。

他们有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，保证初始时 $a_i \leq a_{i + 1}(1 \leq i < n)$ 。现在他们轮流对这些石子进行操作，每次操作人可以选择满足 $a_i > a_{i - 1}$ （ $a_0$ 视为 $0$ ）的一堆石子，并从中取走一个。谁最后不能取了谁输。Alice 先手，他们都使用最优策略，请判断最后谁会取得胜利。

输入格式

第一行一个整数 $n(1 \leq n \leq 100)$ ，表示石子堆数。

接下来一行 $n$ 个数，第 $i$ 个数为 $a_i(1 \leq a_i \leq 10^9)$ ，意义如上所述。

输出格式

"Alice" 或 "Bob"，表示谁会赢。

样例 #1

样例输入 #1

1
1

样例输出 #1

Alice

样例 #2

样例输入 #2

1
2

样例输出 #2

Bob

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x;
long long s;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		s += x;
	}
	cout << (s & 1 ? "Alice" : "Bob") << endl;
	return 0;
}