2021.10.20模拟赛

Crumbled like the sands of time, that’s how it ends

2021.10.20 模拟赛

根据期望的线性性有每个点的期望之和就是整个图的期望，每个点的期望就是选到自己的概率，即能到达自己的点的倒数

Floyd跑传递闭包即可

简单 DP ，设 $dp_{i,j}$ 表示第一个串匹配到了第 $i$ 个，第二个串匹配到了 $j$ ，枚举删不删跳 fail 转移即可

原题 NOIP 2013

暴力跑过去了，感谢时代的进步（和O2

考虑每个时刻新增的不好求，但是总面积跑个矩形面积并就出来了

那设 $F(i)$ 是 $i$ 时刻的总面积，答案为 $\sum i(F(i+1)-F(i))=tF(t)-\sum F(i)$

发现重要性质是每个时刻 $F(i)$ 都是二次函数，系数的值只有在相交才会变，所以有 $O(n^2)$ 次变化，每次前缀和是 $3$ 次的，插值即可