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. 「JSOI2016」飞机调度 - 最短路 + 网络流

    JSOI 王国里有 N N 个机场,编号为 1 1 N N 。从 i i 号机场到 j j 号机场需要飞行 Ti,j T_{i, j} 的时间。由于风向,地理位置和航空管制的因素,Ti,j T_{i, j} Tj,i T_{j, i} 并不一定相同。

    此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 k k 号机场时,需要花费 Pk P_k 的维护时间才能再次起飞。

    JS Airways 一共运营 M M 条航线,其中第 i i 条直飞航线需要在 Di D_i 时刻从 Xi X_i 机场起飞,不经停,飞往 Yi Y_i 机场。

    为了简化问题,我们假设 JS Airway 可以在 0 0 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。

    JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 M M 个航班。

    于  Dinic, Floyd, JSOI, 最短路, 网络流 继续阅读