Menci

眉眼如初,岁月如故

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


  1. 「APIO2013」TOLL - 搜索 + 最小生成树

    幸福国度可以用 NN 个城镇(用 11NN 编号)构成的集合来描述,这些城镇最开始由 MM 条双向道路(用 11MM 编号)连接。城镇 11 是中央城镇。保证一个人从城镇 11 出发,经过这些道路,可以到达其他的任何一个城市。这些道路都是收费道路,道路 ii 的使用者必须向道路的主人支付 cic_i 分钱的费用。已知所有的这些 cic_i 是互不相等的。最近有 KK 条新道路建成,这些道路都属于亿万富豪 Mr. Greedy。

    Mr. Greedy 可以决定每条新道路的费用(费用可以相同),并且他必须在明天宣布这些费用。

    两周以后,幸福国度将举办一个盛况空前的嘉年华!大量的参与者将沿着这些道路游行并前往中央城镇。共计 pjp_j 个参与者将从城镇 jj 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行,并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗,这些道路将由幸福国度中最有钱的人选出,也就是 Mr. Greedy。同样根据这个习俗,Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小,并且仍要保证任何人可以从城镇 jj 前往城镇 11 (因此,这些选出的道路来自将费用作为相应边边权的 “最小生成树”)。如果有多个这样的道路集合,Mr. Greedy 可以选其中的任何一个,只要满足费用和是最小的。

    Mr. Greedy 很明确地知道,他从 KK 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲,如果 pp 个人经过道路 ii,道路 ii 产生的收入为乘积 cipc_i \cdot p。注意 Mr. Greedy 只能从新道路收取费用,因为原来的道路都不属于他。

    Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用(将在明天公布),并且选择嘉年华用的道路(将在嘉年华的前一天公布),使得他在 KK 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

    你是一个记者,你想揭露他的计划。为了做成这件事,你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

    于  APIO, BZOJ, UOJ, 搜索, 最小生成树 继续阅读

  2. 「APIO2014」Split the sequence - 斜率优化 DP

    你正在玩一个关于长度为 n n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1 k + 1 个非空的块。为了得到 k+1 k + 1 块,你需要重复下面的操作 k k 次:

    1. 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
    2. 选择两个相邻元素把这个块从中间分开,得到两个非空的块。

    每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

    于  APIO, BZOJ, DP, UOJ 继续阅读

  3. 「APIO2012」Dispatching - 左偏树

    给定一棵 n n 个点的有根树,每个点有两个属性 Ci C_i Li L_i ,现在你要指定一个点 R R ,并在 R R 的子树内选取若干点(可以选取 R R 自己),使得这些点的 Ci C_i 的和不超过 M M ,而一个选取方案的价值为选取人数 ×LR \times L_R ,求选取方案的最大价值。

    于  APIO, BZOJ, 左偏树, 数据结构 继续阅读

  4. 「APIO2010」特别行动队 - 斜率优化 DP

    一支部队由 n n 名预备役士兵组成,士兵从 1 1 n n 编号,要将他们拆分成若干特别行动队,同一队中队员的编号应该连续。

    士兵 i i 的初始战斗力为 xi x_i 一支特别行动队的初始战斗力 x x 为各士兵初始战斗力之和。一支特别行动队的战斗力会被修正为 x=Ax2+Bx+C x' = Ax ^ 2 + Bx + C ,其中 A A B B C C 已知,A<0 A < 0

    求出将所有士兵组成若干特别行动队的最大总战斗力。

    于  APIO, BZOJ, DP, 单调队列, 斜率优化 继续阅读

  5. 「APIO2009」抢掠计划 - 强连通分量

    城中的道路都是单向的。不同的道路由路口连接。在每个路口都设立了一个 ATM 取款机。酒吧也都设在路口,虽然并不是每个路口都设有酒吧。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆祝他的胜利。

    他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机里面就不会再有钱了。

    于  APIO, BZOJ, Bellman-Ford, DAG, Tarjan, 强连通分量, 最长路, 缩点 继续阅读