《博弈论》

尼姆博弈:

一:给定n堆石子,每次可以从一堆中取任意数量个,最后一个取完的获胜。

二:给定n堆石子,每次可以从一堆中取最多k个,最后一个取完的获胜。

三:给定n堆石子,每次可以选最多k堆,每堆可以取任意数量个。

Solution:

一:这是最经典的一种尼姆博弈,先手必胜态为所有堆石子数异或后答案不为0.否则为必败态。

二: 对每堆的石子数模上(k + 1),就变成了经典的尼姆博弈类型。

三:这个问题又被称为nimk博弈,我们把每堆石头都表示成二进制,从每个二进制位去考虑。

统计每个二进制位上1的个数,如果满足每个二进制位上1的个数都可以 % (k + 1) = 0.那么先手必败。

反之,先手必胜。

《博弈论》

上一篇:[Leetcode 394]编译解码字符串Decode String


下一篇:Mybatis源码执行的浅读