公平组合游戏

• OI Wiki: https://oi-wiki.org/math/game-theory/impartial-game/

题目	难度
$294. 翻转游戏 II	中等	Sprague-Grundy 定理

Sprague-Grundy 定理

这一定理被称作 Sprague-Grundy 定理(Sprague-Grundy Theorem), 简称 SG 定理。

• https://leetcode.cn/problems/flip-game-ii/solution/c-sprague-grundy-acmbo-yi-lun-xiang-guan-1ddj/
• https://zhuanlan.zhihu.com/p/20611132
• https://edwiv.com/wp-content/uploads/2019/08/ACM-ICPC_Templates_201805.pdf

$294. 翻转游戏 II

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution294 {
    public boolean canWin(String currentState) {
        List<Integer> dec = new ArrayList<>();
        currentState = currentState + "s";
        int cnt = 0;
        int dpSize = 0;
        // 分解原状态至多个不可分解的子态
        for (char c : currentState.toCharArray()) {
            if (c == '+') {
                cnt++;
            } else {
                dec.add(cnt);
                dpSize = Math.max(dpSize, cnt);
                cnt = 0;
            }
        }
        if (dpSize <= 1) {
            return false;
        }

        int[] dp = new int[dpSize + 1];

        // 枚举所有不可细分的子状态（0,1 时为 0 已经返回 false，从 2 开始遍历）
        for (int i = 2; i <= dpSize; i++) {
            // 子状态不可以拆分，那么子状态的值等于所有下一个状态的集合外的最小非负整数
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < i / 2; j++) {
                // 每种翻转后，形成的次态可以分解成两种状态
                // 可分解的状态（g值）等于各分解子状态（g值）的异或和
                set.add(dp[j] ^ dp[i - j - 2]);
            }
            // 找到最小的不在集合中的数字，就是本状态的g值
            for (int k = 0; k <= i / 2; k++) {
                if (set.contains(k)) {
                    continue;
                } else {
                    dp[i] = k;
                    break;
                }
            }
        }

        int a = 0;
        for (int b : dec) {
            a ^= dp[b];
        }
        return a != 0;
    }
}

（全文完）