思维链

1. 如何将子集 DP 的 $O(3^n)$ 优化到 $O(2^n \textrm{poly}(n))$ ？

考虑每次不枚举子集，而是枚举关键元转移：具体地，枚举一个元素，然后从除去这个元素即补集转移过来。

这两题需要分组，使得最大化

sum=0

的集合数量。发现

O(3^n)

是简单的。考虑枚举关键元，发现我们似乎还要记录一维表示最后一个集合的

sum

。这样变为

O(2^nnV)

，比朴素还要劣。

我们把分组看作用一些隔板间隔开集合（把集合拍在序列上），我们既可以最大化集合的数量，也可以最大化隔板的数量。我们只考虑

sum=0

的集合。发现我们可以放一个隔板当且仅当前缀

sum=0

。直接 DP 即可。

这启发我们能否将子集转换为关键元，并在本身状态（或者只加 $\textrm{poly}(n)$ ）的状态本身的性质去转移。

AT_abc432_f
P7718 「EZEC-10」Equalization

2. 贡献尽量在小（简短）的地方转移，即尽量将贡献记在一个集中的地方，而非记在连续或散列的地方

可能有些抽象。就是说：如果一个状态可以以一个点出现的形式被记录，那就不要将其放在一段连续的或者散列的状态中记录。

1. B3609. 【NOI2025模拟】计树

考场上记录的状态为：从后向前考虑，至到当前点时：后方缺儿子的点数量：分为能加儿子的点，和强制加儿子的点，后方恰好没有父亲的点的数量。这样就变为了

O(n^4)

的。另一个问题 A 也有存在，但是这里不论，放于注释。但是为什么要分两个状态来考虑呢？

可以这样：我们把当前点是否要加两个儿子放在了添加第二个儿子的时候决策。 但是你发现说：添加第二个儿子时，第二个儿子没有提供任何有效的信息来辅助这个决策，即发现这个第二个儿子是谁无关当前点是否选择第二个儿子。

至于为什么无关，因为你排序后（按序考虑）已经为转移提供了一个完序关系，你不再需要考虑前后的偏序了，所以对于这种只关心偏序的，就不应该把其记录在状态里面，而是应该当前就决策好（钦定好），不要把后效性带到后面去。

也即是说：如果一个状态可以以一个点出现的形式被决策，那就不要将其放在一段连续的状态带着一起转移。

2. B3604. 【NOIP2025模拟】账本

考场上差点没想出来。

贪心时简单的，从前往后如果某个位置小于

0

则翻转，使得一个后缀加。

发现我们的决策点是在每个 $<0$ 的位置。这显然是 $O(n)$ 的。 如果决策点互不影响时，可以拿数据结构维护。但是现在前面的决策点修改后，会使得将后面的决策点也发生改变。

考虑我们是否可以将每次的决策的贡献缩在一个点上面？

我们发现：首先每次决策具有偏序性，即后面一个点的决策值一定比前面要小。想到偏序性就要想到极值元，即最大元/最小元。 我们注意到最小元抬升完毕后，后面就不可能有元素继续抬升，否则当前就不是最小元。

我们注意到贡献只与前缀值最小元有关。这个题就做完了。

但是如何归纳这个问题？就是如果一串点的贡献是将后缀影响的时候，我们需要观察能否将贡献挂在（转移到，写作成）最后一个点/极值元的贡献。即把一串点的贡献归到一个点的贡献。

3. 树上维护一级邻域信息，考虑把贡献分为儿子和父亲，修改时把父亲一起修改，查询时，只查询儿子的贡献和，和父亲的贡献

P9194 [USACO23OPEN] Triples of Cows P

未删除为黑点，否则为白点。

黑点有贡献，设其可以不跨过另一个黑点所能到达的黑点数量为

k

，则其贡献为

k^2-k

。

考虑从全部黑点开始，不断删除黑点。（这里用到了正难则反（双边考虑）的思想，因为要用到的并查集只支持合并，不支持删除。）

把一个极大的白色连通块及其挂着的黑色点合并在一起考虑。

4. 类 ARC 的序列题 1：元素删除，考虑终态，并找一些必要性把终态不对的排除掉

n\le 3\times 10^5

。

考虑终态，有终态为这些序列及其前缀：

1,1,1\\ 1,2,3\\ 2,1,2\\ 2,3,2\\ 3,2,1\\ 3,3,3,\cdots

终态可以考虑能否将一段区间完全删除掉。

考虑枚举一些必要性。一段区间删除的必要性第一是区间和对

4

取模为

0

。你发现说前 $5$ 种情况已经可以被排除掉了。

当推出一个必要性时，要分析什么情况下有情况满足这个必要性之后还不合法。然后我们将终态分为这些情况，并讨论出来只有最后这种全是

3

的情况没有被判掉。

然后就对最后这种情况进行必要性分析。发现其不删掉当且仅当周围不够

1

和

2

来删掉。

每个

1

可以删掉一个

3

。每个

2

可以删掉两个

3

。证明其是必要的。可以用构造证明。考虑归纳。注意归纳之后就可以变为贪心删除。最后证明一下即可。

注意讨论这里的时候要把区间和对 $4$ 取模为 $0$ 这个先验必要性考虑到。

文章操作

1. 如何将子集 DP 的 $O(3^n)$ 优化到 $O(2^n \textrm{poly}(n))$ ？

2. 贡献尽量在小（简短）的地方转移，即尽量将贡献记在一个集中的地方，而非记在连续或散列的地方

1. B3609. 【NOI2025模拟】计树

2. B3604. 【NOIP2025模拟】账本

3. 树上维护一级邻域信息，考虑把贡献分为儿子和父亲，修改时把父亲一起修改，查询时，只查询儿子的贡献和，和父亲的贡献

4. 类 ARC 的序列题 1：元素删除，考虑终态，并找一些必要性把终态不对的排除掉

相关推荐

评论

思维链

文章操作

1. 如何将子集 DP 的 O(3n)O(3^n)O(3n) 优化到 O(2npoly(n))O(2^n \textrm{poly}(n))O(2npoly(n))？

2. 贡献尽量在小（简短）的地方转移，即尽量将贡献记在一个集中的地方，而非记在连续或散列的地方

1. B3609. 【NOI2025模拟】计树

2. B3604. 【NOIP2025模拟】账本

3. 树上维护一级邻域信息，考虑把贡献分为儿子和父亲，修改时把父亲一起修改，查询时，只查询儿子的贡献和，和父亲的贡献

4. 类 ARC 的序列题 1：元素删除，考虑终态，并找一些必要性把终态不对的排除掉

相关推荐

评论

1. 如何将子集 DP 的 $O(3^n)$ 优化到 $O(2^n \textrm{poly}(n))$ ？