算法基础之集合-Nim游戏

集合-Nim游戏

• 核心思想： 博弈论

  • sg函数：在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····,yk的SG函数值构成的集合在执行mex运算的结果,即:SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
    **特别地,**整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).
    • mex函数：设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算

•   #include <iostream>#include <cstring>#include <algorithm>#include <unordered_set>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<m;i++){int sum = s[i];if(x >= sum) S.insert(sg(x-sum));}for(int i=0;;i++)if(!S.count(i))return f[x] = i;}int main(){cin>>m;for(int i=0;i<m;i++) cin>>s[i];cin>>n;memset(f,-1,sizeof f);int res=0;for(int i=0;i<n;i++){int x;cin>>x;res ^= sg(x);}if (res) puts("Yes");else puts("No");}