leetcode 294 翻转游戏II c++

Question

class Solution {
public:
    bool canWin(string s) {
        vector<int> dec;
        s.push_back('-');
        int cnt = 0, dpSize = 0;
        /* 分解原状态至多个不可分解的子态 */
        for(char c: s){
            if(c == '+') ++cnt;
            else{
                dec.push_back(cnt);
                dpSize = max(dpSize, cnt);
                cnt = 0;
            }
        }
        if(dpSize <= 1) return false;

        vector<int> dp(dpSize + 1, 0);

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

        return accumulate(begin(dec), end(dec), int(), [&](auto a, auto b){return a ^ dp[b];});
    }    
};

作者：梦璃夜·天星
链接：https://leetcode.cn/problems/flip-game-ii/solutions/906239/c-sprague-grundy-acmbo-yi-lun-xiang-guan-1ddj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

借鉴 leetcode题解的代码,但是 在k循环 求g值部分,为何可确定 g值 的范围在i/2之内？ 对照 SG定理 没想出合适的解释.

Answer 1

leetcode：294.翻转游戏

leetcode：294.翻转游戏_leetcode294-CSDN博客 文章浏览阅读255次。这道题不是问 “1p是否会怎么选都会赢”，而是 “如果1p每次都选特别的两个+，最终他会不会赢”。所以 canWin 这个函数的意思是 “在当前这种状态下，至少有一种选法，能够让他赢”。canWin) 的意思就变成了 “在当前这种状态下，无论怎么选，都不能赢”。所以 1p 要看的是，是否存在这样一种情况，无论 2p 怎么选，都不会赢。canWin)，1p 就可以确定他会赢。题目要求先手必胜的方案，于是思路在于遍历所有的先手可能，对于每一个先手，一路玩下去，看当前先手策略是不是能让先手赢。..._leetcode294 https://blog.csdn.net/zhizhengguan/article/details/126220867

https://www.cnblogs.com/lightwindy/p/9666939.html