题目链接

浮木博弈

题目描述

Alice 和 Bob 进行一个博弈游戏。有 堆物品，第 堆有 个。双方轮流操作，Alice 先手。

每次操作，玩家必须从编号最小的非空堆中取走任意正整数个物品。

取走最后一个物品的玩家获胜。假设双方都采取最优策略，判断谁会获胜。

解题思路

这是一个公平组合游戏 (Impartial Game)，但由于规则的特殊限制，我们不能直接套用 SG 函数或 Nim 游戏的结论。我们需要从游戏规则本身出发，分析双方的最优策略。

游戏的核心在于，玩家的操作被严格限制在当前编号最小的非空堆上。这使得游戏进程是线性的，从第 1 堆依次进行到第 堆。

关键洞察

让我们分析当轮到某个玩家操作，且当前堆为第 堆时的情况：

  1. 如果当前堆 的物品数量为 1： 玩家别无选择，只能取走这 1 个物品。这堆被清空，轮到对手面对第 堆。在这种情况下，玩家的决策是固定的，会导致回合权的正常交替。

  2. 如果当前堆 的物品数量大于 1： 这时玩家拥有了战略选择。

    • 选择 A: 取走全部 个物品。这堆被清空，轮到对手面对第 堆。
    • 选择 B: 取走 个物品，堆里还剩 1 个。接下来轮到对手，对手必须从第 堆取走这最后 1 个物品。然后，下一回合将由最初的玩家面对第 堆。

    通过选择 B，当前玩家可以花费一个回合（自己取 个）和对手的一个回合（对手取最后 1 个），来确保下一个新堆（第 堆）仍然由自己先手。这意味着，只要一个玩家在非最后一堆（即第 堆，其中 ）上遇到一个数量大于 1 的情况，他就可以“锁定”先手权，将这种优势一直传递下去，直到最后一堆。

    当游戏进行到最后一堆（第 堆）时，轮到谁，谁就可以取走所有物品并直接获胜。

获胜策略

结合以上分析，获胜策略变得明朗：

  • 第一个在非最后一堆（）遇到物品数大于 1 的玩家，拥有必胜策略。他可以通过不断执行上述的“选择 B”，确保自己始终是进入下一个新堆的玩家，最终在第 堆轮到自己时获胜。

因此，整个游戏可以简化为：

  1. 从第一堆开始，模拟回合的交替。
  2. Alice 先手。我们用一个变量记录当前轮到谁。
  3. 遍历 ：
    • 如果 ，说明当前玩家必须取走它，回合权交给对方。
    • 如果 ，说明当前玩家找到了一个可以“锁定”胜局的堆。该玩家获胜，游戏分析结束。
  4. 如果遍历完前 堆，它们全都是 1，那么胜负就由最后一堆决定。此时的回合权已经经过了 次交替。
    • 如果 是偶数（即 是奇数），轮到 Alice 面对最后一堆，Alice 胜。
    • 如果 是奇数（即 是偶数），轮到 Bob 面对最后一堆，Bob 胜。

这个过程等价于寻找第一个 的堆，然后根据其下标 的奇偶性来判断轮到谁。

算法流程

  1. 初始化 is_alice_turn = true。
  2. 遍历堆 从 到 ：
    • 如果 piles[i] > 1，则根据 is_alice_turn 的值判断胜者并结束。
    • 如果 piles[i] == 1，则切换回合权：is_alice_turn = !is_alice_turn。
  3. 如果循环正常结束（说明前 堆都为 1），则根据循环结束后的 is_alice_turn 的值判断胜者。

代码

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    using namespace std;
    int n;
    cin >> n;
    vector<int> a(n);
    bool alice_wins = false;
    bool game_decided = false;
    bool is_alice_turn = true;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i) {
        if (i == n - 1) { // 最后一堆
            if (is_alice_turn) {
                alice_wins = true;
            } else {
                alice_wins = false;
            }
            game_decided = true;
            break;
        }

        if (a[i] > 1) {
            if (is_alice_turn) {
                alice_wins = true;
            } else {
                alice_wins = false;
            }
            game_decided = true;
            break;
        } else { // a[i] == 1
            is_alice_turn = !is_alice_turn;
        }
    }

    if (alice_wins) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        boolean is_alice_turn = true;

        for (int i = 0; i < n - 1; i++) {
            if (a[i] > 1) {
                break; 
            }
            // 如果 a[i] == 1, 交换回合
            is_alice_turn = !is_alice_turn;
        }
        
        if (is_alice_turn) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    is_alice_turn = True
    
    # 遍历到倒数第二堆
    for i in range(n - 1):
        if a[i] > 1:
            break
        # 如果 a[i] == 1, 交换回合
        is_alice_turn = not is_alice_turn
    
    if is_alice_turn:
        print("Alice")
    else:
        print("Bob")

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 博弈论、思维
  • 时间复杂度: 对于每个测试用例，我们最多遍历一次数组，所以时间复杂度是 。总时间复杂度为 。
  • 空间复杂度: 需要存储输入的 个整数，空间复杂度为 。