日记

不想在这里~~~

今天被驱逐至 3 号机房，吃满了 3 号机房的 debuff。

Binary Knapsack# Link to

其实之前做过类似的题。

把 $[x_i,y_i]$ 这个物品塞到 st[x[i]] 这个大根堆里去，总共 $O(\log W)$ 个大根堆。从小到大枚举 $W$ 的每一位。如果说 $W$ 第 $i$ 位是 $0$，就说明可以取偶数个 st[x[i]] 里的元素。我们先不取，把 st[i] 里的每两个相邻的数合并到 st[i + 1] 里去。如果是 $1$ 就说明可以取奇数个，从 $st[i]$ 里取出堆顶加进 ans，就变成偶数的情况了。

Prefix Covering# Link to

我们考虑 $k$ 固定的情况。显然这玩意需要 trie。我们把 trie 建出来并添加一些虚点，使这颗 trie 满足除叶子节点以外的点都有两个子节点。（实现的时候不用添加，因为默认就是 $0$，它的属性正好是虚点的属性）

那么这个问题就变成了，给定一个点集 $S$，求把 $S$ 里的某些点染黑，使得没有从根节点到任意叶子的不经过黑点的路径，求出方案数。设 $dp_u$ 表示 $u$ 这颗子树的方案数。

点集 $S$ 哪里来？
结合题意有：

• 不能是虚点
• 必须是一个串的结尾点

考虑转移：

• $u$ 是叶子：
• • $u \not \in S$，显然有 $dp_u = 0$。
• • $u \in S$，显然有 $dp_u = 1$。
• $u$ 不是叶子：
• • $u \not \in S$，显然有 $dp_u = dp_l \times dp_r$，因为它自己不能被染色，所以只能让子节点被染色。
• • $u \in S$，显然有 $dp_u = dp_l \times dp_r + 2^{c_u - 1}$，就是在不能染色的基础上加上自己染色，剩下的随便的情况数。

一些符号的解释：

• $l,r$：分别表示左儿子和右儿子。
• $c_u$：表示 $u$ 的子树里（包含 $u$）有多少个点属于 $S$。

然后考虑加入一个字符串如何搞。设它在 $u$ 结尾。那么显然只有 $rt \to u$ 这条路径上的点会被更新，暴力更新就行，复杂度 $O(\sum_{i = 1}^{n}|S_i|)$

后日谈 # Link to 后日谈

没啥可谈的。