概念
1、平等组合游戏
- 两人游戏，两人轮流走步
- 有一个状态集，而且通常是有限的
- 有一个终止状态，到达终止状态后游戏结束
- 游戏可以在有限的步数内结束
- 规定好了哪些状态转移是合法的
- 所有规定对于两人是一样的
象棋围棋并不满足最后一个条件，因为双方可移动的策略并不相同
下面的均是在平等组合游戏的前提下讨论
2、N状态（必胜）P状态（必败）
对于最后走的人获胜的情况：
在保证最优策略情况下，这两种状态有三个准则
- 所有的终止状态都为P状态
- 对于任意的N状态，存在至少一条路径可以转移到P状态
- 对于任意的P状态，只能转移到N状态
类型
例一：经典1、2、3石子
有A和B两个竞争者，有n个石子，每次可取1、2、3颗，A先手，取走最后一个的人获胜
问题：A能否保证自己胜利
当\(n=4*k\), \(k\)为非负整数时A必败
因为B总能取走和A的数和为4的石子，一定最后取到最后一个
当不是该情况时，A可以先手构造出B的先手必败情况，所以A必胜
例二：取走特定数的石子
有A和B两个竞争者，有n个石子，每次可取\(p[1]\),\(p[2]\),\(p[3]\)\(……\)\(p[k]\)颗，A先手，取走最后一个的人获胜
那么，AA还有必胜策略吗？
有没有必胜策略，我们关键是要找到哪些状态是P状态，哪些状态是N状态.
不过，本题没有那么容易判断，因此我们需要引入一个新东西——\(SG\)函数
为了方便理解：我们先对每个状态（这里是剩余的石子数）设一个点，对于状态\(u\)，通过一次操作能够到达的状态为其的儿子节点，连单向边
定义\(SG(x)\)为x的后继节点的SG值构成的集合执行\(mex()\)运算后的值
\(mex()\)：设集合S是一个非负整数集合，mex(S)就是求不属于S的最小非负整数。
放个图
通过这里也可以更好的理解前面的三个准则
定理1：同一个图上
对于一个图GG，如果SG(G)!=0，则先手必胜，反之必败
证明：
若SG(begin)=!0
1.根据性质2，先手必可以走向0，
2.因此留给后手的是0，根据性质3，后手只能走向非0
3.以此类推，后手始终无法走向0，后手永远处于非0，当先手到达终点的0时，先手获胜
反之同理，必败
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define pdd pair<double ,double >
using namespace std;
const int N = 110, M = 10010;
int n,m;
int s[N], f[M];
int sg(int x){
if(f[x]!=-1) return f[x];
unordered_set<int> S;
for(int i=0;i<n;i++)
//如果可以减去s[i]，则添加到S中
if(x>=s[i]) S.insert(sg(x-s[i]));
//求mex()，即找到最小并不在原集合中的数
for(int i=0; ; i++)
if(!S.count(i)) return f[x]=i;
}
void solve(){
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
memset(f,-1,sizeof f);
cin>>m;
int ans=0;
while(m--){
int x;cin>>x;
ans^=sg(x);
}
if(ans) puts("Yes");
else puts("No");
}
signed main(){
int t=1;
// cin>>t;
while(t--)
solve();
return 0;
}
待补