清一色的状压？试试暴搜吧

· · 题解

2025/7/11，图炸了，还是用洛谷图床

你见过非官解、思路极简、没有大量剪枝、还没有毒瘤卡常的黑题暴搜吗。

我们照抄 @Ebola 大佬题解里的题目转化：

每次跳跃会让 V 减半，因此最多跳跃 \log V 次。那可以看作一棵 \log V 层的容器，每层有若干条线段。对于第 i 层的一条线段，它所覆盖的点就是按跳跃 i-1 次后的驼峰大小来算，能直接到达的绿洲。

那问题就变成了：在每层选一个线段，将整个区间完全覆盖。其中第一层选择的线段是钦定的（因为要对每个出发点求是否有解）。

（添加了 \KaTeX、空格和句号以满足题解审核要求）

画个图就很直观：

然后考虑暴搜，考虑当前已经填了前 k-1 层，还没有被覆盖的点集为 S。关于这个 S，我们直接用 \operatorname{vector} 套 \operatorname{pair} 来记录，每个 \operatorname{pair} 记录一个第 k 层的线段（参考上图中的方框）。

然后是一个很显然的小剪枝：如果剩下的操作次数（\log V - k）小于第 k 层未被覆盖的线段数，就直接退出。

然后是记搜。我选择直接暴力地上 \operatorname{map}。

就这样。我大概写的是 O(V\log^2V+n\log V)（复杂度 证明不了 在后面）。精细实现 O(V\log V+n\log V)。

提交记录（我代码的变量可能比较迷惑）。

复杂度感性理解

瓶颈在于状态数和记录状态的代价。

要把状态数卡满，必然是不存在可行解的。每一层的待选项的数量卡满，在最后一层炸掉。大概如下图：

如果不记搜，显然是层数的阶乘级别。但记搜下来是 O(2^{\log V})，即 O(V)。因为 V=0 和 V=1 也算一层，所以带最多 4 倍常数。

用 \operatorname{map} 套 \operatorname{vector} 就是 O(\log^2 V) 的。如果哈希并且精细实现 \operatorname{vector} 的转移，应该甚至可以均摊 O(1)（纯口胡）。