Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 2555」SubString - SAM + LCT

    1. 在当前字符串的后面插入一个字符串;
    2. 询问字符串 s s 在当前字符串中出现了几次?(作为连续子串)

    于  BZOJ, Link-Cut Tree, SAM, 字符串, 数据结构 继续阅读

  2. 「NOI2014」魔法森林 - LCT

    魔法森林是一个 N N 个节点 M M 条边的无向图,节点标号为 1N 1 \ldots N ,边标号为 1M 1 \ldots M 。初始时小 E 同学在号节点 1 1 ,隐士在节点 N N

    无向图中的每一条边 Ei E_i 包含两个权值 Ai A_i Bi B_i 。若身上携带的 A 型守护精灵个数不少于 Ai A_i ,且 B 型守护精灵个数不少于 Bi B_i ,这条边上的妖怪就发起攻击。

    小 E 想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数。

    于  BZOJ, Link-Cut Tree, NOI, 数据结构 继续阅读

  3. 「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, 安徽集训, 数据结构, 离线, 高级数据结构 继续阅读

  4. 「SDOI2008」洞穴勘测 - Link-Cut Tree

    如果监测到洞穴 u u 和洞穴 v v 之间出现了一条通道,终端机上会显示一条指令 Connect u v;如果监测到洞穴 u u 和洞穴 v v 之间的通道被毁,终端机上会显示一条指令 Destroy u v。辉辉希望能随时通过终端机发出指令 Query u v,向监测仪询问此时洞穴 u u 和洞穴 v v 是否连通。已知在第一条指令显示之前,洞穴群中没有任何通道存在。

    于  BZOJ, CodeVS, Link-Cut Tree, SDOI, 动态树, 数据结构, 高级数据结构 继续阅读

  5. Link-Cut Tree 学习笔记

    Link-Cut Tree 是一种用来维护动态森林连通性的数据结构,适用于动态树问题。它采用类似树链剖分的轻重边路径剖分,把树边分为实边和虚边,并用 Splay 来维护每一条实路径。Link-Cut Tree 的基本操作复杂度为均摊 O(logn)O({\log}n),但常数因子较大,一般效率会低于树链剖分。

    于  Link-Cut Tree, Splay, 动态树, 数据结构, 算法模板, 高级数据结构 继续阅读