AGC012E Camel and Oases

题意

有一个数轴上有 \(n\) 个点。一开始有一个参数 \(v\)，你可以进行任意次移动，直到 \(v = 0\)：

• 移动到一个距离当前点不超过 \(v\) 的点，\(v\) 不变。
• 移动到任何一个点，使得 \(v \gets \lfloor\dfrac{v}{2}\rfloor\)。

现在对于每个起点，问从这个点出发可不可以遍历所有位置。

\(1 \le n, v \le 2\times10^5, |x| \le 10^9\)。注意 \(v\) 的范围。

题解

和 262144 Revisited 有相似的思路，下次再想不到就跑圈了。

首先转化问题。特定的 \(v\) 只有 \(\log v_0\) 种，对于每一种 \(v\)。假设一开始位置为 \(i\)，则可以遍历一个包含位置 \(i\) 的连续段；且在每一层中，所有这些段拼起来刚好是全集。那么遍历所有点相当于在每一层找一个段，使得所有被选择的段并起来是全集。题目所问也就是钦定了第 \(0\) 层选择的段。

考虑状态压缩。设 \(f_S\) 表示用 \(S\) 里面的层能拼出最长的前缀，\(g_S\) 表示最长后缀，转移枚举最后/最前的段的层数即可。那么对于每个第 \(0\) 层的段，只需要 \(\Theta(v_0)\) 枚举左边的集合检查左右两边是否能覆盖到即可。由于第一层的段不能超过 \(\log_2 v_0\) 个（否则一定无解），所以复杂度是 \(\Theta(v_0\log v_0+n)\)。