博弈论题目

思路：

由于我们只关心总和能否被 3 整除，我们可以将stones[i] 按照模 3 的结果分为 3 组，即 0、1 和 2。

博弈论

c++代码

/**
博弈论：
默认alice先手

由于我们只关心总和能否被 3 整除，我们可以将stones[i] 按照模 3 的结果分为 3 组，即 0、1 和 2。

**/
class Solution {
public:

    //序列为:11212121212....
    bool choneSolution(map<int,int> count,vector<int>& stones){  //先手选择选择余数为1的情况
        if(!count[1]) return false;  //没有余数为1的数,直接返回失败
        int length = 0;  //去掉的数最多可以形成的长度

        count[1] -= 1;  //首先第一步选择1

        //能够获得得的最长合法序列
        length = min(count[1],count[2]) * 2 + count[0] + 1;

        if(count[1]>count[2]) length++;   //最后还能加上一个1

        //alic获胜的条件：合法序列的长度为奇数，并且还有石子可以选
        if(length % 2 == 1 && length < stones.size()) return true;

        return false; 
    }

    //序列为:221212121212....
    bool chtwoSolution(map<int,int> count,vector<int>& stones){  //先手选择选择余数为1的情况
        if(!count[2]) return false;  //没有余数为2的数,直接返回失败
        int length = 0;  //去掉的数最多可以形成的长度

        count[2] -= 1;  //首先第一步选择1

        length = min(count[1],count[2]) * 2 + count[0] + 1;

        if(count[2]>count[1]) length++;   //最后还能加上一个2

        //alic获胜的条件：合法序列的长度为奇数，并且还有石子可以选
        if(length % 2 == 1 && length < stones.size()) return true;

        return false; 
    }

    bool stoneGameIX(vector<int>& stones) {
        map<int,int> count;
        //先算出所有数模3的值是多少
        for(int i = 0;i < stones.size();++i){
            if(!count.count(stones[i] % 3)) count[stones[i] % 3] = 1;
            else count[stones[i] % 3] += 1;
        }

        //判断alice先手选择余数为1或者选择余数为2的情况下能够获胜
        return choneSolution(count,stones) || chtwoSolution(count,stones);
    }
};