题解 | #取石子#

前面几天补了SG函数的知识点就来写一篇题解。

因为两堆石子可以看作两个单独的ICG（公平组合游戏）游戏，这个游戏规则对两个人公平于是我们可以使用sg函数。

我们定义一个函数,对于公平组合游戏来说 ,这个公式意味着从 的状态转移到 状态，也就是找到 可转移集合中没有出现的最小非负整数。其中 。我们一般把 称为必输态。

对于由很多个ICG组合成的一个复杂游戏，我们有Sprague–Grundy 定理

定义若干个的组合构成的一个游戏：两个玩家轮流对这个游戏中的任意进行操作一次，当所有的子游戏无法操作时，游戏结束。计两个 游戏的状态分别为 ，则这两个 游戏和状态就是 。对于函数有：

其中 代表异或操作。

我们可以将 定理推广值多元有：

这样我们就可以将单一游戏的情况推广到全局游戏。若最终时，就可以判断谁必败，谁必胜。

在本题中

预处理前100的sg值。 最后判断sg(n+m)==0即可。

int pd[105];
int num[]={1,3,9};
void solve(){
    for(int i=1;i<=100;i++){
        int sg=0;
        //vector<int> seek;
        int used[5]={0};
        for(int j=0;j<3;j++){
            if(i-num[j]>=0){
                used[pd[i-num[j]]]=1;
            }
        }
        while(sg<5&&used[sg])++sg;
        pd[i]=sg;
    }
    while(cin>>n>>m){
        int ans=0;
        ans^=pd[n];
        ans^=pd[m];
        if(ans) cout<<"win"<<endl;
        else cout<<"lose"<<endl;
    }
}