SG函数学（hua）习（shui）记录

时间：2023-11-10 09:23:08

---恢复内容开始---

听说有一个东西叫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

 #include<stdio.h>

 #include<stdlib.h>

 int main()

 {

     int T,n,i,x,SG,flag;

     scanf("%d",&T);

     for(;T>;T--)

     {

         scanf("%d",&n);

         SG=flag=;

         for(i=;i<=n;i++)

         {

             scanf("%d",&x);

             SG^=x;

             if(x!=) flag=;

         }

         if( (SG==&&flag==) || (SG!=&&flag==) ) printf("John\n");

         else printf("Brother\n");

     }

     return ;

 }

BZOJ 1022

这是一道最简单的SG函数题，连SG函数都不用存就可以一路推推推推出终态的SG函数

http://www.lydsy.com/JudgeOnline/problem.php?id=4035

 #include<bits/stdc++.h>

 #define N 100010

 using namespace std;

 int n,T,SG1[N],SG2[N],m;

 int read(){

     int f = ; char ch = getchar();

     while (ch > '' || ch < '' ) ch = getchar();

     while (ch <= ''&& ch >= '') {

         f = f* + ch - '';

         ch = getchar();

     }

     return f;

 }

 int nxt(int x,int y){ return (x==y)?y+:y/(y/(x+)); }  

 void GetSG(){

     int now,cnt,a[N]; bool bo[N];

     memset(SG1,,sizeof(SG1));

     memset(bo,,sizeof(bo));

     memset(SG2,,sizeof(SG2));

     for (int i=; i<=n; i=nxt(i,n)){

         now=cnt=;

         for (int j=; j<=i; j=nxt(j,i)){

             int x=i/j; int t=(x>m)?SG2[n/x]:SG1[x];

             a[++cnt]=now^t; bo[a[cnt]]=;

             if ((i/x-i/(x+))&) now^=t;

         }

         now=; while (bo[now]) now++;

         (i <= m) ? SG1[i] = now : SG2[n/i]=now;

         for (int j=; j<=cnt; j++) bo[a[j]]=;

     }

 }  

 int main(){

     n = read();    T = read(); m = (int)sqrt(n); GetSG();

     while (T--){

         int cnt = read(),ans = ,x;

         for (int i = ; i <= cnt; i ++){

             x = n/read();

             ans^=(x>m)?SG2[n/x]:SG1[x];

         }

         puts((ans)?"Yes":"No");

     }

 }

BZOJ4035

这题可以对每一个白格子位置搞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 = ; i <= n; i = n/(n/(i+))) // 记得判 i == n时不要让程序计算n/(n/(i+1))不然会除0

——————————————————————————————————未完待 θ.θ 续——————————————————————————————————

相关文章