题解：AT_agc012_e [AGC012E] Camel and Oases

ZM____ML · 2024-12-12 21:38:15 · 题解

感觉是一道很牛牛的题，第一反应是建图跑路，反应过来可以拆成 \log 层维护就会了。

因为每次跳跃操作会将我背包容量的上限 V 变成 \frac{V}{2}，所以不难发现我至多进行 \log V 次跳跃操作，我的容量上限也只会发生 \log V 次变化，所以我们可以考虑对于每一个 V 进行维护。

具体的，我们可以简单递推出当我处在第 i 个绿洲，当前的背包容量上限为 V 时能够通过走路操作到达的最左端点以及最右端点。

同样我们可以处理出来设当前选择的层集合，向左边延申可以到达的最远的位置，同理也可以处理出来向右边延申可以到达的最远的位置，可以简单状压 dp。最终状态合法就是存在一个集合，其补集和本身刚好能够填满两边。

时间复杂度 O((n + v) \log n)。