Menci

眉眼如初,岁月如故

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


  1. 「JSOI2008」星球大战 - 离线 + 并查集

    给一个图,每次删除一个点,求连通块数量。

    于  BZOJ, JSOI, 并查集, 离线 继续阅读

  2. 「HDU 5906」Square Revolution - 后缀数组 + 并查集 + 树状数组

    对于一个给定的字符串 S S ,有多少连续子串是 prefix-suffix-square free 的。

    一个字符串被称为 square 当且仅当它可以由两个相同的串连接而成。例如,ababaa 是 square,而 aaaabba 不是。一个字符串是 prefix-suffix-square free 的当且仅当他的任何前缀或者后缀都不是 square。

    于  Bestcoder, HDU, 后缀数组, 字符串, 并查集, 树状数组, 离线 继续阅读

  3. 「TJOI2013」最长上升子序列 - 离线 + 树状数组

    给定一个序列,初始为空。现在我们将 1 1 N N 的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

    于  BZOJ, Splay, TJOI, 树状数组, 离线 继续阅读

  4. 「SCOI2015」情报传递 - 离线 + Link-Cut Tree

    奈特公司有着庞大的情报网络。情报网络中共有 n n 名情报员。每名情报员有若干名下线,除 1 名大头目外其余 n1 n - 1 名情报员有且仅有 1 名上线。每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。 奈特公司每天会派发以下两种任务中的一个任务:

    1. 搜集情报:指派 T T 号情报员搜集情报;
    2. 传递情报:将一条情报从 X X 号情报员传递给 Y Y 号情报员。

    情报员最初处于潜伏阶段,危险值为 0;一旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加 1 点危险值(开始搜集情报的当天危险值仍为 0,第 2 天危险值为 1,以此类推)。传递情报并不会使情报员的危险值增加。

    为了保证传递情报的过程相对安全,每条情报都有一个风险控制值 C C 。公司认为,传递这条情报的所有情报员中,危险值大于 C C 的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

    于  BZOJ, Link-Cut Tree, SCOI, 安徽集训, 数据结构, 离线, 高级数据结构 继续阅读