购物网站黑白,珠海市网站建设分站怎么样,wordpress主题访问慢,装修室内设计培训学校先#xff0c;定义一下 状态Position P 先手必败 N x先手必胜 操作方法#xff1a; 反向转移 相同状态 不同位置 的一对 相当于无 对于ICG游戏#xff0c;我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j#xff0c;且j是i的后继局面(即局面i可…先定义一下 状态Position P 先手必败 N x先手必胜 操作方法 反向转移 相同状态 不同位置 的一对 相当于无 对于ICG游戏我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j且j是i的后继局面(即局面i可以转化为局面j)我们用一条有向边从i出发到j连接表示局面i和局面j的点。则整个游戏可以表示成为一个有向无环图根据ICG游戏的定义我们知道任意一个无法继续进行下去的局面为终结局面即P局面(先手必败)。在上图中我们可以标记所有出度为0的点为P点。接着根据ICG游戏的两条性质我们可以逆推出所有点为P局面还是N局面 对于一个游戏可能发生的局面x我们如下定义它的sg值(1)若当前局面x为终结局面则sg值为0。(2)若当前局面x非终结局面其sg值为sg(x) mex{sg(y) | y是x的后继局面}。mex{a[i]}表示a中未出现的最小非负整数。举个例子来说mex{0, 1, 2} 3, mex{1, 2}0, mex{0,1,3}2我们将上图用sg函数表示后得到可以发现若一个局面x为P局面则有sg(x)0否则sg(x)0。同样sg值也满足N、P之间的转换关系若一个局面x其sg(x)0则一定存在一个后续局面ysg(y)0。若一个局面x其sg(x)0则x的所有后续局面ysg(y)0。由上面的推论我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中还有一个非常好用的定理叫做sg定理对于多个单一游戏Xx[1..n]每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。 先定义mex(minimal excludant)运算这是施加于一个集合的运算表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}3、mex{2,3,5}0、mex{}0。 对于一个给定的有向无环图定义关于图的每个顶点的Sprague-Grundy函数g如下g(x)mex{ g(y) | y是x的后继 },这里的gx即sg[x] 例如取石子问题有1堆n个的石子每次只能取{13,4}个石子先取完石子者胜利那么各个数的SG值为多少 sg[0]0f[]{1,3,4}, x1时可以取走1-f{1}个石子剩余{0}个mex{sg[0]}{0}故sg[1]1; x2时可以取走2-f{1}个石子剩余{1}个mex{sg[1]}{1}故sg[2]0 x3时可以取走3-f{1,3}个石子剩余{2,0}个mex{sg[2],sg[0]}{0,0}故sg[3]1; x4时可以取走4-f{1,3,4}个石子剩余{3,1,0}个mex{sg[3],sg[1],sg[0]}{1,1,0},故sg[4]2; x5时可以取走5-f{1,3,4}个石子剩余{4,2,1}个mex{sg[4],sg[2],sg[1]}{2,0,1},故sg[5]3 以此类推..... x 0 1 2 3 4 5 6 7 8.... sg[x] 0 1 0 1 2 3 2 0 1.... 计算从1-n范围内的SG值。 f(存储可以走的步数f[0]表示可以有多少种走法) f[]需要从小到大排序 1.可选步数为1~m的连续整数直接取模即可SG(x) x % (m1); 2.可选步数为任意步SG(x) x; 3.可选步数为一系列不连续的数用GetSG()计算 //f[]可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];
void getSG(int n)
{int i,j;memset(sg,0,sizeof(sg));for(i1;in;i){memset(hash,0,sizeof(hash));for(j1;f[j]i;j)hash[sg[i-f[j]]]1;for(j0;jn;j) //求mes{}中未出现的最小的非负整数{if(hash[j]0){sg[i]j;break;}}}
} SG打表 //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
int SG_dfs(int x)
{int i;if(sg[x]!-1)return sg[x];bool vis[110];memset(vis,0,sizeof(vis));for(i0;in;i){if(xs[i]){SG_dfs(x-s[i]);vis[sg[x-s[i]]]1;}}int e;for(i0;;i)if(!vis[i]){ei;break;}return sg[x]e;
} dfs 注意在SG表的初始化中不用每次都初始否则会T的因为可以循环利用这是一个强大的地方 HDU1536 实战 #includestdio.h
#includealgorithm
#includestring.h
using namespace std;
int s[110],sg[10010],n;
char op[200];
int SG_dfs(int x)
{int i;if(sg[x]!-1)return sg[x];bool vis[110];memset(vis,0,sizeof(vis));for(i0;in;i){if(xs[i]){SG_dfs(x-s[i]);vis[sg[x-s[i]]]1;}}int e;for(i0;;i)if(!vis[i]){ei;break;}return sg[x]e;
}
int main()
{int k;while(scanf(%d,n)!EOF){if(n0)break;for(int i0 ; in ; i)scanf(%d,s[i]);sort(s,sn);int m,cnt0;scanf(%d,m);memset(sg,-1,sizeof(sg));for(int i0 ; im ; i){scanf(%d,k);int x0;while(k--){int w;scanf(%d,w);x^SG_dfs(w);}if(x!0)printf(W);elseprintf(L);}puts();}return 0;
} View Code 转载于:https://www.cnblogs.com/shuaihui520/p/9564718.html
