E.Throwing the Die

题目链接

这道题我赛场上脑抽了

我们可以令\(dp_{i,j}\)表示还剩\(i\)轮时百分百投出\(j\)的最大期望值,\(sum_i\)表示还剩\(i\)轮时无论投出多少的最大期望值。

转移就很好想了

\(dp_{i,j}=\max{(sum_{i-1},j)},sum_i=\sum^{6}_{j=1}\frac{dp_{i,j}}{6}\)

就结束了

Code

F.Well-defined Path Queries on a Namori

题目链接

依然脑抽

很明显这道题是基环树(我没看出来),然后不难就可以想到:如果两个点之间的最短路只会经过环上最多一个点,那么这两个点之间的简单路径是唯一的。

当我们求出来环上的点后,我们不难想出从环上每一个点向外拓展,且不经过其它环上的点讲这个基环树分成一个个块,询问时,如果两个点在一个块内,那么答案就是Yes

Code