省选总结

开场看 T1，显然转换成每个边是重边的期望，答案是好算的。猜了个结论直接对重链长算期望然后再用期望求和算边是重边的期望，然后通过样例一的第二组数据可以发现假完了，考虑记 $dp_{i,j}$ 表示点 $i$ 的重链长为 $j$ 的概率，然后有

当时并没有继续推，然后看后两题，T2感觉可以自动机上dp，T3完全没想法，于是看T2。

因为恰好有 $k$ 个字串满足某种条件再自动机的转移上是比较好记录的，这里是单串，于是考虑再kmp自动机上做dp，于是记出了 $dp_{i,j,x}$ 的状态表示跑了 $i$ 个字符，在自动机的 $x$，有 $x$ 个子串小于 $k$ 是否可以到，但是马上发现不对，字典序比 $s$ 小的分两类，$s$ 的前缀或者 $s$ 的前缀，然后再一个 $s$ 为 $1$ 的位上填0，后面乱填不管。对于第一类，我们可能转移到一半让它变成 $s$ 了，并不会像第二类一样添加字符仍然还是第二类，所以第一类到第二类、第二类到第二类的转移都可以跑，但是第一类绝对不能直接和第二类公用一维，状态必须记 $dp_{i,j,x,y}$ 表示跑了 $i$ 个字符，在自动机的 $x$，有 $x$ 个第一类子串小于 $k$，$y$ 个第二类子串是否可以到。然后状态大小 $n^2m^2$ 打算就先当个暴力写，写完才发现还要包含 $s$，于是再加一位 $01$，也是好记的，然后测样例，才发现要输出方案，然后一想无论是不滚动记从哪里来还是直接记答案都是 $n^2m^2$ 的空间估计才 $15$ 分还要看我实现的常数，然后放弃，回去看T1。

发现上面式子可以枚举儿子、枚举长度，然后钦定这个儿子选择这个长度，然后记一个 $f_i$ 表示目前选择的所有儿子的链长和为 $i$ 的概率，然后枚举儿子跑dp，对于我们钦定的儿子只能取钦定的长度，设钦定的长度为 $x$，儿子$v$，让 u->v 的边成为重边的概率和 $dp_{u,x}$ 同时加 $x\sum_{i=1}^n\frac{f_i}{i}$，然后分析复杂度：

每个点枚举儿子和长度，是 $O(n^2)$ 的。

每个儿子的每个长度要扫一遍其他儿子，每个儿子更新f，复杂度是 $O(\text{不同长度数量}\times n)$ 的，所以一个儿子的一个长度的复杂度是 $O(n^2)$ 的，所以一个 $u$ 的复杂度是 $siz_u\times n^2$，总复杂度 $n^4$。

用时：

T1 4h

T2 50min

T3 5min

先通读了一遍题目，T1有点说法，T2什么玩意，T3什么玩意。

然后开始死磕T1，首先考虑到按值域从小到大跑，然后发现找到 $0$ 后可以维护一共区间 $[l,r]$，每次看一个没用的数 $v$ 在左边还是右边，然后直接暴力拓展过去，拓展到了之后设新的 $mex$ 是 $x$，然后把 $v$ 填在端点上，然后 $v+1\sim x$ 还没有用的数在 $[l,r]$ 乱填都可以，但是在性质 $n$ 会被卡到 $2n+\log_2 n$，然后就开始了各种优化，最终结果是卡到 $1.5n$。没然后了，后两题什么玩意。

T1 4.5h T2 5min T3 5min

Day1的T1dp都写出来了但是我都没想到背包我是唐逼，dp都写出来了但是我都没发现可以直接多项式卷起来我是唐逼，dp都写出来了但是我都没法很快的分析出复杂度我是唐逼。Day1的T2dp都写出来了但是我都没想到没必要记 $i$ 直接放在状态里面存最小值就行我是唐逼。Day2的T1直接掉进 $1.5n$ 做法不出来我是唐逼。

所以我这么唐为什么可以去省选。

我真的学会树形dp了吗我真的学会多项式了吗我真的学会背包了吗我真的学会自动机了吗我真的学会构造了吗我真的学会dp了吗我真的学会分析复杂度了吗？

估计总分：$20+[0,100)=[20,100]$