Menci

眉眼如初,岁月如故

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


  1. 「AHOI2013」作业 - 莫队

    给一个长度为 n n 的序列,每次查询一个区间 x[l,r] x \in [l, r] 内满足 aixbi a_i \leq x \leq b_i x x 的数量和不重复的 x x 的数量。

    于  AHOI, BZOJ, 数据结构, 莫队 继续阅读

  2. 「AHOI2013」差异 - 后缀数组

    一个长度为 n n 的字符串,令 Ti T_i 表示它从第 i i 个字符开始的后缀,求

    1i<jnlen(Ti)+len(Tj)2×lcp(Ti,Tj) \sum\limits_{1 \leq i < j \leq n} \mathrm{len}(T_i) + \mathrm{len}(T_j) - 2 \times \mathrm{lcp}(T_i, T_j)

    于  AHOI, BZOJ, 单调栈, 后缀数组, 字符串 继续阅读

  3. 「AHOI2014」支线剧情 - 费用流

    游戏中有 N N 个剧情点,由 1 1 N N 编号,第 i i 个剧情点可以经过不同的支线剧情,前往 Ki K_i 种不同的新的剧情点。当然如果为 0 0 ,则说明 i i 号剧情点是游戏的一个结局了。

    开始处在 1 1 号剧情点。任何一个剧情点都是从 1 1 号剧情点可达的。从任意剧情点出发,都不能再回到这个剧情点。要想回到之前的剧情点,唯一的方法就是开始新的游戏,回到 1 1 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间,看完所有不同的支线剧情。

    于  AHOI, BZOJ, Edmonds-Karp, 上下界网络流, 网络流, 费用流 继续阅读

  4. 「AHOI2008」紧急集合 - 最近公共祖先

    在树上寻找一个点,使其到给定三点的距离之和最小。

    于  AHOI, BZOJ, 乱搞, 倍增, 最近公共祖先 继续阅读