2022/04/08 做题记录

Posted on 2022-04-10 Disqus:

题面写的十分复杂，我甚至没弄明白开始节点在那个图上是哪 /yun

只看它描述的位置对应的题意，发现把格子 51~56 高斯消元一下就能求出它们的期望，剩下直接 dp 就行，之后在加上第一次投出 6 的期望 $\frac{1}{p_6}$ 就行。

考虑什么时候无解，首先是 $p_6=0$ ，如果 $p_6 \not = 0$ , 那么它和 1,2,4,5 都能拼到终点，于是另一种无解情况就是 $p_3 + p_6 = 1$ 。

code: /code/2022.4.8/ac8159.cpp

由于期望的线性性可以拆成每个点被经过次数的期望之和，因为保证了每个强联通分量的大小小于等于 100，可以拓扑排序后依次高斯消元。

判无解比较恶心，但感觉这东西意义不是很大，过了就行。

code: /code/2022.4.8/bz2707.cpp

发现背包大于 n 没有意义，直接 dp[i][j][k] 表示考虑到了第 i 项挑战，背包容量为 j (大于 n 时设为 n)，赢了 k 场的概率，直接转移就行。

复杂度 $\text{O}(n^3)$ 。

code: /code/2022.4.8/bz3029.cpp

我们可以维护一个类似于双指针的东西，记录从原串某一个位置开始最多能匹配到哪一位（循环的，并且最多匹配 len 位），于是容易向后添加字符，而删除第一个字符就是判断 len[fail] 是否大于等于 curlen 即可，curlen 也容易维护，简单分析可以得到时间复杂度 O(n)。

code: /code/2022.4.8/CF235C.cpp

话说这个 1C 怎么用 SAM /jk