我们需要通过最少的操作次数，在多重集合 $S$ 中插入目标数字 $n$。每次操作可以选择一个子集 $T$，删除 $T$ 中的所有元素，然后插入 $\text{mex}(T)$。

关键观察：要得到 $n$，必须有一次操作中 $T$ 包含 $0,1,\dots,n-1$ 且不包含 $n$。

算法思路

核心思想

从高位到低位（$n-1$ 到 $0$）处理，计算需要"生成"多少次数字。

变量说明

• cnt：表示当前需要生成的目标数字数量（从高位传递到低位）
• ans：初始化为 $2^n$，然后减去不需要的操作

算法步骤

1. 初始化 ans = 1 << n（最大可能操作次数）
2. 从 $i = n-1$ 到 $0$ 倒序处理：
   • 从 ans 中减去 $\min(cnt, a[i]) \times 2^i$
   • 更新 cnt += max(cnt - a[i], 0)

代码详解

void solve() {
    int n;
    std::cin >> n;
    std::vector<i64> a(n);
    
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    i64 ans = 1ll << n;  // 初始化为 2^n
    i64 cnt = 1;         // 初始需要生成 n 这个数字
    
    for (int i = n - 1; i >= 0; i--) {
        // 减去当前位可以节省的操作次数
        ans -= std::min(cnt, a[i]) << i;
        // 更新需要生成的数量
        cnt += std::max(cnt - a[i], 0ll);
    }
    
    std::cout << ans << "\n";
}

算法正确性证明

为什么倒序处理？

• 要生成数字 $k$，需要 $0$ 到 $k-1$ 都存在
• 从高到低处理可以正确传递依赖关系

状态转移理解

• min(cnt, a[i])：当前数字 $i$ 能覆盖的需求数量
• cnt - a[i]：当前数字 $i$ 无法满足的需求数量，需要继续向前传递
• cnt += max(cnt - a[i], 0)：累积需要生成的数量

复杂度分析

• 时间复杂度：$O(n)$，每个数字处理一次
• 空间复杂度：$O(n)$，存储输入数组