E
设扔到 $i$ 的概率是 $p_i$,答案为 $\sum \limits_{i = 1}^n a_i p_i$。
显然有 $p_i = \dfrac{1}{n}\sum \limits_{j = 1}^{i - 1} p_j$。
递推就行。
F
神秘题,以后看到 $n$ 比较小但又不是太小(如小)一定要记得考虑折半搜索。
首先注意到每次走之前都要转一下,这意味着奇数次操作一定是竖直方向上走,偶数次操作一定是水平方向上走,这样就可以把原问题划分成两个小问题,然后 $n$ 的范围减半。
接下来就是折半搜索模版题了,用 map
存一下所有可能的位置,dfs 完判断即可。
G
数据范围这么小,$L_{i, j}$ 还不超过 $5$,实在是太像网络流了!
然后我发现我不记得最小割是什么了,6。
直接做是不好做的,假设最开始已经获得了所有成就的奖励,然后看要去掉哪些成就。
首先让 $S$ 往每个技能的五个阶段连边,容量都是 $c_i$。
一个技能的等级是有先后顺序的,所以等级 $i$ 向 $i - 1$ 连容量是 $\infty$ 的边。
对于每个成就,从对应需要的技能最低等级那里连边,容量是 $\infty$。
最后把每个成就连到 $T$ 上,流量是 $a_i$。
这个图的最小割就是成本和未取得的奖励的和的最小值,拿总和减一下就行。
One comment
不错不错,我喜欢看 https://www.237fa.com/