当前位置：首页 > news >正文

题目记录（before 暑假 ver.）

news 2026/5/11 21:13:47

T1. P15649

考虑令 \(dp_{u,l}\) 表示在节点 \(u\)，重链长度为 \(l\) 的概率，然后考虑树上背包。

首先先把 \(l = \sum l_i\) 给预处理出来，这个可以直接用树上背包。然后考虑枚举重儿子 \(v\)，那么我们可以考虑使用前后缀拼接来算，复杂度是 \(\mathrm O(n^3)\)。

此时我们发现背包合并其实类似于多项式乘法，所以这提示我们可以考虑用类似于多项式除法的东西来把 \(v\) 的贡献扣掉。这种东西就叫做删除背包。

所以此时复杂度就是 \(\mathrm O(n^2)\)。算答案是容易的。

T2. P15650

考虑一个子串 \(h\) 长什么样的时候才会有贡献：

是 \(s\) 的前缀。
存在 \(i\) 满足 \(h_{[1,i]} = s_{[1,i]}\) 且 \(h_{i + 1} = 0,s_{i + 1} = 1\)。

那么如果 \(t\) 的一个子串 \(h\) 满足 \(h\) 是 \(s\) 的前缀，此时 \(h\) 就有两种可能的贡献：

\(t\) 中 \(h\) 下一位是 \(0\)，\(s\) 中 \(h\) 的下一位是 \(1\)，此时后面每次加一个数都会加一贡献。
否则贡献为 \(1\)。

此时发现我们把问题转化为了前缀匹配。此时考虑令 \(dp_{i,j,k,0/1}\) 表示当前匹配到了 KMP 自动机的 \(i\) 号节点上，有 \(j\) 次第一种贡献，当前贡献总数是 \(k\)，是否匹配出一个完整的 \(s\)。注意到第二维有用的个数是在 \(\mathrm O(\sqrt k)\) 这个级别的，所以可以直接暴力跳 \(nxt\) 数组来 dp。

T3.qoj4892

考虑对于一组 \(a,b,c\)，假设这三个数的中位数为 \(v\)，那么对于任意两个数 \(i,j \in \{a,b,c\}\) 都有：

如果 \(i > v\) 则 \(j \le v\)。
如果 \(i < v\) 则 \(j \ge v\)。

考虑令 \(x_{i,t}\) 表示 \([v_i \ge t]\)。那么我们就可以把上面的两个限制条件转化为一个 \(2-SAT\) 模型，即：

若 \(v_{i,v+1}\) 为真，那么 \(v_{j,v+1}\) 为假。
若 \(v_{i,v}\) 为假，那么 \(v_{j,v}\) 为真。

同时需要注意如果 \(v_{i,v+1}\) 为真，那么 \(v_{i,v}\) 肯定也为真。

此时只需要看这个 \(2-SAT\) 是否有解即可。

T4.qoj2570

令 \(f_i\) 表示以 \(i\) 为结尾的 \(LIS\) 数量，\(g_i\) 表示以 \(i\) 开头的 \(LIS\) 数量，\(m = \max f_i\)。那么我们注意到只有 \(f_i + g_i = m + 1\) 的点我们才值得考虑，我们令这些点为关键点。

那么考虑建出以下的最小割模型：

\((i,i + n,1)\)。
\((S,i,1)\) 且 \(f_i = 1\)。
\((i + n,T,1)\) 且 \(f_i = m\)。
\((i + n,j,1)\) 且 \(i < j,a_i < a_j,f_j = f_i + 1\)。

此时考虑这个最小割模型在干什么：每一次删掉一个长度为 \(m\) 的 \(LIS\)，要求每一次删除的 \(LIS\) 互不相交，请问最多能删多少次。

现在考虑把前面的图简化为只有 \((i,j)\) 且 \(i < j,a_i < a_j,f_j = f_i + 1\) 这一种边。此时考虑按照 \(f\) 的值来分层，具体的令 \(i\) 在第 \(f_i\) 层。那么我们就可以注意到所有的边一定是从上一层连到下一层的。且对于第 \(k\) 层的点，将其按照下标从小到大排序后，每一层的 \(a\) 都是单调不降的。

然后我们又能发现对于所有在第 \(k\) 层的点 \(i\)，其向 \(k+1\) 层的点的连边一定为一个区间 \([l_i,r_i]\)。且对于所有的 \(i < j\) 且在同一层的 \(i,j\) 均有 \(l_i \le l_j,r_i \le r_j\)。而总是存在一种删除方法，使得所有的第 \(i\) 条路径 \(p_i\) 和第 \(j\) 条路径 \(p_j\) 满足 \(\forall k\in [1,m],p_{i,k} < p_{j,k}\)。