做悬赏的网站,路由器统一登录网站,网站稳定期的推广,网站外链查询集合-Nim游戏 核心思想#xff1a; 博弈论 sg函数#xff1a;在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,yk,定义SG(x)的后记节点y1,y2,,yk的SG函数值构成的集合在执行mex运算的结果,即:SG(x)mex({SG(y1),SG(y2)SG(yk)}) **特别地,**整个有向图…集合-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_setusing 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_setint S;for(int i0;im;i){int sum s[i];if(x sum) S.insert(sg(x-sum));}for(int i0;;i)if(!S.count(i))return f[x] i;}int main(){cinm;for(int i0;im;i) cins[i];cinn;memset(f,-1,sizeof f);int res0;for(int i0;in;i){int x;cinx;res ^ sg(x);}if (res) puts(Yes);else puts(No);}
