SG 函数

大部分的公平组合游戏都可以转化为有向图游戏。

有向无环图棋子游戏

在一个有向无环图中没只有一个起点，上面有一个棋子，两个玩家按照有向图轮流来推棋子，直到不能继续走。

---

$mex$运算

$mex(S)$为不属于S集合中的最小非负整数，

例如，$mex(\{0,1,2\}) = 3,mex(\{1,2\}) = 0$。

---

$SG$函数

设状态节点$x$有$k$个后继状态节点$y_1,y_2,...,y_k$，

若果说当前状态 $SG$值 不是 $0$ ，呢么其子状态中一定有一个状态的 $SG$值 是 $0$ ，也就是说处于当前状态的人必胜，因为其一定能导向其对手的必败态（ $SG$值 是 $0$）。

若果说当前状态 $SG$值 是 $0$ ，呢么其子状态中一定没有有一个状态的 $SG$值 是 $0$ ，也就是说处于当前状态的人必败，因为其一定会导向其对手的必胜态（ $SG$值 不是 $0$）。

---

$SG$定理

由$n$个有向图游戏组合的游戏，设起点分别为$s_1,s_2,s_3, ... , s_n$,当$SG(s_1) \oplus SG(s_2) \oplus SG(s_3) \oplus ... \oplus SG(s_n) \neq 0$时，先手必胜，反之必败。

 

vector<int> vec[N] ;
int f[N] ;
int sg(int x){
    if(f[x] != -1) return f[x] ;
    set<int> se ;
    for(auto e : vec[x]){//统计子结点中的sg值
        se.insert(sg(e)) ;
    }
    for(int i = 0 ; ; ++ i){//计算当前的SG函数值
        if(!se.count(i)) return f[x] = i ;
    }
}
void solve(){
    cin >> n >> m >> k;
    int u, v, w ;
    for(int i = 1; i <= m ; ++ i){
        cin >> u >> v ;
        vec[u].push_back(v) ;
    }
    memset(f, -1, sizeof f) ;
    int x ;
    for(int i = 1; i <= k ; ++ i){
        cin >> x ;
        ans ^= sg(x) ;
    }
    if(ans){
        cout << "win" << endl ;
    }else{
        cout << "lose" << endl ;
    }
}

---

集合型 $Nim$ 游戏

给定两个 $m$ 个整数构成的集合 $a_i$ ，给定 $n$ 对石子的数量分别是 $b_i$ 。两个玩家轮流操作，每次操作可以从任意一堆石子中拿去石子，但是拿去石子的数量一定是集合 $a_i$ 中的一个数，最后无法进行操作就的人失败。

int sg(int x){
    if(f[x] != -1) return f[x] ;
    set<int> se ;
    for(int i = 1 ; i <= m ; ++ i){
        if(x >= a[i]) se.insert(sg(x-a[i])) ;
        else break ;
    }
    for(int i = 0 ; ; ++ i){
        if(!se.count(i)) return f[x] = i ;
    }
}
void solve(){
    cin >> m ;
    for(int i = 1; i <= m ; ++ i) cin >> a[i] ;
    sort(a + 1, a + 1 + m) ;
    memset(f, -1, sizeof f) ;
    int x ;
    cin >> n ;
    for(int i = 1; i <= n ; ++ i){
        cin >> x ;
        ans ^= sg(x) ;
    }
    if(ans){
        cout << "Yes" << endl ;
    }else{
        cout << "No" << endl ;
    }
}

---

剪纸游戏

给定一张 $N×M$

的矩形网格纸，两名玩家轮流行动。

在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。

首先剪出 $1×1$ 的格纸的玩家获胜。

两名玩家都采取最优策略行动，求先手是否能获胜。

提示：开始时只有一张纸可以进行裁剪，随着游戏进行，纸张被裁剪成 $2,3,…$

更多张，可选择进行裁剪的纸张就会越来越多。

int f[M][M] ;
int sg(int x,int y){
    if(f[x][y] != -1) return f[x][y] ;
    set<int> se ;
    for(int i = 2 ; i <= x - 2 ; ++ i){
        se.insert(sg(x-i,y) ^ sg(i,y)) ;
    }
    for(int i = 2 ; i <= y - 2 ; ++ i){
        se.insert(sg(x,y-i)^ sg(x,i)) ;
    }
    for(int i = 0 ; ; ++ i){
        if(!se.count(i)) return f[x][y] = i ;
    }
}
void solve(){
    ans = 0 ;
    ans = sg(n,m) ;
    if(ans){
        cout << "WIN" << endl ;
    }else{
        cout << "LOSE" << endl ;
    }
}
signed main(){
    IOS ;
    memset(f, -1, sizeof f) ;
    while(cin >> n >> m){
        solve() ;
    }
    return 0;
 
}