题目链接

最多取半的巴什博弈

题目描述

给定 个石子，Alice 和 Bob 轮流操作，Alice 先手。

每次操作，设当前石子总数为 ：

  1. 若 ，则当前玩家立即输掉游戏。
  2. 当前玩家必须从石堆中取走 个石子，其中 满足 。

假设双方都采取最优策略，判断谁会获胜。

解题思路

这是一个经典的公平组合游戏，其胜负状态可以通过寻找必胜态（N-position）和必败态（P-position）来解决。

  • 必败态 (P-position)：处于该状态的玩家，无论如何操作，其后继状态都将是必胜态。
  • 必胜态 (N-position)：处于该状态的玩家，至少存在一种操作，使其后继状态是必败态。

根据规则，状态 是一个必败态。我们可以从小到大推导其他状态的胜负性：

  • ：可取 个，剩余 个。状态 是必败态，故 是必胜态 (N)。
  • ：可取 个，剩余 个。状态 是必胜态，任何操作都转移到必胜态，故 是必败态 (P)。
  • ：可取 个，剩余 个。状态 是必败态，故 是必胜态 (N)。
  • ：可取 。取 时，剩余 个。状态 是必败态，故 是必胜态 (N)。
  • ：可取 ，剩余为 或 。状态 都是必胜态，故 是必败态 (P)。

我们列出小数据范围内的必败态：

结论与证明

观察发现，正整数的必败态 满足递推关系 ，其中 。

这个递推公式可以解得通项公式。令 ，可知 是一个公比为 的等比数列。

首项为 。因此 ，即 。

换言之，一个正整数 是必败态，当且仅当 可以被表示为 的形式（对于某个 ）。

Alice 先手，如果初始石子数 是必胜态，则 Alice 胜；如果是必败态，则 Bob 胜。

算法上，我们判断 是否能被 整除，以及 是否为 的幂。判断一个正整数 是否为 的幂，可以通过位运算 (x & (x - 1)) == 0 来实现。

代码

#include <iostream>

int main() {
    using namespace std;
    long long n;
    cin >> n;
    long long x = n + 1;
    bool bob_wins = false;
    if (x % 3 == 0) {
        x /= 3;
        // 检查 x 是否是 2 的幂
        if (x > 0 && (x & (x - 1)) == 0) {
            bob_wins = true;
        }
    }
    if (bob_wins) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long x = n + 1;
        boolean bob_wins = false;
        if (x % 3 == 0) {
            x /= 3;
            // 检查 x 是否是 2 的幂
            if (x > 0 && (x & (x - 1)) == 0) {
                bob_wins = true;
            }
        }
        
        if (bob_wins) {
            System.out.println("Bob");
        } else {
            System.out.println("Alice");
        }
    }
}

import sys

def main():
    n = int(sys.stdin.readline())
    x = n + 1
    bob_wins = False
    if x % 3 == 0:
        x //= 3
        # 检查 x 是否是 2 的幂
        if x > 0 and (x & (x - 1)) == 0:
            bob_wins = True
    
    if bob_wins:
        print("Bob")
    else:
        print("Alice")

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 博弈论、位运算
  • 时间复杂度: ，仅进行几次算术和位运算判断。
  • 空间复杂度: ，仅使用常数个变量。