mex函数

将图上一个点可以到达的所有点的mex值组成一个集合

集合中不存在的最小自然数

此题用到的图

将终点状态（所有无法继续操作的石子数）的mex值设为0

起点为其中一堆石子的石子数

通过每种石子数可以到达的状态算出起点的mex值

就像这样：（样例的第3堆石子）

它的mex值就是：

所以mex(7)=0

必胜态和必败态

（这里只考虑一幅图）

当这幅图的起点的mex值为0

就是必败态

否则就是必胜态

原因：

从mex值的定义可以看出

当一个点的mex值为0

它一定只能到达mex值不为0的点

当一个点的mex值不为0

它一定可以到达mex值为0的点（双方都绝顶聪明，所以一定会到达mex值为0的点）

这时因为所有终点的mex值都是0

所以起点的mex值为零

说明先手一定走不到终点

所以是必败态

否则先手一定会走到终点

就是必胜态

解题方法

把n堆石子作为n幅图的起始点

每一步只能选择一幅图走一步

一个点的mex值为x

说明它可以到达mex值为0~x-1中任意一个自然数的点

所以可以从起点的mex值中拿取任意数值

有n个起点

这不就是经典nim游戏吗？！

所以把所有图起点的mex值亦或起来，就是结果

C++ 代码

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
int f[10005],s[105],k,n;
int sg(int x){  //用来求mex值
    if(f[x]!=-1)    //记忆化搜索，可以优化掉不少
        return f[x];
    unordered_set<int> vis; //用来记录所有可以到达的点的mex值
    for(int i=0;i<k;i++)
        if(x>=s[i]) //可以这么拿
            vis.insert(sg(x-s[i]));
    for(int i=0;;i++)
        if(!vis.count(i))
            return f[x]=i;  //求出x点的mex值
}
int main(){
    memset(f,-1,sizeof f);
    scanf("%d",&k);
    for(int i=0;i<k;i++)
        scanf("%d",&s[i]);
    scanf("%d",&n);
    int ans=0;
    while(n--){
        int now;
        scanf("%d",&now);
        ans^=sg(now);
    }
    puts(ans?"Yes":"No");
    return 0;
}