题解 | #不连续的巴什博弈#

题目链接

不连续的巴什博弈

题目描述

Alice 和 Bob 进行一个博弈游戏。初始有 $n$ 个石子。给定一个包含 $m$ 个正整数的集合 $S = \{s_1, s_2, \dots, s_m\}$ 。

双方轮流操作，Alice 先手。每次操作，玩家从集合 $S$ 中选择一个元素 $s_i$ ，且 $s_i$ 不超过当前石子数。然后从石堆中取走 $s_i$ 个石子。

如果轮到某位玩家时，对于集合 $S$ 中的所有元素 $s_i$ ，都有 $s_i$ 大于当前石子数，那么该玩家无法操作，判负。

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

解题思路

这是一个经典的公平组合游戏，其胜负状态可以通过 Sprague-Grundy 定理来解决。该定理为每个游戏状态分配一个称为 Grundy 数（或 SG 值）的非负整数。

必败态 (P-position)：指当前玩家无论如何操作，都会转移到对手的必胜态。其 SG 值为 $0$ 。
必胜态 (N-position)：指当前玩家至少存在一种操作，可以转移到对手的必败态。其 SG 值大于 $0$ 。

一个状态的 SG 值被定义为其所有后继状态 SG 值的 $\text{mex}$ (Minimum Excluded value，最小不包含值)。 $\text{mex}$ 函数的结果是从一个非负整数集合中找出最小的、未在该集合中出现的非负整数。例如， $\text{mex}\{0, 1, 3, 4\} = 2$ 。

对于本题，一个状态由石子数量 $i$ 唯一确定。我们用 $sg(i)$ 表示有 $i$ 个石子时的 SG 值。根据定义，其后继状态为 $i - s_j$ （其中 $s_j \in S$ 且 $s_j \le i$ ）。因此， $sg(i)$ 的计算公式为： [ sg(i) = \text{mex}{ sg(i - s_j) \mid s_j \in S \land s_j \le i } ]

这是一个典型的动态规划问题。我们可以从小到大计算出 $sg(0), sg(1), \dots, sg(n)$ 。

基础状态： $sg(0) = \text{mex}\{\} = 0$ 。这是一个必败态，因为没有石子时，玩家无法操作。
状态转移：对于 $i > 0$ ，我们首先找到所有后继状态 $\{i - s_j\}$ 的 SG 值，即 $\{sg(i - s_j)\}$ ，然后计算这个集合的 $\text{mex}$ 值，即为 $sg(i)$ 。

最终，我们只需判断初始状态 $sg(n)$ 的值。

如果 $sg(n) > 0$ ，说明初始状态是必胜态，先手 Alice 获胜。
如果 $sg(n) = 0$ ，说明初始状态是必败态，先手 Alice 失败，Bob 获胜。

为了高效计算 $\text{mex}$ ，我们可以用一个布尔数组或集合来记录所有后继状态的 SG 值，然后从小到大查找第一个未出现的值。

代码

cpp
java
python

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

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> s(m);
    for (int i = 0; i < m; ++i) {
        cin >> s[i];
    }

    vector<int> sg(n + 1, 0);
    vector<bool> seen(m + 1);

    for (int i = 1; i <= n; ++i) {
        fill(seen.begin(), seen.end(), false);
        
        for (int move : s) {
            if (i >= move) {
                if (sg[i - move] <= m) {
                    seen[sg[i - move]] = true;
                }
            }
        }
        
        int mex = 0;
        while (mex <= m && seen[mex]) {
            mex++;
        }
        sg[i] = mex;
    }

    if (sg[n] > 0) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] s = new int[m];
        for (int i = 0; i < m; i++) {
            s[i] = sc.nextInt();
        }

        int[] sg = new int[n + 1];
        boolean[] seen = new boolean[m + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(seen, false);
            
            for (int move : s) {
                if (i >= move) {
                    if (sg[i - move] <= m) {
                        seen[sg[i - move]] = true;
                    }
                }
            }

            int mex = 0;
            while (mex <= m && seen[mex]) {
                mex++;
            }
            sg[i] = mex;
        }

        if (sg[n] > 0) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }
}

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    s = list(map(int, sys.stdin.readline().split()))

    sg = [0] * (n + 1)
    
    for i in range(1, n + 1):
        seen = set()
        for move in s:
            if i >= move:
                seen.add(sg[i - move])
        
        mex = 0
        while mex in seen:
            mex += 1
        sg[i] = mex

    if sg[n] > 0:
        print("Alice")
    else:
        print("Bob")

if __name__ == "__main__":
    main()

算法及复杂度

算法: 博弈论, Sprague-Grundy 定理, 动态规划
时间复杂度: $\mathcal{O}(n \cdot m)$ ，其中 $n$ 是石子总数， $m$ 是集合 $S$ 的大小。我们需要计算 $n$ 个状态，每个状态的计算需要遍历集合 $S$ 。
空间复杂度: $\mathcal{O}(n)$ ，用于存储从 $0$ 到 $n$ 的所有状态的 SG 值。