arrays - 如何处理这个组合学和博弈论问题？

Question

问题

给定一个大小为N的整数序列S ，两个玩家用这个序列进行最佳游戏，游戏规则如下：

• 玩家交替轮流。
• 在每一轮中，当前玩家必须选择当前序列 S 中的一个或多个元素，使得所有选择的元素的值相同，并将这些元素从 S 中删除。
• 当玩家无法选择任何东西时（序列 S 已经为空），该玩家输掉游戏。

我们必须找出第一个玩家在第一回合中获胜的步数。如果该特定序列没有获胜的动作并且第一个玩家总是输掉游戏，我们必须简单地输出零。

例如，如果序列是1 2 2 2，那么第一个玩家在第一轮中获胜的步数将为 3，因为删除三个“二”中的任何两个将确保第一个玩家获胜。

我的观察

我认为首先我们必须存储独特元素的数量，然后是每个元素的频率，然后我们必须将序列简化为一个特定的方向，确保第一个玩家获胜，然后我们必须简单地计算使用组合学移动以达到该方向。我观察到，如果所有元素的频率相等，那么如果唯一元素的数量是奇数，那么第一个玩家将在一个动作中获胜，并且每次唯一元素的数量是偶数时都会输掉。但是在频率不相等的情况下，我无法概括这种情况。

感谢所有帮助。

标签： arrayscombinatoricsgame-theory