3

谜底是：

一行中有 n 个硬币，硬币有不同的价值。两名玩家轮流从线的一端拿一枚硬币，直到没有硬币为止。钱多的玩家获胜。如果 n 是偶数，是否有任何 hacky 算法可以决定第一个玩家在 O(1) 内存和 O(n) 时间内是赢还是输？

我已经用动态编程解决了这个问题，但我不知道hacky算法是什么。搜索后，我从这里找到了解决方案：

def firstWillWinEven(self, values):
    """
    odd_s: sum of values at odd position
    even_s: sum of values at even position
    if odd_s == even_s, the first mover cannot win if the other player mimics the first player
    if odd_s > even_s, the first mover chooses the odd position values, and FORCE the other player choose the even
    position values. The strategy and outcome are similar when even_s > odd_s.
    """
    odd_s = 0
    even_s = 0
    for i in xrange(len(values)):
        if i%2 == 0:
            even_s += values[i]
        else:
            odd_s += values[i]

    return odd_s != even_s

虽然我可以理解 if odd_s != even_s，第一人总是会赢，但我就是无法理解这种情况odd_s == even_s。如果 ，如何证明没有获胜策略odd_s == even_s？

4

1 回答 1

0

原来我误解了解决方案。这是完整的解决方案：

def firstWillWin(self, values):
    """
    :param values: a list of integers
    :return: a boolean which equals to True if the first player will win
    """
    n = len(values)
    if n%2 == 0 and self.firstWillWinEven(values):
        return True

    return self.firstWillWinNormalCase(values)

如果odd_s != even_s那么第一人肯定会赢。如果odd_s == even_s，我们不知道谁会赢，所以退回到firstWillWinNormalCase。

于 2015-07-04T13:13:45.160 回答