做题记录

CF1671E

注意到不同子树间的答案独立。那么对于 \(u\) 为根的子树，其贡献应该是其左儿子乘右儿子再乘它自己的方案。那么由于它自己的方案只与 \(f(l),f(r)\) 有关，所以当其操作后能使答案贡献增加，当且仅当 \(f(l) \ne f(r)\)。为了排除儿子自身的影响，我们将 \(f(x)\) 视为 \(x\) 为根子树中遍历得到字典序最小的序列。那么只要 \(f(l) \ne f(r)\)，\(u\) 就会对答案贡献 \(2\) 倍，因为可以不交换。时间复杂度 \(O(n 2^n)\)。

CF1485F

考虑暴力 DP。定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个数，\(\sum\limits_{k=1}^{i} a_k =j\) 时的方案数。对于情况 \(1\)，我们有：\(f_{i,j}=f_{i-1,j-b_i}\)。对于情况 \(2\)，我们有：\(f_{i,b_i}=\sum\limits_{j=-V}^{V} f_{i-1,b_i-j}\)。其中 \(V\) 为值域，我们可以将 \(V\) 视作 \(\inf\)。那么有：\(f_{i,b_i}=\sum\limits_{j=-V}^{V} f_{i-1,j}\)。

整理一下，有：\(f_{i,j+b_i}=f_{i-1,j},f_{i,b_i}=\sum\limits_{j=-V}^{V} f_{i-1,j}\)。不难发现，我们每次相当于将第二维同时增加了 \(b_i\)，而后面是个全局 \(sum\)。这里有个很典的 trick，我们记录 \(tag\) 表示整体右移的大小。那么这次转移较初始状态右移了 \(tag=\sum\limits_{j=1}^{i} b_j\)。我们还原到初始状态，就有：\(f_{i,j}=f_{i-1,j},f_{i,b_i-tag}=sum\)。记 \(s_i=\sum\limits_{j=1}^{i} b_j\)，有：\(f_{i,-s_{i-1}}=sum\)。然后就做完了，由于第一个转移相当于直接赋值，所以只需要维护 \(f_{i,-s_{i-1}}=sum\)，记录全局 \(sum\) 即可。答案也为全局 \(sum\)。时间复杂度 \(O(n \log n)\)。