Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「NOIP2016」换教室 - Floyd + DP + 概率与期望

    对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

    在可以选择的课程中,有 2n 2n 节课程安排在 n n 个时间段上。在第 i i 1in 1 \leq i \leq n )个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci c_i 上课,而另一节课程在教室 di d_i 进行。

    在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n n 节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第 i i 个时间段去教室 di d_i 上课,否则仍然在教室 ci c_i 上课。

    由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i i 节课程的教室时,申请被通过的概率是一个已知的实数 ki k_i ,并且对于不同课程的申请,被通过的概率是互相独立的。

    学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请白己最希望更换教室的 m m 门课程,也可以不用完这 m m 个申请的机会,甚至可以一门课程都不申请。

    因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课问时间从一间教室赶到另一间教室。

    牛牛所在的大学有 v v 个教室,有 e e 条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。当第 i i 1in1 1 \leq i \leq n - 1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。

    现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

    于  DP, Floyd, NOIP, 概率与期望 继续阅读

  2. 「JSOI2009」有趣的游戏 - AC 自动机 + 概率与期望

    现有 n n 个单词,均由前 m m 个大写字母组成。每一时刻随机产生一个字母,产生第 i i 个字母的概率为 piqi(0piqi) {p_i \over q_i} (0 \leq p_i \leq q_i) T T 时刻后会产生一个长度为 T T 的串。

    如果某个时刻,有一个单词在这个串中出现了,则过程结束。求产生的串中出现每个单词的概率。

    于  AC 自动机, BZOJ, JSOI, 字符串, 数学, 概率与期望, 高斯消元 继续阅读

  3. 「UVa 11021」Tribles - 概率与期望

    k k 个 Tribles,每个 Trible 只能存活一天,但在死亡之前,每个 Trible 有 pi p_i 的概率繁衍出 i i 个 Tribles。求 m m 天之后所有 Tribles 全部死亡的概率。

    于  COGS, DP, UVa, 数学, 概率与期望 继续阅读

  4. 「BZOJ 4318」OSU! - 概率与期望

    我们可以把 osu! 的规则简化与改编成以下的样子:

    一共有 n n 次操作,每次操作只有成功与失败之分,成功对应 1 1 ,失败对应 0 0 n n 次操作对应为 1 1 个长度为 n n 的 01 串。在这个串中连续的 x x 1 1 可以贡献 x3 x ^ 3 的分数,这 x x 1 1 不能被其他连续的 1 1 所包含(也就是极长的一串 1 1 )。

    现在给出 n n ,以及每个操作的成功率,请你输出期望分数。

    于  BZOJ, DP, 数学, 概率与期望 继续阅读