「Summary」2022-08-02 做题记录

我太菜了T_T

2022-08-02

$\mathbb{CF1209E2}$

状压忘得要完了。

一个直接的想法是只取最大值最大的前 $n$ 列，可以把这个矩阵缩小到 $n^2$ 的级别。
考虑状压，用 $f_{i, j}$ 表示第 $i$ 列选择状态为 $j$ 的数字产生的贡献，$dp_{i, j}$ 表示前 $i$ 列选择状态为 $j$ 的数字产生的贡献。
则 $dp_{i, j} = \max\{dp_{i - 1, j \oplus k} + f_{i,k}\}$ ，其中 $k$ 是枚举的 $j$ 的子集。
最终贡献为 $dp_{n, 2^m - 1}$ 。

$\mathbb{CF1208F}$

这个就是传说中的 $SOS \ dp$！

然而我不会，那就学一手。
卧槽，牛逼，放个原作者的链接 SOS Dynamic Programming [Tutorial]。
这个问题可以如此考虑，分开看每一位，如果能选 $1$ 就尽量选 $1$ ，判断的标准需要用 $SOS \ dp$ 预处理，即 $dp_{i, 0/1}$ 分别表示与值是 $i$ 的超集的两个数的下标的最大值和和次大值，此时枚举 $d_i$ ，判断是否可以以 $d_i$ 作为最左边的数，使得 $dp_{\complement x, 0} > i$ 。

$\mathbb{Problem \ J. \ CSGO}$

题目名字很上头

看到有绝对值很难受，试着把它拆开，你会发现其实相当于给其中一个的系数赋 $1$，另外一个赋 $-1$，对于每一件武器，可以直接枚举是哪一个能力的系数为 $-1 / 1$ ，做一个类似于 $SOS \ dp$ 的转移，具体地说，设 $dp_{0/1, sta}$，表示：是主 / 副武器，此时系数为 $1$ 的能力值组成的集合是 $sta$ ，的权值最大值，那么答案就是 $\max\{ dp_{0, sta} + dp_{1, 2^k - sta}\}$，这样复杂度是 $\Theta(n 2^k)$ 的，很可以过。
为什么是对呢，其实不难想到，如果存在两个武器的能力系数赋反，那么此时的贡献一定是负的，则一定不比正确的赋值方法优秀，也就不会成为答案。

$\mathbb{HDU - 3001}$

CJG 🤡 DJ nb!

这不很显然吗，首先定义 $dp_{i, j, pos}$ 表示走过的集合为 $i$ ，走过两遍的集合为 $j$ ，现在停在 $pos$ 。很好转啊，枚举上一层的终点就好了。
20 min later…
写完了，$MLE$ 了，🤡，被卡空间了！！！
转成 3 进制，$WA \times 3$ ，啥玩意？怎么还是不对，请来兔兔 $DJ$ 帮忙调， 1 min later… “你为啥给 int 赋了个 1e18 的初值啊？”
🤡🤡🤡🤡🤡🤡🤡🤡

$\mathbb{Sandy \ and \ Nuts}$

COLLAPSED

要甚么时候才能停止做这些分类讨论题？
一个朴素的想法是设 $dp_{u, sta}$ 表示以 $u$ 为根，此时子树里点的集合是 $sta$ 。
在不考虑限制的情况下，转移方程是 $dp_{u, sta} = \sum_{v \in substa} dp_{v, substa} \times dp_{u, sta \oplus substa \oplus 2^u}$ 。
然后看到限制，有连边和限制 lca 两种。
这个必须恶臭的讨论：

对于连边的限制，如果 $x, y$ 其中有一个等于 $u$ ，则统计 $substa$ 中与 $u$ 有连边的 $i$ 的数量，如果大于了 $1$ ，则不合法；如果 $x, y$ 均不等于 $u$，当 $x, y$ 不同时存在或不存在在 $substa$ 中时，则不合法。

对于 lca 的限制，如果 $(a, b, c)$ 中 $c = u$，且 $a, b$ 同时存在于 $subsat$ 中，则不合法；如果 $c$ 存在于 $substa$ 中但是 $a, b$ 有一者不存在 $substa$ 中，则不合法。

写完一个样例都不过 🤡。
发现算重了，怎么办？？？思考算重的原因是在枚举 $lson$ 时能枚举到 $rson$ ，而反过来枚举 $rson$ 时也可以枚举到 $lson$ 。这两棵子树的地位是等价的，必须有手段区分，可以强制指定一个 $v$ 使其只存在于 $lson$ 中，这样问题就解决了。