Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 1396」识别子串 - SAM + 线段树

    对于一个字符串 S S ,和 S S 中的第 i i 个字符 x x ,定义子串 T=S(ij) T = S(i \ldots j) 为一个关于 x x 的识别子串,当且仅当:

    1. ixj i \leq x \leq j
    2. T T S S 中只出现一次。

    S S 关于每一位字符的最短识别子串长度。

    于  BZOJ, SAM, 李超树, 线段树 继续阅读

  2. 「SDOI2016」游戏 - 树链剖分

    Alice 和 Bob 在玩一个游戏。
    游戏在一棵有 n n 个点的树上进行。最初,每个点上都只有一个数字,那个数字是 123456789123456789 123456789123456789
    有时,Alice 会选择一条从 s s t t 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r r ,若 r r s s 的距离是 dis dis ,那么 Alice 在点 r r 上添加的数字是 a×dis+b a \times dis + b
    有时,Bob 会选择一条从 s s t t 的路径。他需要先从这条路径上选择一个点,再从那个点上选择一个数字。
    Bob 选择的数字越小越好,但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

    于  BZOJ, COGS, SDOI, 数学, 数据结构, 最近公共祖先, 李超树, 树链剖分, 线段树 继续阅读