Day8考试总结及学习笔记

考试心路历程

预计得分：$50 + 100 + 0$

实际得分：$100 + 0 + 0$

排名：$38$

T1考场上推了好长时间才得到一些有用的结论，最后写了一个复杂度玄学的做法，不过还是过掉了这题。下午讲题的时候仔细思考了一下发现复杂度是对的。

T2推出了最核心的式子，无奈还是对期望的理解不够，在决策的时候误以为最短路是最优决策。成功爆零

T3在还有1h的时候想到了$n^3$的做法，不过在结束的时候都没有调出来。。

考试题解

T1

由于题目中保证了$m$次一定能消完，那么每段颜色区间一定是互不包含的。

那么最优的决策一定在两端

T2

首先推出期望的式子

$f[x] = \frac{\sum f[to] + M}{inder[x]}$

直接把期望代入Dijkstra即可

T3

没看。。

题目

大部分都没听懂。。

相关资料

https://loj.ac/problem/129

http://acm.hdu.edu.cn/showproblem.php?pid=5343