题解：P7836 「Wdoi-3」夜雀 collecting

题解摘自做题记录。

分析

数据范围明显得要让我们分开搞。

【Sub2】

应该是暴力。这里有个主体思路，我们完全可以贪心地将当前背包里的食材删掉，直到每种出现过的食材数量刚好为 \(1\)。因为我们保留更多的是没有用的。那么我们就可以用二进制数表示 \(x\) 种食材的出现状态了。

同时，可能存在当前的一个状态 \(s\)，将 \(s\) 与第 \(i\) 个采集点结合时出现了背包装不下，单删掉 \(s\) 中的几个 \(1\) 后能够装下且更优。这启示我们，对于一个 \(s\) 实际上是可能转移到其一个子集会更优。既然都能转到子集了，那么在第 \(i\) 个采集点的时候，记 \(t_i\) 为这个采集点每个食材的出现状态，我们就完全可以用一个与 \(t_i\) 不交的状态 \(s\) 来转移。

我们对于当前能够达到的所有状态 \(s\) 去转移 \(s'\)。如果 \(s'\) 已经被转移过了，那显然是没有必要再转移一次的。那么我们就能保证每个状态最多被转移 \(1\) 次。同时，因为 \(s\) 的所有子集也可以去转移，所以算上枚举子集的复杂度就是 \(O(3^x)\) 的。

这里给个小优化：因为 \(n\) 十分巨大，如果我们对于每个 \(t_i\) 都去枚举它能达到的状态 \(s'\)，最坏是 \(O(2^xn)\) 的，但是根据上一自然段的分析，得知对于相同的 \(t_i\) 是没必要再去遍历一遍的，直接清空就行。具体操作的时候会发现，我们可能一个 \(|s'|+V_i >v\) 了，在这个采集点是无法转移的，而可能会有后面的某个转移点可以转移，但是我们给它清空了。为了避免这种情况，我们可以存一下 \(|s'|\)。

【Sub3】

考虑到，对于一个状态 \(s'\)，如果它可以通过 \(t_i\) 和 \(s\) 得到，当且仅当 \(s'\) 是 \(t_i \cap s\) 的子集。根据 Sub2 分析的第二个自然段，可以进一步得到：当状态 \(s'\) 能被转移到时，需要满足 \(s'\) 的所有子集都能被转移到。那么我们拿一个 set 来记录所有合法的状态，如果一个状态可以得到，我们去推它的一个超集，动态插入所有从不合法变成合法的超集。那么之后任意时间，这个状态都没有用了，可以直接删掉。

现在考虑枚举超集。根据上述的条件，我们得知 \(s'\) 合法的前提是其子集都合法，那么我们枚举超集的时候就只需要枚举所有 \(|S|=|s'|+1\) 的 \(s'\) 的超集，只要 \(S\) 删掉任意一个 \(1\) 得到的集合都合法，那么它就合法了。为什么不需要枚举 \(|S|=|s'|+2\) 的超集？很显然，当 \(|S'|=|s'|+1\) 且 \(S'\) 是 \(S\) 的子集时，如果 \(S'\) 仍不合法，那么 \(S\) 显然不合法。如果 \(S'\) 合法，那么 \(S\) 将在枚举 \(S'\) 的超集时被枚举到。所以这样就是对的。

因为这样我们保证了对于任意时刻，不存在 set 中的两个状态 \(a,b\)，有 \(a\) 是 \(b\) 的子集。所以 set 中最多 \(x\) 个状态。额，分析不来了。复杂度未知，应该不是很大。

代码

你可以自己写。