写题解啦!JLOI2012 | JLOI2013 题解包

[JLOI2012]树

蛤! 趣题一道

每个点都倍增跳链即可。O(n \log n)

[JLOI2012]时间流逝

经典好题

首先……我们可以发现一个非常奇妙的性质,那就是可能的状态数是2 \times 10^5左右。那就可以大力搜了。

考虑状态。状态就是记录一下能量环。

转移

dp_i=p \cdot dp_{last} + (1-p) \cdot \frac{1}{|next|} \cdot \sum dp_{next} +1

next就是吃下一个圈,last是删掉min的状态。

这样转移显然是一棵树。

可是这也没法搞,想一下别的出路。。

尝试把\mathrm{dp_i}表示为k \cdot \mathrm{dp_{last}} +b的形式。

假设可以,那么我们有:

dp_i=p \cdot dp_{last} + (1-p) \cdot \frac{1}{|next|} \cdot \sum (k \cdot dp_i +b) +1

A= (1-p) \cdot \frac{1}{|next|} ,那么

dp_i - A \cdot \sum (k \cdot dp_i) = p \cdot dp_{last} + A \cdot \sum b +1

化简!

dp_i = \frac{p}{1-A \cdot \sum k} \cdot dp_{last} + \frac{1+A \cdot \sum b}{1-A \cdot \sum k}

证毕!

初始状态不存在last,所以答案就是那个常数项。

还要注意特判没圈的情况。

排序之后会很好处理。

谁出的这题,太强了……

注意到可以在平面坐标系上做第一象限的HPI。完事儿。

注意运用各种double运算,包括inf , nan , -inf的用法等,可以大量简化实现难度,这才是本题的重点。

数数题!当然不会数数,看的题解……

第一问就很简单,排序之后把每个点可以插进去的位置乘起来。

第二问把每段相同高度的答案都乘起来,段内答案这么算:

设dp[i][j]为段内前i个放前j个位置。

然后转移就是 \sum_{k=1}^{\min ( \mathrm{height} , \mathrm{cntpos} )}dp[i-1][k]

然后如果你滚动你就可以

dp[i]=dp[i]+dp[i-1]

就挺简单的一数数题

这题它是脑洞题。你把两个堆头碰头对在一起,然后拿个什么数据结构维护就行。

就挺好玩的。

这题年代久远了……分层概率dp

我忘了具体怎么做了……不写题解了(咕咕)

还有一个原因就是写题解写的我胃疼。。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据