Menci

眉眼如初,岁月如故

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


  1. 「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

    给出 m m 个串组成的「标准作文库」。对于任意一个串,如果它的长度不少于 L L 且在标准作文库中出现过,则它是「熟悉」的。对于任意一个串,如果能将它划分为若干个串,使「熟悉」的串的长度超过总长度的 90% 90\% ,则称这个串是「熟悉的文章」,定义 L0 L_0 为使这个串成为「熟悉的文章」的最大的 L L 。给出若干个串,求每个串的 L L 值。

    于  BZOJ, CTSC, DP, SAM, 二分, 单调队列, 字符串 继续阅读

  2. 「CTSC1999」星际转移 - 网络流

    现有 n 个太空站位于地球与月球之间,且有 m 艘太空船在其间来回穿梭。每个太空站可容纳无限多的人,第 i 个太空船只可容纳 H[i] 个人。每艘太空船将周期性地停靠一系列的太空站。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上,太空船全在初始站。求让所有人尽快地全部转移到月球上的最短时间。

    于  COGS, CTSC, Dinic, 图论, 枚举答案, 网络流, 网络流 24 题 继续阅读

  3. 「CTSC1997」选课 - 树形 DP

    学校开设了 N(<= 300) 门课程,每门课程有不同的学分,每个学生最多可以选择 M 门课程,有些课程有“先修课”,即这门课必须在先修课选定之后再选,每门课程的先修课最多有一门。求获得学分最多的选课方案。

    于  CTSC, CodeVS, DP, 树形 DP 继续阅读