2024 北京 - dp

12.12 上午：dp from larryzhong

[AGC058F] Authentic Tree DP

高妙的转化，怎么能想到呢？

把题目中的转成概率上的意义，如果那个分数分母是 $n-1$ 那么答案就是 $1$，等价于随机删边最后都是大小为 $1$ 的连通块的概率。但是现在是 $n$，考虑可以将其转化成点。因为分裂的是两个子树的递归问题，于是我们对于每个边建立一个点，此时总和点数是 $2n-1$ 个。但是！我们只需要在模 $P$ 意义下总点数为 $n$ 就好了！那我们给每个边点下面加上 $P-1$ 个点，总和就是 $n$ 个点了。现在式子就是给模意义下 $n$ 个点赋予一个排列，所有边点都比旁边的点小的概率。

转化的题意后，现在有若干条限制形如 $id_u>id_v$，但是方向不同意，$u,v$ 的祖先关系不确定。于是容斥，对于根向边，分为钦定和删除两种转移，这个是平凡的，时间复杂度 $\mathcal O(n^2)$。

[ARC157F] XY Ladder LCS

看着不是很可做啊！原本想着能不能 dp 套 dp，结果失败了。考虑暴力：令 $f_{i,j,S}$ 表示 $s$ 匹配到 $i$，$t$ 匹配到 $j$，$i,j$ 中间是否交换的状态为 $S$，答案是多少。这里有一个关键结论，最长公共子序列 $\ge \dfrac{2n}{3}$，具体就是每三个肯定有两个匹配。于是 $S$ 我们只要记录 $\dfrac{n}{3}$ 位就好了，时间复杂度 $\mathcal O(n^22^{\frac n 3})$。

CF1434E A Convex Game

细节调了好久，，，，这种题开始还是要想清楚

容易想到单独求出所有序列的 SG 函数然后异或起来，转化成了单个序列的问题。

容易想到一个比较暴力的 dp：令 $f_{i,j}$ 表示最后两次操作分别选择了 $i,j$ 的 SG 函数值，每次转移就是一个后缀的 mex，是可以预处理的，时间复杂度 $\mathcal O(n^2)$。但是状态就已经是 $\mathcal O(n^2)$ 级别的了，而且基本上每个元素就是有数的，试着换个状态。

发现 $f_{i,j}$ 的值域是 $\mathcal O(\sqrt V)$ 范围的（这个同样可以从转移的角度考虑，$m$ 次转移得到的最大 SG 值是 $\mathcal O(\sqrt m)$ 的，记得是一道 AGC 里用到了），所以可以答案状态换维，因为对于一个固定的 $j$，$i$ 越小 $f_{i,j}$ 越小，令 $g_{x,j}$ 表示当 SG 函数值 $\ge x$ 的时候，$i$ 的最小值，转移式为 $g_{j,x}=\min\{i\mid f_{i,j}\ge x\}$，这里又要引进 $f$，再把 $f$ 拆开。$f_{i,j}=\text{mex}\{f_{j,k}\mid a_k\ge2a_j-a_i\}$。

这个 mex 很丑，转成判定性问题。令 $h_{x,j}$ 表示 $f_{j,k}=x$ 的最大 $k$，则 $f_{i,j}=\max\{x\mid\forall t\in[0,x),a_{h_{x,j}}\ge2a_j-a_i\}$，重新套到 $g$ 里就可以得到 $g_{x,j}=\min\{i\mid\forall t\in[0,x),a_i\ge2a_j-a_{h_{x,j}}\}$。这个 $a$ 具有单调性，所以这个 $\forall$ 能套到下标里：$g_{x,j}=\min\{i\mid a_i\ge2a_j-a_{\min_{t\in[0,x)}h_{x,j}}\}$。

现在只要快速计算 $h$ 就好了。每次求出 $g$，$h_{x,i}, i\in [g_{x,j},g_{x+1,j})$ 就可以和 $j$ 取 chkmax，线段树容易做到 $\mathcal O(n\sqrt V\log n)$，如果从大到小枚举 $j$，每个元素只会覆盖一遍，拿个并查集维护可以做到 $\mathcal O(n\sqrt V)$。

CF1519F Chests and Keys

假如我们能承受枚举锁的放置方案的复杂度，试着快速判定合不合法。

看到这个二者选其一的东西，而且是钥匙匹配箱子，想到最小割，图就容易建立了。连接边 $(S, i, a_i)$，$(i',T,b_i)$，如果在箱子 $i$ 上挂上了锁 $j$，连边 $(i,j',c_{i,j})$，答案就是 $\sum a-\text{maxflow}$。注意到我们希望其得不到收益，则 $\text{maxflow}=\sum a$，说明 $S$ 连出去的边一定都是满流的。我们现在只需要用最小的边代价，使得左侧边都满流就好了。令 $f_{i,j,w,s}$ 表示当前考虑到第 $i$ 个箱子是否放置第 $j$ 个锁，此时 $(S,i)$ 的流大小为 $w$，右边和 $T$ 连边的流量信息为 $s$（状压），直接转移就能过。

QOJ6194 Knapsack Problem & CF1290F Making Shapes

前者先咕咕了，后面是一个简单的情况，但是方法是一样的。

首先先对向量排个序，令 $c_i$ 表示 $i$ 的出现次数，则凸包合法的条件就是：$\sum\limits_{a_i<0}-c_ix_i=\sum\limits_{a_i\ge 0}c_ix_i\le m$，$y$ 同理，看着是很不可做的，思考一下这个 $n,|x|,|y|$ 的极小值域给我们带来了什么。对 $c$ 进行数位 dp 的决策，令 $f(d,x_p,x_n,y_p,y_n,l_x,l_y)$ 代表从低到高决策到第 $d$ 位，其中 $x_i\ge 0,x_i<0$ 的分别进位为 $x_p,x_n$，$y$ 同理，$n$ 对 $\sum x, \sum y$ 是否有限制，状态数是能过的，直接记搜就好。

• CodeChef COUNTSEQ2
• CodeChef COMPRBLEGRID
• Topcoder 17778
• GYM103627K
• qoj6194
• qoj7301
• qoj4811