文章

25

粉丝

0

获赞

0

访问

244624

头像
博弈-SG函数(cutting game )
经验总结
发布于2020年4月18日 22:24
阅读数 8466

SG函数的模板:

//f[N]:可改变当前状态的方式,N为方式的种类,f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0,所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
            SG[i] = j;
            break;
        }
    }
}

(2)cutting game:

有一张W∗H大小的网格纸,每个人每次可以选择一块纸片沿任意一条网格线剪开,先剪出1∗1大小方格者胜。
问是否先手必胜。2≤W,H≤200

#include<iostream>
using namespace std;
const int N = 210;
int SG[N][N], w, h;
int f[N];//标记子游戏的SG取值,进行mex运算

int main(){
	//对每种纸片求SG值SG[i][j]
	for (int i = 2; i <= 200; i++){//行
		for (int j = 2; j <= 200; j++){//列     
			memset(f, 0, sizeof f);
			for (int u = 2; i - u >= 2; u++){
				f[SG[u][j] ^ SG[i - u][j]] = 1;
			}
			for (int v = 2; j - v >= 2; v++){
				f[SG[i][v] ^ SG[i][j - v]] = 1;
			}
			//mex
			for (int k = 0; k <= 200; k++){
				if (!f[k]){
					SG[i][j] = k;
					break;
				}
			}
		}
	}

	while (cin >> w >> h){
		if (SG[w][h]){
			cout << "WIN" << endl;
		}
		else{
			cout << "LOSE" << endl;
		}
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发