1.Mex运算:
设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;
2.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).
3.有向图游戏的和
设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)
代码:
#include #include #include #include using namespace std; const int N=110,M=10010; int n,m; int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值 int sg(int x) { if(f[x]!=-1) return f[x]; //因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可 set S; //set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同) for(int i=0;i<m;i++) { int sum=s[i]; if(x>=sum) S.insert(sg(x-sum)); //先延伸到终点的sg值后,再从后往前排查出所有数的sg值 }
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));//初始化f均为-1,方便在sg函数中查看x是否被记录过 int res=0; for(int i=0;i<n;i++) { int x; cin>>x; res^=sg(x); //观察异或值的变化,基本原理与Nim游戏相同 } if(res) printf("Yes"); else printf("No"); return 0;
}
往年题解(非常lj,可直接跳过)
将每一个h[i]h[i]的所有方案看做是一张有向图，例
若S=[2,5],h=10S=[2,5],h=10,则有如下展开形式：
mex()：mex()：设集合S是一个非负整数集合，定义mex(S)mex(S)为求出不属于S的最小非负整数的运算，即：mes(S)=min[x],其中xmes(S)=min[x],其中x属于自然数，且xx不属于SS（用人话说就是不存在SS集合中的数中，最小的那个数）
SG()：SG()：在有向图中，对于每个节点xx，设从xx出发共有kk条有向边，分别达到节点y1，y2……yky1，y2……yk，定义SG(x)SG(x)为xx的后继节点的SGSG值构成的集合执行mex()mex()运算后的值
即：SG(x)=mex(SG(y1),SG(y2)…SG(yk))SG(x)=mex(SG(y1),SG(y2)…SG(yk))；（用人话说就是比后继节点的SGSG都小的值）
特别的整个图GG的SGSG值被定义为起点ss的SGSG值，即SG(G)=SG(s)SG(G)=SG(s)
上图标红的值就是每一个节点的SGSG值
性质：1.SG(i)=k，则i最大能到达的点的SG值为k−1。1.SG(i)=k，则i最大能到达的点的SG值为k−1。
2.非0可以走向0 2.非0可以走向0
3.0只能走向非0 3.0只能走向非0
定理：
对于一个图GG，如果SG(G)!=0SG(G)!=0，则先手必胜，反之必败
证明：
若SG(G)=!0SG(G)=!0，
1.根据性质2，先手必可以走向0，
2.因此留给后手的是0，根据性质3，后手只能走向非0
3.以此类推，后手始终无法走向0，后手永远处于非0，当先手到达终点的0时，先手获胜
（由此我们可以知道，有些事是命中注定的~~~）
反之同理，必败
定理：
对于n个图，如果SG(G1)SG(G1) ^ SG(G2)SG(G2) ^ … SG(Gn)!=0SG(Gn)!=0 ,则先手必胜，反之必败
证明（类似与Nim游戏）：
①当SG(Gi)=0SG(Gi)=0 时 ， xor=0xor=0 ， 显然先手必败
（PS：结束状态必是状态①，但状态①不一定是结束状态）
②当xor=x!=0xor=x!=0 时，因为肯定存在一个SG(xi)SG(xi)^x <SG(xi)<SG(xi),而根据SG()SG()的性质1可知，SG(k)SG(k)可以走到0−k−10−k−1的任何一个状态，
因此，必定可以从SG(xi)−>SG(xi)SG(xi)−>SG(xi)^xx ， 于是使得xor=0xor=0
③当xor=0xor=0时，当移动任何一个节点时，对应的SGSG值必然减小，可以证明：xor!=0xor!=0
下证：xor!=0xor!=0
假设:xor=0xor=0,则说明移动的那个节点的值并没有变化，即从SG(k)SG(k)变成了kk，但是这与SGSG函数的性质1相矛盾，因此不成立
证得：若先手面对的状态是xor!=0xor!=0,则先手方总能使xor=0xor=0，即使后手面对的永远是必败态直到结束状态①，因此先手必胜！
反之，必败！
C++ 代码
#include #include <unordered_set> #include 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];//记忆化搜索，如果f[x]已经被计算过，则直接返回
// 因为这题中较大堆的拆分情况独立于较小堆，因此有别于894.拆分-Nim，这里的S必须开成局部变量 unordered_set<int> S;//用一个哈希表来存每一个局面能到的所有情况，便于求mex for(int i = 0 ; i < m ; i++) if(x >= s[i]) S.insert(sg(x - s[i]));//如果可以减去s[i]，则添加到S中 for(int i = 0 ; ; i++)//求mex()，即找到最小并不在原集合中的数 if(!S.count(i)) return f[x] = i;
} int main() { cin >> m; for(int i = 0 ; i < m ; i++) cin >> s[i];
memset(f , -1 , sizeof f); cin >> n; int res = 0; while(n--) { int x; cin >> x; res ^= sg(x); } if(res) puts("Yes"); else puts("No"); return 0;
}
