博弈SG函数模板

mac2022-06-30  17

#define maxn 1e4+10//maxn为堆中最大个数 #define cmax 1005//cmax为取个数的方法总数 using namespace std; int sg[maxn];//记录sg[n](n为堆的个数)sg值 int mex[maxn];//模拟mex运算 int get[cmax];// void get_sg() { // 例如有三种情况的取石子方法 get[1] = 1,get[2] = 2,get[3] = k; // 然后注意如果题目所要求堆个数过大即要找规律,不能直接用sg函数运算 memset(sg,0,sizeof(sg)); //i小于需要求的sg范围:默认堆最大个数maxn内 for(int i=1;i<=maxn;i++) { memset(mex,0,sizeof(mex)); //条件为get[j]必须小于i才合法&&总类数小于cmax //要根据不同题目要求来写对应的取法 for(int j=1;get[j]<=i&&j<=cmax;j++) mex[sg[i-j]]=1;//状态转移(注意根据不同题要求来写) //比如:此题分堆问题,mex[sg[j]^sg[i-g]]=1; for(int j=0;j<=maxn;j++)//j小于等于堆中最大个数 { if(!mex[j]) { sg[i]=j; break; } } //找规律输出 // printf("sg[%d]:%d\n",i,sg[i]); } }

转载于:https://www.cnblogs.com/Tianwell/p/11442383.html

最新回复(0)