首页 > 代码库 > SG函数学（hua）习（shui）记录
SG函数学（hua）习（shui）记录
---恢复内容开始---
听说有一个东西叫SG函数
觉得自己好像原来是懂一些粗浅的应用但现在感觉要再深♂入一点呢
让我们先来介绍一下SG函数吧
这是某类满足下列条件的玄学博弈问题解法
- 双人、回合制；
- 信息完全公开（perfect information）；
- 无随机因素（deterministic）；
- 必然在有限步内结束（finite）；
- 没有平局；
- 双方可采取的行动相同（impartial）；
- 无法行动者判负（normal play）；
具体证明可以见https://zhuanlan.zhihu.com/p/20611132?columnSlug=maigo
那么我们现在有一个函数SG[i]表示某种状态的SG函数
且有SG[i] = mex{SG[k] | k->i(k是i的下一级状态)} SG[i] = SG[a1]^SG[a2]^SG[a3]^...^SG[ak] (a1...ak是组成状态i的子状态)
如果SG[i] == 0 那么 i 是一种必败态，不然是一种必胜态
于是介绍完了
下面上例题
http://www.lydsy.com/JudgeOnline/problem.php?id=1022
1 #include<stdio.h> 2 #include<stdlib.h> 3 int main() 4 { 5 int T,n,i,x,SG,flag; 6 scanf("%d",&T); 7 for(;T>0;T--) 8 { 9 scanf("%d",&n); 10 SG=flag=0; 11 for(i=1;i<=n;i++) 12 { 13 scanf("%d",&x); 14 SG^=x; 15 if(x!=1) flag=1; 16 } 17 if( (SG==0&&flag==0) || (SG!=0&&flag==1) ) printf("John\n"); 18 else printf("Brother\n"); 19 } 20 return 0; 21 }
这是一道最简单的SG函数题，连SG函数都不用存就可以一路推推推推出终态的SG函数
http://www.lydsy.com/JudgeOnline/problem.php?id=4035
1 #include<bits/stdc++.h> 2 #define N 100010 3 using namespace std; 4 int n,T,SG1[N],SG2[N],m; 5 6 int read(){ 7 int f = 0; char ch = getchar(); 8 while (ch > ‘9‘ || ch < ‘0‘ ) ch = getchar(); 9 while (ch <= ‘9‘&& ch >= ‘0‘) {10 f = f*10 + ch - ‘0‘;11 ch = getchar();12 }13 return f;14 }15 16 int nxt(int x,int y){ return (x==y)?y+1:y/(y/(x+1)); } 17 18 void GetSG(){ 19 int now,cnt,a[N]; bool bo[N];20 memset(SG1,0,sizeof(SG1));21 memset(bo,0,sizeof(bo));22 memset(SG2,0,sizeof(SG2));23 for (int i=1; i<=n; i=nxt(i,n)){ 24 now=cnt=0; 25 for (int j=2; j<=i; j=nxt(j,i)){ 26 int x=i/j; int t=(x>m)?SG2[n/x]:SG1[x]; 27 a[++cnt]=now^t; bo[a[cnt]]=1; 28 if ((i/x-i/(x+1))&1) now^=t; 29 } 30 now=1; while (bo[now]) now++; 31 (i <= m) ? SG1[i] = now : SG2[n/i]=now; 32 for (int j=1; j<=cnt; j++) bo[a[j]]=0; 33 } 34 } 35 36 int main(){37 n = read(); T = read(); m = (int)sqrt(n); GetSG(); 38 while (T--){39 int cnt = read(),ans = 0,x;40 for (int i = 1; i <= cnt; i ++){41 x = n/read();42 ans^=(x>m)?SG2[n/x]:SG1[x];43 }44 puts((ans)?"Yes":"No");45 }46 }
这题可以对每一个白格子位置搞SG：SG[i]=mex{SG[i*1]^SG[i*2]^...^SG[i*k]}，k∈[2,N/i]
但是我们会发现状态太多存不下
所以我们可以再推一推，发现每个SG函数只和n/i有关，所以状态数就变成了N^0.5个，大于N^0.5的状态就存在n/i里就好了
然后对于每一个状态，有很多状态都是冗余的，不需要计算，所以在循环的时候直接写成像这样就好了：
for (int i = 1; i <= n; i = n/(n/(i+1))) // 记得判 i == n时不要让程序计算n/(n/(i+1))不然会除0
——————————————————————————————————未完待 θ.θ 续——————————————————————————————————
SG函数学（hua）习（shui）记录