L2174. 「FJOI2016」神秘数 - 完整题解

题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，有 $m$ 个询问。对于每个询问 $[l, r]$，考虑由 $a_l, a_{l+1}, \dots, a_r$ 构成的可重复数字集合，求这个集合的神秘数——即最小的不能被该集合的某个子集的和表示的正整数。

数据范围：

$n, m \leq 10^5$

$\sum a_i \leq 10^9$

核心思路分析

1. 问题转化 我们需要快速求出区间 $[l, r]$ 中数字组成集合的神秘数。直接枚举所有子集显然不可行。

2. 关键观察 设当前已经能够表示出 $[1, R]$ 中的所有整数，考虑下一步：

情况1：如果集合中存在某个数 $x \leq R+1$

那么我们可以用 $x$ 加上 $[1, R]$ 中的某些数，表示出 $[x, x+R]$

由于 $x \leq R+1$，区间 $[1, R]$ 和 $[x, x+R]$ 会合并成 $[1, x+R]$

新的表示范围变为 $[1, R']$，其中 $R' = R + x$

情况2：如果集合中所有数都 $> R+1$

那么 $R+1$ 无法被表示

答案就是 $R+1$

3. 贪心算法 扩展上面的思路：不是只加一个 $\leq R+1$ 的数，而是一次性加入所有 $\leq R+1$ 的数。

算法流程：

text 初始化 R = 0 循环： 设 S = 区间内所有 ≤ (R+1) 的数的和 如果 S > R： R = S # 能表示的范围扩展到 [1, S] 否则： 输出 R+1 作为答案 结束循环 正确性证明：

设当前能表示 $[1, R]$，令 $X = R+1$

查询所有 $\leq X$ 的数的和 $S$

如果 $S = R$：说明没有新的数可以加入，$X$ 无法表示

如果 $S > R$：设新增的数为 $v_1, v_2, \dots, v_k$（都 $\leq X$）

对于每个 $v_i$，由于 $v_i \leq X = R+1$，且已能表示 $[1, R]$

可以表示 $[v_i, v_i + R]$，这些区间会合并成 $[1, S]$

因此更新后能表示 $[1, S]$

4. 复杂度分析 设最终答案为 $ans$：

每次循环中，新的 $R$ 至少是原来的 $R$ 加上某个 $\leq R+1$ 的数

实际上 $R$ 的增长速度很快（类似倍增）

循环次数为 $O(\log(\sum a_i))$，通常不超过 40 次