一些 Topcoder DP题 题解

剩下的题有些不可做,可做的也懒得去写了。(咕咕咕

DifferenceSequence

定义对一个序列进行一次操作为

对于任意一个序列,进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串,求所有长度为 $n$ 的串的代表串去重后字典序第 $k$ 小的串。

我们先打个表观察一下会发现,任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 $0$ 组成的串一直循环。再发现 $n \le 26$ 于是可以枚举所有的二进制串,看看它在进入循环后是否已经有被其他二进制串统计过了,如果没有就把最大的串放入答案。

由于一个串进行操作后得到的串只会被便历一遍,使用位运算来操作,这样做的复杂度是 $O(2^{26})$ 。

UniqueMST

看了题解才懂。

我们设 $F(n,k)$ 表示 $n$ 个点的完全图,每个边边权在 $[1,K]$ 内,最终最小生成树唯一且生成树上的边权 $\le k$ 的方案数。

我们考虑枚举一下除开权值是 $k$ 的边时每个最小生成树部分的大小,假设在不加入权值 $=k$ 的边的时候最小生成树的连通块是 $x_1,x_2,\dots ,x_r$ ,且 $x_1$ 是 $1$ 所在的连通块大小,$x_2$ 是除开第一个连通块后最小的点所在的连通块大小 $\dots$ ,同时我们假设这些连通块本身的导出子图已经被确定好了边权,于是它们的贡献就是

然后考虑如何给树之间连边。考虑 prufer 序。根据口罩那题的经典结论,在加入权值等于 $k$ 的边后的树的形态种数是

然后还需要考虑对不在树上剩下的边定权值,这些边权值必须是 $(k,K]$ ,其中 $K$ 是最大的可以用的边权。这部分的贡献是

所以总的式子就是

可以发现 $F(n,k)$ 可以 $dp$ 求得。具体来说,考虑如何计算 $F(n,k)$ ,由于最后那个 $\prod$ 里面有一个 $n$ ,必须再做一次 $pd[x]$ 表示一共是 $n$ 个点,当前有了 $x$ 个点,转移就是加入一个连通块,贡献是显然的。最后再用 $pd[n]$ 推到 $F(n,k)$ 。这样做复杂度是 $O(n^3 k)$ 。

这题 $k$ 竟然是 $10^9$ ,可以想到会不会是插值。考虑把 $F(n,k)$ 看成一个关于 $k$ 的多项式。其实直接求 $n^2$ 个点值做插值就能过了。实际分析出来多项式的次数是 $\binom n 2$ 的。考虑归纳证明。考虑 $r \ge 2$ 的情况,假设 $F(x_i,k-1)$ 次数是 $\binom {x_i} 2$ ,那么实际上次数是

而如果 $r = 1$ ,即贡献是 $F(n,k - 1)$ 的次数。也就是说 $F(n,k) - F(n,k-1)$ 次数是 $\binom{n}2 - 1$ ,做前缀和后次数显然就是 $\binom n 2$ 。

这玩意显然可以 $O(n^4)$ 插值。具体实现可以直接把 $k$ 代进拉格朗日插值式子里面。

CannonballPyramids

还是先打表,会发现前 $3 \times 10^6$ 的数只有不到 $1000$ 的时候才可能需要六个数,大于 $1000$ 的时候一定只需要少于 $6$ 个数。于是我们考虑对于 $x$ 我们找出小于它最大的 $\frac{n(n+1)(2n+1)}{6}$ 然后减掉它,不难发现得到的数一定少于 $2.25\times 10^6$ 左右。于是如果差值不到 $1000$ 则找次大的来做,否则直接输出方案即可。

复杂度看起来很大,本机也很慢,但是交上去跑过去了。。

CardConcat

直接做 $dp$ 可能会有一些复杂度比较高且不太好写的做法。于是可以考虑每个数的贡献。具体来说,我们考虑对于一个数,我们从它前面选择 $j$ 个数,从它后面选择 $k$ 个数,把这些数放到它的后面,于是就会导致它有 $10$ 的这些数字的数位和次方的贡献,这歌贡献是可以通过对前后缀做一个背包处理的。然后还需要算出在剩下的 $n-1-j-k$ 个数随便选择并排列好的方案数。这个也是非常好求的。

于是总复杂度 $O(n^3)$ 可以通过。

TwoPerLine

按照套路,我们可以把 $(x,y)$ 的棋子看成是二分图左侧的 $x$ 和右侧的 $y$ 之间的一条连边。于是现在问题就变成了给定 $n,m$ 求有多少种二分图满足有 $m$ 条边,且每个点度数不超过 $2$ 。一种非常显然的想法是设 $dp[l][r][a]$ 表示左边有 $l$ 个点度数是 $1$ ,右边有 $r$ 个,且一共已经连了 $a$ 条边。我们考虑左边的情况,假设有 $x$ 个点度数是 $0$ ,$y$ 个是 $2$ 于是有

发现可以解出 $x,y$ 。

但是还是存在一个问题。在连边的时候,如果我们想要给两个度数为 $1$ 的点连边,会发现我们并不知道这两个点之间是否已经存在边了。这个问题看起来很不可处理,可能需要多开好几维来解决。这个时候可以想到容斥掉这种情况,也就是说我们钦定最后图种会有 $k$ 条长成这样的重边存在,系数就是 $(-1)^k$ 。那么我们可以在转移中增加一种,在两个度数为 $0$ 的点间一次性连两条边。注意连第二条边的时候我们需要乘上一个 $m-a-1$ ,因为需要给他钦定一个连入的时间,这样才可以方便去重。

复杂度 $O(n^4)$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/02/13/yi-xie-topcoder-dp-ti-ti-jie/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog