CCF NOI 考纲里提到了 零和博弈 和 SG函数
没有提到不平等博弈
意味着双方优化目标是完全相反的，可以和贪心 动态规划 等结合
设想一个这样的游戏，在一个有向无环图上，有一枚棋子放在某点，双方轮流操作，每次操作是沿着某条边移动这枚棋子，无法操作的输。
这个题目是一个非常简单的动态规划，如果从点出发，先手必胜设，后手必胜设。对于点，如果没有出边，或者只能到达值为的节点，那么；否则。
Chomp
除了的情况，先手必胜，因为先手总是可以用后手获胜的策略取胜。
poj 2931
不平等博弈
其经典的例子就是囚徒困境。囚徒困境是一个非零和博弈。大意是：一个案子的两个嫌疑犯被分开审讯，警官分别告诉两个囚犯，如果你招供，而对方不招供，则你将被立即释放，而对方将被判刑10年；如果两人均招供，将均被判刑2年。如果两人均不招供，将最有利，只被判刑半年。于是两人同时陷入招供还是不招供的两难处境。但两人无法沟通，于是从各自的利益角度出发，都依据各自的理性而选择了招供，这种情况就称为纳什均衡点。这时个体的理性利益选择是与整体的理性利益选择不一致的。
一句话：纳什均衡局面下，单方面改变策略无法使自己更好
比如石头剪刀布游戏中，以1/3概率选择每一个选项，就是一个混合策略
这个混合策略是最优的，即使对方知道自己的策略，对方也无法获得更大收益
练习题：如果以石头获胜得10分，以布获胜得5分，以剪刀获胜得2分，那最优策略是什么？
石头概率x
布概率y
剪刀概率z
石头 (2/17)
布 (10/17)
剪刀 (5/17)
poj 1704
将之间的距离作为石子堆，对于阶梯博弈，偶数堆不影响，相当于奇数堆的NIM。
Luogu P1290
欧几里得博弈，谁先有机会减倍或以上，谁就必胜。
hdu 3863
游戏是对称的，先手必胜。
poj 1082
考虑月日之和。如果是偶数，那么先手必胜；如果是奇数，那么先手必败。
9月30日和11月30日因为可以进位到下一个月，先手必胜。
https://www.luogu.com.cn/problem/P4643
贪心
https://acm.hdu.edu.cn/showproblem.php?pid=1846
巴什博奕 (Bash game)
n个石子，每次只能取1到m个，双方轮流操作
问先手必胜还是后手必胜？
https://acm.hdu.edu.cn/showproblem.php?pid=1847
n个石子，每次只能取2的次幂个，双方轮流操作
先手必胜输出Kiki，后手必胜输出Cici
看是不是3的倍数，
3的倍数先手必败
不是3的倍数先手必胜
石子数可以很大，也可以很多堆
https://acm.hdu.edu.cn/showproblem.php?pid=1850
取石子游戏，如果先手必胜的话，输出第一步的方案数
https://acm.hdu.edu.cn/showproblem.php?pid=5229
除非一步获胜，否则看总长度的奇偶
https://acm.hdu.edu.cn/showproblem.php?pid=6105
输入一个树
Bob在游戏开始之前，可以选择删掉树中至多k条边，把树变成森林
Alice和Bob轮流操作，Alice先
Alice每次操作选一个未染色的点染成白色
Bob每次操作选一个未染色的点，把这个点和相邻的点染成黑色
如果最后所有点都是黑色Bob获胜，如果存在白色的Alice获胜
https://www.spoj.com/problems/ADAFIMBR/
n个石子，每次只能取斐波那契数个，双方轮流操作
先手必胜输出Ada，后手必胜输出Vinit
https://codeforces.com/problemset/problem/1194/D
n个石子，每次只能取1个或2个或k个，双方轮流操作
先手必胜输出Alice，后手必胜输出Bob
只有一堆石子，找规律即可
https://codeforces.com/problemset/problem/603/C
有两个人做游戏，游戏规则如下：
有n堆石子，每次可以对一堆石子进行操作，如果当前石子是偶数
那么可以选择将这2 * x个石子分成k堆石子数为x的石子堆
还有一种没有前提的操作是取走当前堆的一个石子
问先手赢还是后手赢，先手和后手都足够聪明的情况下。
先手赢输出Kevin，后手赢输出Nicky
n堆石子，对一堆石子找规律即可
https://codeforces.com/problemset/problem/494/E
有一个 n×n 的棋盘，初始全黑，有 m 个矩形是白色。
Hamed 和 Malek 玩游戏，Hamed 是先手。
每次可以选出一个右下角是白色的边长不超过 k 的棋盘并将其反色。
不能操作人输，问谁赢。
先打表发现规律 SG(x,y) = min(lowbit(x), lowbit(y), highbit(k))
然后按位做
对于每一位来说，是一个矩形求面积并的问题
http://codeforces.com/problemset/problem/1149/E
高维 SG
只要能在更高维 SG 中获胜，可以对以后所有局面产生影响
n堆石子 a1 .. an
n堆石子 b1 .. an
每次操作选一堆从中拿走若干个
特别的，如果这一次操作是从ai中拿去的若干个，那么可以任意修改bi（可以改成0，改小，不变，改到任意大）
无法操作的输
先手必败条件：如果所有ai异或为0，且所有bi异或为0
先手必胜条件：如果所有ai异或非0，或（所有ai异或为0且所有bi异或非0）
https://www.luogu.com.cn/problem/CF1110G
先手不败
分类讨论
https://www.luogu.com.cn/problem/CF794E
从K=0开始分类讨论
https://www.luogu.com.cn/problem/CF388C
偶数大小的堆一定平分，奇数大小的堆，把中间的一张排序
https://acm.hdu.edu.cn/showproblem.php?pid=6415
问有多少个矩阵，存在唯一的纳什均衡
最大值一定是纳什均衡
对于其他每个值，同一行或同一列一定有比他大的数字
f[i][j][k]已经放了最大的i个数字，占据了j行k列
https://atcoder.jp/contests/agc002/tasks/agc002_e
转化为在网格图中走，找规律
https://atcoder.jp/contests/agc010/tasks/agc010_f
枚举根节点，每个根节点DFS判断
https://www.spoj.com/problems/COT3/
对于每个子树记录
不操作的SG值
操作一次能到的SG值集合
就可以得到暴力做法了
为了优化效率，集合需要支持
集合中所有数字异或x
合并两个集合
求mex
这些操作都可以用trie实现
https://projecteuler.net/problem=344
n个格子，上面放c个普通棋子，1个特殊棋子
双方轮流操作，每次选一个棋子向左移动若干步
不能不移动，不能越过其他棋子，可以移出棋盘并且获得这个棋子
谁获得特殊棋子谁获胜
W(n,c)表示，这个游戏先手必胜的局面个数
求W(1000000, 100)
第一个问题，什么局面先手必胜
如果特殊的在第一个，先手直接获胜
否则如果有奇数个硬币，需要在第一个之前加一个假硬币，让所有硬币两两成对
如果特殊的是第二个，那么在第一个之前加的硬币应该在-1的位置上上（第一个硬币至多挪到0，挪到出界就输了）
如果特殊的不是第二个，那么在第一个之前加的硬币应该在-2的位置上上（第一个硬币可以挪到0，也可以出界）
棋子个数m = 普通棋子个数c + 特殊棋子个数1
基本思路是全部局面 - 必败局面
全部局面是C(n, m) * m
必败局面分为3类
特殊的在第一个，先手必胜，没有必败局面
特殊的在第二个，把 n-m 个空位分给(m+1)/2对 内部，然后剩下一些1，插入到m/2+1对 的之间，
(m+1)/2对 内部 的 空位个数 异或为0
m/2+1对 的之间 的 空位个数 任意
这个可以用动态规划来做
f[i][j][k] 还剩下i个空位来分配，有j对（注意j几乎不变的），2的k次方以下的都已加入
特殊的不在前二个，这个额外要求第一对内部之间不能为0，这个也用容斥来做
第一对内部空位个数任意 的方案数 减去 第一对内部空位个数为0 的方案数
https://www.luogu.com.cn/problem/P4363
注意到总状态数C(n+m,n)
对于每个状态计算最优解即可
《浅谈如何解决不平等博弈问题》
《浅谈SG游戏的若干拓展及变形》