题解「夜雀 collecting」

幽云蓝 · 2021-08-06 17:56:23 · 题解

这里是八云蓝&cxy的官方题解~

注：按位与用 | 表示，按位或用 \& 表示，按位异或用 \oplus 表示。

一档不简单但是很套路的部分分。首先我们应该发掘一些信息&性质：

1. 如果拥有 \ge1 个某种食材，那么将其丢弃到只剩一个肯定更优。

我们可以用一个二进制位来表示出有/无某种食材，那么根据性质 2，容易想到用一个 x 位的二进制数来表示出一个状态，代表拥有哪些食材。根据性质 1，可以想到这样的一个二进制数能表示出某次采集之后背包里装了哪些食材。那么记状态 f_{i,j} 为第 i 次采集后是否能够达到食材状态 j，能达到就是 1，否则为 0。每一次采集也可以压缩成两个数 w_i 和 q_i，其中 w_i 代表这次采集到的食材数量，q_i 代表可以采集到的食材状态。得到如下转移：

如果有 f_{i,j}=1，并且令 g(x) 为 x 在二进制下 1 的个数，那么如果有 g(j)+w_{i+1}\le v，那么有 f_{i+1,j|q_{i+1}}=1。并且如果有 f_{i,j}=1，那么有 f_{i+1,j}=1。

在转移结束后，考虑用高维前缀和来模拟丢弃食材的过程。具体来说，记当前转移到第 i 次采集，那么就从大到小枚举 x 位二进制数 j，对于 f_{i,j}，如果存在 2^k 满足 f_{i,j|2^k}=1，那么有 f_{i,j}=1。

最后将所有满足 f_{n,j}=1 的 j 计算其对应价值即可。

注：该部分 written by chenxinyang2006

首先我们可以观察到，对于任意 S，dp_S 必然在某次采集前一直为 0，而某次采集后一直为 1 。我们如果要从这个状态进行丢弃，必然只有在它由 0 变为 1 的状态的丢弃是有意义的，于是我们可以用枚举子集换掉高维前缀和。

接下来我们考虑优化收集食材的过程，如果我们能够快速地找到每次的有效转移 S ，一共的转移次数是 2^x 级别的。

这个部分存在三个限制

实际上第二个限制是最好处理的，我们可以开 x 个桶，把 S 状态存在第 g(S) 个桶里面，每次我们只考虑前 \min(v - w,x) 个桶的 S 进行的转移。

接下来考虑一三限制，这部分似乎比较麻烦，但我们考虑到本题的一个性质：如果 S 可行，那么 S 的任意子集都可行。

那么我们考虑对于有效转移 S，去掉同时在 S 和 q 中存在的位，得到一个新的状态 S' ，容易发现 S' 必然仍满足三个限制，且能转移到相同的位置。

于是我们可以改写一三限制为：

看似多了一条限制，但我们发现，对于所有 S，我们再去枚举 q，这样所有 q 数量的总和是 3^x 级别的。

于是我们可以开一些 \text{vector} ，第 i 个 \text{vector} 存储所有 S，满足 dp_S=1，i\operatorname{and}S=0。

然后我们对于前 \min(v-w,x) 个桶中的每个桶，遍历 \text{vector } q，就可以找到可能可行的 S 。

为什么说可能可行？因为我们并不保证 dp_{i+S} = 0。但在进行此次转移后，显然这个 \text{vector} 中的所有转移都失效了（或者说，无法进行有效转移了），可以全都删去。于是复杂度均摊正确。

当 dp_S 在此次收集食材中可行时，要维护那些 \text{vector}，包括 S 是在丢掉食材时变得可行的情况。

发现上面出现了很多无用的转移。考虑维护一个数组 f，其中 f_i 代表状态 i 是否能得到，然后从第一次采集开始向后计算。显然 f_i 具有单调性——也就是说，对于从第 k 次采集转移到第 k+1 次采集，我们只需要计算哪些 f_i 会从 0 变为 1。我们继续发掘性质：如果 f_j 在一次转移中会从 0 变为 1，那么其所有子集（子集即状态 \alpha 满足 \alpha\&j=j 且 \alpha\neq j）都一定在转移前为 1，或者在这次转移时会从 0 变为 1。考虑一个类似于轮廓线的思路：维护所有状态 j 满足：① j 的所有子集 \alpha 都满足 f_{\alpha}=1；② 所有以 j 为子集的状态 \alpha 都满足 f_{\alpha}=0。接下来称这些状态为关键状态。这些状态一定是最容易达到的，并且根据这些状态的性质（性质①），我们可以迅速的算出在一次转移中，某个关键状态 j 是否会转移为 f_j=1。具体来说，我们有下面的转移：

若当前从第 k 次采集转移到第 k+1 次转移，并且有关键状态 j，那么如果有 g(j\oplus (j\&q_{k+1}))+w_{k+1}\le v，那么就有 f_j=1。

食材数量为 k 时关键状态的最大值等于有 k 种元素的没有包含关系的集合的个数最大值，这个值等于 C(x,x/2)（记 C(A,B) 为从 A 个带标号物品中选 B 个的方案数），其中 / 代表整除。上述算法的复杂度在只考虑转移的情况下即为 O(2^xx+C(x,x/2)\times n)。

考虑细节实现，首先枚举关键状态的时候最好按状态从小到大枚举，因为如果状态 j 在转移中满足了 f_j=1，那么其可能导致一些新的状态加入关键状态集合。显然，加入的状态一定大于状态 j，这样枚举可以避免重复计算状态。并且，我们需要在某些时刻删除一些关键状态。那么我们就可以使用 set 来维护关键状态集合啦。因为 set 的遍历是 O(size) 的，而插入是 log 的，每个状态最多被插入删除一次，所以复杂度为 O(2^x\times \log C(x,x/2)+C(x,x/2)\times n)。

那如何计算哪些状态会被加入关键状态集合呢。考虑高维前缀和的套路，如果一个状态 j，其本身满足不在关键状态集合，并且在某次转移后有 f_j=0，且对于所有满足 2^k\&j>0 的 k 都满足 f_{j\oplus 2^k}=1，那么将其加入关键状态集合。可以通过对于每个集合维护满足上述条件的 k 的数量来完成维护。

综上，我们以 O(2^xx+C(x,x/2)\times n) 的复杂度解决了此题（2^x\times \log C(x,x/2) 必然小于 2^xx）。经过计算，该复杂度为 O(2^xx+\frac{2^x\times n}{\sqrt x})。顺带一提，蓝已经构造数据将其卡到上界啦（但是还是跑的很快）。

其实该题还存在一种 O(2^xx+2^x\times n) 的贪心做法。考虑枚举最终获得的食材集合，记这一目标集合为 T，然后从后往前考虑每次采集，那么对于当前枚举到的第 i 次采集，如果我们进行了这次采集，在这次采集之前我们就必须采到集合 T\oplus(T\&q_i)（否则就不能达到目标集合了），那么能进行这次采集当且仅当 g(T\oplus(T\&q_i))+w_i\leq v。如果能进行这次采集，那么采集就相当于将原目标集合 T 变成 T\oplus(T\&q_i)，容易发现进行采集一定优于不进行采集，于是贪心解决即可。完结撒花~