dp

一些笔者最近做过的 dp 好（？）题。

题解 TBD。

题解 TBD。

不太常规的树上背包？

首先考虑点分治，转化为对每个点 $i$，求出若根 $r$ 到 $i$ 的路径必须选的答案。

发现对于点 $i$ 的答案可以分成两部分：$i$ 到 $r$ 的路径上的左兄弟的子树以及 $i$ 的儿子的子树，和 $i$ 到 $r$ 的路径上的右兄弟的子树。将这两个背包进行卷积，由于只用算单点值，对于每个点可以 $O(k)$ 算出。

问题在于如何快速求出这两个背包。我们发现前者是出栈 dfs 序的一个前缀，后者是入栈 dfs 序的一个后缀。两者求法类似，以前者为例：按照出栈 dfs 序从前往后扫，当前扫到点 $s$，若选 $s$，则可以根据 $s-1$ 处的值转移；若不选 $s$，则 $s$ 的子树都不能选，可以根据 $s-siz_s$ 处的值转移。

两部分的时间复杂度均为 $O(nk)$，加上点分治后总时间复杂度为 $O(nk\log n)$。

比较简单的一个题。

假设已经知道了每个点的度数，考虑如果判断可能的最大匹配是多少。

显然最大值是两侧度数非零点的数量的 $\min$。最小值考虑使用 hall 定理，最大匹配为 $\min\{n-|S|+|N(S)|\}$。不难发现一定是取左边度数最小的一些点作为 $|S|$，右边度数最大的一些点作为 $|N(S)|$，给定的 $|S|$ 与 $|N(S)|$ 可行当且仅当 $|S|$ 内部点的度数之和 $\leq |N(S)|$ 内部点的度数之和（因为可以有重边）。直接对两侧做 dp 即可，$dp_{i,j,k,u,w}$ 表示考虑了前 $i$ 个点，度数之和为 $j$，钦定选了 $k$ 个点，这 $k$ 个点度数之和为 $u$，前 $i$ 个点中一共有 $w$ 个度数非零的点。时间复杂度 $O(n^6)$。

DAG 容斥在非集合幂级数上的应用。

不难发现一个集合可行当且仅当她是一个 SCC。考虑使用类似 SCC 子图计数的 DAG 容斥。选定若干入度为 $0$ 的 SCC，显然所在区间不交。首尾与两个 SCC 之间可能会连出一些边，一个 SCC 所在区间的内部也可能会连出一些边。

我们设 $dp_{l,r,l',r'}$ 表示用了 $[l,r]$ 内的点，$l,r$ 必须选，点构成 SCC，并且选的每个点的 $[a_i,b_i]$ 构成的区间都在 $[l',r']$ 内，此时的方案数。辅助数组 $dp'_{l,r,l',r'}$ 定义类似，只是不保证所有点构成一个 SCC，而是由若干入度为 $0$ 的 SCC 拼接而成（不一定首尾相接），每有一个就乘上一个容斥系数 $-1$，相邻 SCC 之间可以夹着一些东西，$l$ 与 $r$ 所在 SCC 必然没有入度。

直接实现时间复杂度为 $O(n^6)$，但是这样做有一个问题：没有考虑一个 SCC 向其所在区间内部的更小的 SCC 连边。为了消除这类边的影响，我们引入一个函数 $f$ 满足：

按照区间从小到大扫，可以 $O(n^4)$ 或 $O(n^3)$ 算出 $f$，这里不是时间复杂度瓶颈。

改变一下 $dp$ 与 $dp'$ 数组的定义：选择一个合法点集 $S$ 时，其对答案的贡献从 $1$ 改为对于所有 $S$ 内标号相邻的点 $u,v$（一共有 $|S|-1$ 对），$f_{u+1,v-1}$ 之积。改完之后我们发现仍然可以以同样的方法计算这两个 dp 数组的值。对于一个 SCC 内标号相邻的两点 $u,v$，该 SCC 可以向 $[u+1,v-1]$ 内的点连边，其总贡献就是上面的那个式子，永远为 $1$。

比较常规，dp 基本功题，不过好像爆标了？（没看题解，不知道题解是什么做法）

第一问是 BJWC 倒数第二场 T1，相信大家稍微想想都会做。

我们发现我们第一问的 slope trick 优化 dp 的流程相当于是解决如下问题：维护一个集合 $S$，初始为空。按 $b_i$ 从小到大排好序后，从前往后扫，每次先执行 $b_i$ 步若 $S$ 不为空则从 $S$ 中选择一个数并将其减 $1$，减到 $0$ 后就扔出集合。然后将 $a_i$ 加入集合。最后还可以再执行任意多步上述减 $1$ 操作。$f(a,b,k)$ 即为删去 $k$ 个数最少需要多少步。显然每次贪心地让最小的数减 $1$ 是最优的。

当确定 $a$ 时没有一个简洁形式的答案表示 $f(a,b,k)$。于是我们考虑直接将贪心过程压进 dp：依旧从前往后扫，每往集合中加入一个数时钦定其是否会被扔掉。我们需要贪心地去钦定：若当前加入的数不小于集合中一个未被钦定的数，则这个数必须不能被钦定；若当前加入的数小于集合中的一个被钦定的数，则这个数必须被钦定。否则会重复计算。于是我们设计出如下状态：$dp_{i,j,k,u,w}$ 表示考虑了前 $i$ 个数，钦定了 $j$ 个，当前被钦定的数之和为 $k$，最大的为 $u$，未被钦定的最小的数为 $w$。转移时枚举当前 $a_i$，枚举其是否被钦定，时间复杂度为 $O(n^3V^4)$，使用前缀和优化可做到 $O(n^3V^3)$。

upd：感觉可以做到 $O(n^3V^2)$，不过只是口胡，没有写，不知道有没有假。

题目比较简单。

首先考虑将 $q$ 划分成 $k$ 个上升子段，然后将每个上升子段打乱得到原排列 $p$。我们考虑怎样才是合法的。对于一个确定的 $p$ 我们有如下贪心过程：若 $k=1$ 则将排列排序并退出，否则取出其前 $n-k+1$ 个数并排序，找到其最小的前缀满足其中所有数在 $p$ 中出现的位置也是一个前缀，取出这个前缀作为第一段并递归到 $k-1$。

考虑 dp：令 $dp_{i,j}$ 表示使用了 $q$ 中的前 $i$ 个数，划分成了 $j$ 段的答案。这样做我们发现 $dp_{i,j}$ 会对之后的数有限制。具体地，如果 $q$ 中第 $u$ 段结尾的数为 $end_u$，那么要求 $p$ 在 $[i+1,n-k+u]$ 中的数全部 $>end_u$（否则与前面所述的贪心过程矛盾）。我们发现若当前剩余段的长度不必全都是 $1$（即 $n-k+j>i+1$），则下一段（第 $j+1$ 段）结尾的数必然大于第 $j$ 段结尾的数。也就是说，$end_u$ 单调递增，因此只用考虑第 $j$ 段带来的限制。我们枚举下一个 $q$ 上的单增段，设其长度为 $len$，共 $x$ 个数比 $end_u$ 小。若 $x=0$，则其贡献为长度为 $len$ 且【不存在前缀是排列】的排列个数，预处理即可；若 $x>0$，则贡献非零当且仅当 $x=1$ 且当前段为 $[i+1,n-k+j]$，其贡献就是一个阶乘。

笔者快退役了，估计续不了了