SGs

SG函数及SG定理

  • SG函数

    所有的组合游戏最后都能抽象成为一个DAG,得到了DAG我们就可以对所有点的SG函数进行求解。

    SG函数的定义为: SG(x)=mex\{ SG(y)|x→y \} ,其中y为x所有的后继状态。

    当SG函数为0时,为必败态;否则为必胜态。

  • SG定理

    若干个组合游戏可以组成一个新的组合游戏。以nim游戏为例,将每一堆石子看作一个组合游戏,N个组合游戏构成nim游戏。其中我们知道,对于每一堆石子,其SG函数恰好为其石子数量。

    SG定理: SG(G)=SG(G1)⊕SG(G2)⊕SG(G3)….SG(Gn)SG(G) = SG(G_1) \oplus SG(G_2) \oplus SG(G_3) …. SG(G_n)SG(G) = SG(G_1) \oplus SG(G_2) \oplus SG(G_3) …. SG(G_n)

    恰好是符合nim游戏。也可以将每一个子组合游戏进行的阶段类比每一堆石子剩余的石子数量后进行理解。

例题

  • HDU1524 A Chess Game

    SG函数裸题

  • HDU1536 S-Nim

    nim游戏,但是能取的石子数量必须在给定的集合S内。

    能取石子的数量是一个给定的集合,因此无法用普通的nim游戏结论求解。

    先把问题分解成一个子组合游戏:一堆数量为n的石子的SG函数。

    取数的集合的大小 1≤k≤1001 \leq k \leq 1001 \leq k \leq 100 ,即SG函数是不会超过100的。(最差情况下把0,1,2,3…都填满,则100一定是空的)。又 0≤hi≤100000 \leq h_i \leq 100000 \leq h_i \leq 10000 ,故我们直接可以通过递推,打出SG函数表。

    接下来考虑原问题,相当于若干个组合游戏的和,求出异或和即可。

  • HDU3032 Nim or not Nim\?

    Lasker’s Nim. n堆石子,每次可以:

    • 从一堆中取走一些石子
    • 把一堆石子分成两堆非空堆

    同样的,我们先对每一堆进行考虑。假设当前石子数为x

    • 对于操作1,能转移到任意小于x的石子数,对答案的贡献为 SG(i),0≤i\<xSG(i), 0 \leq i \< xSG(i), 0 \leq i \< x
    • 对于操作2,能转移到两堆分别为a和b的石子,并且满足a+b = x,因此相当于a和b两个组合游戏的和,即对答案的贡献为 SG(a)⊕SG(b)SG(a) \oplus SG(b)SG(a) \oplus SG(b)

    因此, SG(x)\=mex{SG(i)(0≤i\<x),SG(a)⊕SG(b)(a+b\=x)}SG(x) = mex\left\{ SG(i)(0\leq i\<x),SG(a)\oplus SG(b)(a+b=x) \right\}SG(x) = mex\left\{ SG(i)(0\leq i\<x),SG(a)\oplus SG(b)(a+b=x) \right\}

    这样单个的子组合游戏的SG函数就求解完了,最后把所有SG值异或起来就得到其和。

    但是这样求解SG函数是平方级的,但是打个表可以发现:

    SG( 4k+1)= 4k+1 SG( 4k+2)= 4k+2 SG( 4k+3)= 4k+4 SG( 4k+4)= 4k+3

  • HDU2509 Be the Winner

    一堆苹果,每堆排成一行,可以从中拿走若干个连续的苹果,两端的苹果自动分成两堆(可以只拿头尾若干个)。取走最后一个苹果的输。

    和上面的题相似,只取头尾,就是普通的nim游戏。但是存在一个操作拿中间的苹果,变成两堆。即 a+b\<xa+b\<xa+b\<x 。数据范围不是很大,可以直接暴力打表求出SG函数。

    需要注意的是,这是一个反常游戏。所以我们SG函数得出必胜态和必败态的结论需要进行修改,同反常nim游戏。即,

    • SG全为1时,SG异或和为0时必胜,否则必败
    • SG不全为1时,SG异或和为0时必败,否则必胜。
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    #define MAXN 205
    
    int sg[MAXN];
    int book[MAXN];
    
    int main() {
    
        ios::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
    
        sg[0] = 0;
        for(int i=1;i<MAXN;++i) {
    
            memset(book,0,sizeof(book));
            for(int j=0;j<i;++j) book[j] = 1;
    
            for(int a=1;a<i;++a)
                for(int b=1;b<i;++b)
                    if(a+b<i) {
                        book[sg[a]^sg[b]] = 1;
                    }
            for(int j=0;j<MAXN;++j)
                if(book[j]==0) {
                    sg[i] = j; break;
                }
        }
    
        int N;
        while(cin >> N) {
            int ans = 0, maxx = 0;
            for(int i=1;i<=N;++i) {
                int x; cin >> x; ans ^= sg[x]; maxx = max(maxx,sg[x]);
            }
            if( (maxx==1&&ans==0) || (maxx>1&&ans>0) ) cout << "Yes\n";
            else cout << "No\n";
        }
        return 0;
    }
    
  • [HNOI2007]分裂游戏

    0\~n-1堆石子,你可以选择第i堆减少一个石子,在选择j,k,满足 i\<j\leq ki\<j\leq k ,使得第j堆和第k堆均+1,不能操作的输。求解必胜的先手方案(字典序最小)和方案数。

    考虑把每一个石子作为一个组合游戏。设距离第n-1堆的距离为x,则我们可以开始求解SG(x)。

    SG(x) = mex\left\{ SG(y)\oplus SG(z) ,x >y \geq z\right\}SG(x) = mex\left\{ SG(y)\oplus SG(z) ,x >y \geq z\right\}

    打个表出来即可。

    同时,同一堆石子中,若石子数为偶数,则对答案的贡献为0,否则为SG(x)。因为全部异或起来自然会抵消大量,这样就可以加速计算。

    接下来就是如果计算先手必胜策略,暴力枚举,判断操作后的SG值是否为0即可。

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    #define MAXN 205
    
    int sg[MAXN];
    int book[MAXN];
    int a[MAXN];
    
    int main() {
    
        ios::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
    
        sg[0] = 0;
        for(int i=1;i<MAXN;++i) {
    
            memset(book,0,sizeof(book));
            for(int j=0;j<i;++j) book[j] = 1;
    
            for(int a=0;a<i;++a)
                for(int b=0;b<i;++b)
                        book[sg[a]^sg[b]] = 1;
    
            for(int j=0;j<MAXN;++j)
                if(book[j]==0) {
                    sg[i] = j; break;
                }
        }
    
        int T; cin >> T;
        while(T--) {
            int N; cin >> N; int SG = 0;
            for(int i=1;i<=N;++i) {
                cin >> a[i];
                a[i] = a[i]%2==1 ? sg[N-i] : 0;
                SG ^= a[i];
            }
    
            int ans = 0;
            if(SG==0) {
                cout << "-1 -1 -1\n0\n"; continue;
            }
            for(int i=1;i<=N;++i)
                for(int j=i+1;j<=N;++j)
                    for(int k=j;k<=N;++k) {
                        int temp = SG^sg[N-i]^sg[N-j]^sg[N-k];
                        if(temp==0) {++ans;}
                    }
            bool flag = true;
            for(int i=1;i<=N&&flag;++i)
                for(int j=i+1;j<=N&&flag;++j)
                    for(int k=j;k<=N&&flag;++k) {
                        int temp = SG^sg[N-i]^sg[N-j]^sg[N-k];
                        if(temp==0) {cout << i-1 << " " << j-1 << " " << k-1 << "\n"; flag = false;}
                    }
            cout << ans << "\n";
        }
        return 0;
    }
    
  • AtCoder AGC017 D – Game on Tree

    先看看最基础的版本

    每次我们可以删掉任意一条边,如果有一个连通块没有与地面连接,则同时删掉整个连通块

    如图,如果所有图均为链,那么这个游戏本质上就是普通的nim游戏。

    对于树的部分,我们可以考虑把每个子树化为等价的树链,最后把所有树都变成链,则最后就会转移到nim游戏

    对于nim游戏,SG值恰好表示石子堆中的石子数量

    对于叶节点:SG = 0,即等价于0个石子

    对于叶节点的父亲节点:若有x个子节点,则相当于有x堆石子,且每堆石子数均为1,那么 SG = \oplus (SG(v)+1)SG = \oplus (SG(v)+1) ,这样得到的SG值就可以把当前节点转化为一个有SG个石子的堆

    那么对于所有的节点,其子节点的SG值均代表了每一堆的石子数量,并多了其连向自己的一条边,即SG+1个石子。那么我们把所有子节点的SG+1异或,就可以得到当前节点的SG值。

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    #define MAXN 200005
    struct edge {
        int v,next;
    } G[MAXN<<1];
    int head[MAXN], tot = 0;
    int N;
    
    inline void add(int u,int v) {
        G[++tot].v = v; G[tot].next = head[u]; head[u] = tot;
    }
    
    int sg[MAXN];
    void dfs(int u,int fa) {
        sg[u] = 0;
        for(int i=head[u];i;i=G[i].next) {
            int v = G[i].v; if(v==fa) continue;
            dfs(v,u); sg[u] ^= sg[v] + 1;
        }
    }
    
    int main() {
    
        ios::sync_with_stdio(0);
        cin >> N;
        for(int i=1;i<N;++i) {
            int u,v; cin >> u >> v; add(u,v); add(v,u);
        }
    
        dfs(1,0);
        if(sg[1] > 0) cout << "Alice";
        else cout << "Bob";
        return 0;
    }
    
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇