9

NIM游戏/SG函数 - 腾云今天首飞了吗

 1 year ago
source link: https://www.cnblogs.com/CZ-9/p/17280698.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

NIM游戏

先看一下一维 NIM游戏。

有一堆大小为 n 的石子，甲和乙轮流从石堆里面拿石子，不能一次拿掉所有石子，取走最后一个石子的人获胜，甲先开始，谁是必胜的？

显然，谁先手，谁就获胜。那么推广到二维呢？

有两堆大小为 nm 的石子，甲和乙轮流从两个石堆里拿石子，每次从一个石堆里拿石子，不能一次拿掉一堆中所有石子，取走最后一个石子的获胜，甲先开始拿，谁是必胜的？

当 n=m 的时候，先手必输。因为先手从一堆中拿 Y 颗，后手也可以从另外一个堆中拿 Y 颗。循环下去，后手必胜。
而如果 n!=m，先手就可以制造两堆相等的石子，使得后手必败。

引入点新概念。当两堆相等时，先手必败，我们将这种状态叫做必败态。记为 P。
当两堆不相等时，先手必胜，将这种状态叫做必胜态，记为 N。

那么，推广到多维，如何确定谁是必胜的呢？
由前两种NIM游戏可以知道，如果所有石堆大小都相等，那么先手是不能直接取得胜利的。这种状态称为平衡态。反之，可以进行一次操作就取得胜利的状态就是非平衡态。平衡态也就是必胜态，非平衡态也就是必败态。
考虑将所有石堆的大小异或起来，如果结果为 0，那么这就是一个平衡态。如果结果不为零，那就是非平衡态。
我们每拿一次石子，都可以将异或时某一位上的值由这位上的 1 的奇偶性决定。因此我们拿石子时可以控制每一位上 1 的奇偶性，也就因此能控制异或出的总结果了。同样的，对手每操作一次，由于必须拿至少一颗石头，就势必将会影响某一位上 1 的数量，状态必然会改变。这就意味着我们在操作的时候，可以实现平衡态和非平衡态之间的转化。

如果一开始我们接手的是一个不平衡态，要取胜，就可以反复给对手构造一个平衡态，这是必胜的。
如果一开始接手的是一个平衡态，只要对手足够聪明，就可以让我们每次都拿到一个平衡态。这就是必败的。

由刚才的论述可知，必胜态和必败态之间是可以相互转化的。必败态经过一次操作必然会转化为必胜态，必胜态经过一次操作可能是必胜态，也可能是必败态（想想异或的过程）。当一个状态已经转化为能够分出胜负的必败态时，称这个状态是0级必胜点，记作 SG(x)=0（x 描述了当前的状态）。
如果某个状态最少操作一次就能变为0级必胜点，那么这个状态就是1级必胜点，以此类推，有2级，3级……必胜点。而SG函数就是用来描述每个状态到达终末态时所需要的最少的步骤，即描述每个状态是几级必胜点。定义为：

SG(x)=MEX{SG(y)|x−>y}

  • 两个同级必胜点（SG函数值相等）组成的游戏是必败的。因为先手如果降低其中一个必胜点的等级，后手可以降低另一个必胜点的相同数量的等级，使先手一直面对两个同级必胜点，最后面对两个1级必胜点，只能将其中一个必胜点变成必败点，这样先手必败。

  • 两个不同级必胜点（SG函数值不同）组合成的的游戏是必胜的，因为先手可以将等级高的必胜点的等级降低到与另一个必胜点相同，这样后手面对的就是由两个同级必胜点构成局面，先手必胜。

对于一个游戏，可以将组成它的每一个游戏的SG函数值异或起来，为 0，则对于先手来说必败，反之对于先手就是必胜的。这就是 SG定理了！

Fibonacci again and again

三堆大小分别为 n，m，p 的石子，每堆大小均不超过 1000，两个人拿，令 x 为菲波那契数列中的一项，每个人每次只能从一堆里拿 x 个石子，问谁是必胜的。

板题，主要想说说怎么记忆化搜索求SG函数值。




int sg[MAXN + 5],f[MAXN + 5];//f为菲波那契数列
int getsg(int num){
    if(num == 0)return sg[num] = 0;
	if(sg[num] != -1)return sg[num];
	bool vis[MAXN + 5];//表示从石子数为num可以转换到哪些状态
	for(int i = 1; i <= MAXN: i++){
		vis[num - f[i]] = 1;
		getsg(num - f[i]);
	}
	for(int i = 0; ; i++){
		if(!vis[i])return sg[num] = i;//找mex，求出是几级必胜点
	}
	return sg[num];
}




求出三个数的SG值后，看 SG(n)SG(m)SG(p) 是否为 0 即可得出答案。


A multiplication game




给定一个 n，令 p=1，甲和乙可以每次将 p 乘上一个属于 [2,9] 的数，谁使 p 大于 n 谁就赢。求谁是必胜的。







#include<iostream>
#include<cstring>
#include<map>
#define int long long
using namespace std;
const int MAXN = 1e5;
int n;
map<int,int> sg,vis;
int getsg(int x){
    if(x >= n)return sg[x] = 0;
    if(vis.find(x) != vis.end())return sg[x];
    vis[x] = 1;
    int s[10];//9的十次方已经大于n的最大值了，故sg函数的值最大为9
    memset(s,0,sizeof s);
    for(int i = 2; i <= 9; i++){
        s[getsg(x * i)] = 1;
    }
    for(int i = 0; i < 10; i++){
        if(!s[i])return sg[x] = i;
    }
    return sg[x];
}
signed main(){
    while(~scanf("%lld",&n)){
        sg.clear();
        vis.clear();
        getsg(1);
        if(sg[1])cout << "Stan wins.\n";
        else cout << "Ollie wins.\n";
    }
}




Cutting Game




两个人在一张大小为 h∗w 纸上面切，每个人每次可以横着切一刀，也可以竖着切一刀，谁切出了 1∗1 大小的纸，谁就获胜，问谁必胜。




注意到状态是二维的，即当前纸的长与宽。注意下SG函数的记录方法。





#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1e3;
int sg[MAXN + 5][MAXN + 6],n,m;
int getsg(int x,int y){
    if(x < y)swap(x,y);
    if(sg[x][y] != -1)return sg[x][y];
    if(x == 1 && y == 1)return sg[x][y] = 1;
    bool vis[4001];
    memset(vis,0,sizeof vis);
    for(int i = 2; i <= x - 2; i++){//横着切
        vis[getsg(i,y) ^ getsg(x - i,y)] = 1;//每切一刀，就将当前纸分成了两张，也就是分成了两个子游戏，因此取异或的值
    }
    for(int i = 2; i <= y - 2; i++){//竖着切
        vis[getsg(x,i) ^ getsg(x,y - i)] = 1;
    }
    for(int i = 0; i <= 4000; i++){
        if(!vis[i])return sg[x][y] = i;
    }
    return sg[x][y];
}
int main(){
    memset(sg,-1,sizeof sg);
    for(int i = 2; i <= MAXN; i++){
        sg[1][i] = 0;
    }
    while(~scanf("%d%d",&n,&m)){
        int ans = getsg(n,m);
        if(ans)cout << "WIN\n";
        else cout << "LOSE\n";;
    }
}




__EOF__

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK