题解 | #绝对值博弈#

题目链接

绝对值博弈

题目描述

给定一个包含 $N$ 个不同整数的集合 $S$ 。Alice 和 Bob 轮流进行操作，Alice 先手。每次操作，玩家需选择集合 $S$ 中两个不同的整数 $x$ 和 $y$ 。

若 $|x-y|$ 的结果也在集合 $S$ 中，则执行此次操作的玩家立即输掉游戏。
若 $|x-y|$ 的结果不在集合 $S$ 中，则将 $|x-y|$ 添加到集合 $S$ 中，轮到对方操作。

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

解题思路

这是一个典型的公平博弈问题。直接模拟整个游戏过程非常复杂，因此我们需要寻找问题的核心性质或不变量，来简化游戏模型。

寻找不变量 (Invariant)：设 $G$ 是当前集合 $S$ 中所有数字的最大公约数 (GCD)。如果我们从集合中选择两个数 $x$ 和 $y$ ，我们知道 $G$ 一定能整除 $x$ 和 $y$ 。根据数论的基本性质， $G$ 也必然能整除它们的差 $|x-y|$ 。这意味着，当我们计算出一个新的数字 $|x-y|$ 并将其加入集合时，新集合所有数字的 GCD 仍然是 $G$ 。因此，集合中所有数字的最大公约数在整个游戏过程中是一个不变量。
简化游戏模型：既然 GCD ( $G$ ) 是不变的，那么在游戏中出现的所有数字都必须是初始 GCD 的倍数。设初始集合中的最大值为 $M_{max}$ 。任何新产生的数 $|x-y|$ 必然小于 $M_{max}$ 。这启发我们将游戏过程看作是“填空”：初始集合提供了一些 $G$ 的倍数，而游戏的终点是将从 $G$ 到 $M_{max}$ 之间所有 $G$ 的倍数全部“填满”。
确定终局状态：游戏在什么时候结束？当集合 $S$ 对于“取差的绝对值”这个操作变得“封闭”时，游戏结束。此时，对于任意 $x, y \in S$ ， $|x-y|$ 的结果都已经在 $S$ 中，导致当前玩家的任何操作都会直接判负。可以证明，这个最终的“封闭”集合就是 $\{G, 2G, 3G, \dots, kG\}$ ，其中 $k \cdot G = M_{max}$ 。
计算总移动次数：我们已经知道了游戏的初始状态和终局状态，因此可以精确地计算出从开始到结束总共有多少次有效的移动。
- 终局状态的集合大小为 $k = M_{max} / G$ 。
- 初始状态的集合大小为 $n$ 。
- 因此，游戏中总共可以执行的有效移动次数为 $T = (M_{max} / G) - n$ 。
判断胜负：问题被转化成了一个极其简单的 impartial game：总共有 $T$ 个石子，Alice 和 Bob 轮流取一个，取走最后一个石子的人获胜。
- 如果总移动次数 $T$ 是奇数，先手 Alice 会执行第 1, 3, ..., T 步操作。Alice 会执行最后一次操作，因此 Alice 获胜。
- 如果总移动次数 $T$ 是偶数，后手 Bob 会执行第 2, 4, ..., T 步操作。Bob 会执行最后一次操作，因此 Bob 获胜。

算法步骤：

计算初始集合所有数字的最大公约数 $G$ 。
找到初始集合中的最大值 $M_{max}$ 。
计算总移动次数 $T = (M_{max} / G) - n$ 。
根据 $T$ 的奇偶性判断胜负。

代码

cpp
java
python

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

using namespace std;

// 用于计算最大公约数的辅助函数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

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

    if (n == 0) {
        cout << "Bob" << endl;
        return 0;
    }

    long long common_divisor = a[0];
    for (int i = 1; i < n; ++i) {
        common_divisor = gcd(common_divisor, a[i]);
    }

    long long total_moves = (max_val / common_divisor) - n;

    if (total_moves % 2 != 0) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    // 用于计算最大公约数的辅助函数
    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long maxVal = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            if (a[i] > maxVal) {
                maxVal = a[i];
            }
        }

        if (n == 0) {
            System.out.println("Bob");
            return;
        }
        
        long commonDivisor = a[0];
        for (int i = 1; i < n; i++) {
            commonDivisor = gcd(commonDivisor, a[i]);
        }

        long totalMoves = (maxVal / commonDivisor) - n;

        if (totalMoves % 2 != 0) {
            System.out.println("Alice");
        } else {
            System.out.println("Bob");
        }
    }
}

import sys
import math

def gcd_list(numbers):
    if not numbers:
        return 0
    result = numbers[0]
    for i in range(1, len(numbers)):
        result = math.gcd(result, numbers[i])
    return result

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n == 0:
        print("Bob")
        return

    max_val = max(a)
    common_divisor = gcd_list(a)
    
    total_moves = (max_val // common_divisor) - n
    
    if total_moves % 2 != 0:
        print("Alice")
    else:
        print("Bob")

solve()

算法及复杂度

算法: 数论 (最大公约数)
时间复杂度: 我们需要遍历一次数组以找到最大值，时间复杂度为 $\mathcal{O}(N)$ 。接着，我们需要计算 $N$ 个数字的最大公约数，这可以通过迭代计算实现，时间复杂度为 $\mathcal{O}(N \cdot \log(\max(a_i)))$ 。因此，总时间复杂度为 $\mathcal{O}(N \cdot \log(\max(a_i)))$ 。
空间复杂度: 我们需要一个数组来存储 $N$ 个初始数字，因此空间复杂度为 $\mathcal{O}(N)$ 。