「eJOI2022」Game With Numbers 题解

算法思路

本题使用博弈论和分治搜索来解决双方最优策略下的数字移除游戏。核心思想是通过递归搜索所有可能的游戏路径，并按照玩家类型选择最小化或最大化最终剩余数字的和。

关键观察

1. 游戏规则分析

• 两位玩家轮流操作，玩家1（奇数轮）希望最终和最小，玩家2（偶数轮）希望最终和最大
• 每轮必须选择两种操作之一：
  • 移除所有能被 $b_i$ 整除的数字
  • 移除所有不能被 $b_i$ 整除的数字

2. 状态空间分析

• 每轮操作都会将当前数字集合分成两个不相交的子集
• 游戏状态可以用当前数字范围 $[first, last)$ 和当前轮数 $bcur$ 表示

代码解析

核心数据结构

#define MAXN 20000
#define MAXM 30
using lli = long long;

lli a[MAXN], b[MAXM], *bend;  // 数字数组和除数数组

分治搜索函数

lli dfs(lli *first, lli *last, const lli *bcur) {
    static lli tmp[MAXN];  // 临时数组用于分区

    // 基准情况1：没有剩余数字
    if (first == last)
        return 0LL;

    // 基准情况2：所有轮次已完成
    if (bcur == bend)
        return accumulate(first, last, 0LL);

    // 分区操作：将数字按能否被当前除数整除分开
    lli *lend = tmp, *rfirst = tmp + (last - first);
    for (lli *it = first; it != last; ++it)
        (*it % *bcur ? *lend++ : *--rfirst) = *it;

    // 复制回原数组保持顺序
    for (lli *it = first; it != last; ++it)
        *it = tmp[it - first];

    // 根据玩家类型选择最优策略
    if ((bcur - b) & 1LL)  // 玩家2（最大化）
        return max(dfs(first, first + (lend - tmp), bcur + 1), 
                   dfs(first + (rfirst - tmp), last, bcur + 1));
    else  // 玩家1（最小化）
        return min(dfs(first, first + (lend - tmp), bcur + 1), 
                   dfs(first + (rfirst - tmp), last, bcur + 1));
}

优化剪枝

// 当轮数足够多时，可以清空所有数字
if (m >= (__lg(n) + 1U) << 1U) {
    printf("0");
    return 0;
}

算法正确性

博弈策略保证

• 玩家1（最小化方）：在每轮选择两种操作中结果较小的那个
• 玩家2（最大化方）：在每轮选择两种操作中结果较大的那个
• 递归边界：当没有数字或所有轮次完成时返回确定值

分区操作正确性

• 使用临时数组 tmp 将数字分为两个集合：
  • 左半部分：不能被 $b_i$ 整除的数字
  • 右半部分：能被 $b_i$ 整除的数字
• 保持相对顺序以便后续处理

复杂度分析

理论复杂度

• 最坏情况：$O(2^m \cdot n)$，每轮产生两个分支
• 实际优化：通过 $m \geq 2(\log n + 1)$ 的剪枝避免指数爆炸

可行性分析

• $n \leq 2 \times 10^4$，$m \leq 30$（代码中限制）
• 在合理范围内，搜索树不会过深

关键技巧

1. 原地分区：使用双指针技术在临时数组中分区，避免频繁内存分配
2. 玩家类型判断：通过 (bcur - b) & 1 判断当前玩家
3. 递归状态压缩：仅传递指针范围，不复制整个数组
4. 提前终止：当轮数足够多时直接返回0