Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 3376」Cube Stacking - 带权并查集

    约翰和贝茜在玩一个方块游戏。编号为 1 1 n n n n 个方块正放在地上.每个构成一个立方柱。

    游戏开始后,约翰会给贝茜发出 m m 个指令。指令有两种:

    1. 移动:将包含 x x 的立方柱移动到包含 y y 的立方柱上;
    2. 统计:统计名含 x x 的立方柱中,在 x x 下方的方块数目。

    写个程序帮贝茜完成游戏。

    于  BZOJ, 并查集, 数据结构 继续阅读

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

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

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

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

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

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

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

  4. 「BZOJ 3277」串 - 后缀数组 + 并查集 + 启发式合并

    n n 个字符串,询问每个字符串有多少子串(不要求本质不同,不包括空串)是所有 n n 个字符串中至少 k k 个字符串的子串。

    于  BZOJ, Codeforces, 后缀数组, 启发式合并, 字符串, 并查集 继续阅读

  5. 「SDOI2013」森林 - LCA + 主席树 + 启发式合并

    森林中有 n n 个点,m m 条边,每个点有点权,执行 T T 次操作:

    1. 查询两点间点权的第 k k 小;
    2. 连接两个点,保证图在操作后仍然为森林。

    于  BZOJ, SDOI, 主席树, 启发式合并, 并查集, 最近公共祖先 继续阅读

  6. 「NOI2015」品酒大会 - 后缀数组 + 并查集

    给定字符串 S S 和序列 f(i) f(i) ,对于 r[0, n1] r \in [0,\ n - 1] ,求:

    1. 满足 LCP(suffix(i), suffix(j))r \mathrm {LCP}(\mathrm{suffix}(i),\ \mathrm{suffix}(j)) \geq r 的无序二元组 (i, j) (i,\ j) 数量;
    2. 上述二元组 (i,j) (i, j) 使 f(i)×f(j) f(i) \times f(j) 取得的最大值。

    于  BZOJ, NOI, 后缀数组, 字符串, 并查集 继续阅读

  7. 「HNOI2016」最小公倍数 - 分块 + 并查集

    给定一张 N N 个顶点 M M 条边的无向图(顶点编号为 ),每条边上带有权值。所有权值都可以分解成 2a3b 2 ^ a 3 ^ b 的形式。现在有 q q 个询问,每次询问给定四个参数 u u v v a a b b ,请你求出是否存在一条顶点 u u v v 之间的路径,使得路径依次经过的边上的权值的最小公倍数为 2a3b 2 ^ a 3 ^ b

    于  BZOJ, COGS, CodeVS, HNOI, 分块, 并查集 继续阅读

  8. 「NOI2015」程序自动分析 - 离散化 + 并查集

    给定 n 个形如xi=xjx_i=x_j 的变量相等 / 不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。

    于  BZOJ, CodeVS, NOI, map, 哈希, 并查集, 离散化 继续阅读

  9. 最小生成树 && 次小生成树

    最近回顾了一下图论中的最小生成树算法,又学习了神奇(个卵)的“次小生成树”的算法。

    总体来说,图论里面的东西还是挺灵活的嘛 ~

    于  Kruskal, POJ, Prim, 倍增, 图论, 学习笔记, 并查集, 最小生成树, 算法模板 继续阅读

  10. 「NOI2002」银河英雄传说 - 并查集

    有 30000 个元素,初始时每个元素以单独的队列形式存在,支持一下两种操作:

    1.动态合并两条队列,将 x 元素所在队列首合并在 y 元素所在队列尾;
    2.查询 xy 是否在同一条队列中,若是,查询 xy 间隔元素数量。

    共 500,000 次操作。

    于  CodeVS, NOI, 并查集 继续阅读