博弈论 ----- Nim游戏

题目：

结论：

1. 假设有三堆石子{3, 4, 5}, 每堆石子分别有3、4、5个石子
2. 把3、4、5分别转为二进制：011、100、101
3. 对011、100、101取异或(对位相同取0，相异取1)，011^100^101 = 010
4. 若异或结果为0，那么只要改变任意一堆石子的任意数量则异或结果必定会变为非0

最优策略：

• 只要每堆石子数量的二进制数求异或结果不为0，则到自己回合的时候改变其中一堆石子数量让异或结果为0

因为只要在我回合结束后把异或结果变为0，那么对手回合则无论他怎么操作，异或结果必定不为0 —> 在他当前回合一定无法取完所有石子，最后一个回合我赢的局面一定是取完石子后每堆石子数量都为0 —> 异或结果为0。

解决本问题思路：

• 如果双方都采取上面的最优策略
• 根据上面的推导可知：只要先手的那个人最开始面对的那几堆石子二进制数异或为0，那么他一定输，反之他一定赢
• 即只需要判断初始的石堆二进制异或是否为0 <=> 初始的石堆的几堆石子数量异或是否为0(因为一个数的十进制数异或为0 当且仅当 其二进制数异或为0)

   public static boolean solve(int[] A) {
        int res = 0;
        for (int value : A) {
            res ^= value;
        }
        return res != 0;//不为0就会赢
    }

本文地址：https://blog.csdn.net/k909397116/article/details/107898288