Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 3809」Gty 的二逼妹子序列 - 莫队 + 分块

    给一个序列,每次求 [l,r] [l, r] 之间权值在 [a,b] [a, b] 之间的不同的数的数量。

    于  BZOJ, 分块, 莫队 继续阅读

  2. 「JSOI2012」玄武密码 - SAM

    给一个字符串 S S ,给一些字符串 si s_i ,求每个 si s_i 的最长的在 S S 中出现过的前缀的长度。

    于  BZOJ, JSOI, SAM, 字符串 继续阅读

  3. 「BZOJ 3569」DZY Loves Chinese II - 随机化 + 线性基

    给一个无向连通图,每次指定其中的 k k 条边,求如果将这些边删除,剩余的图是否仍然连通。

    于  BZOJ, 线性基, 随机化 继续阅读

  4. 「BZOJ 1677」求和 - DP

    给出一个 N N ,使用一些 2 2 的若干次幂的数相加来求之。问有多少种方法。

    于  BZOJ, DP, USACO, 背包 DP 继续阅读

  5. 「JSOI2010」部落划分 - Kruskal

    在二维平面上给若干个点,将这些点划分为若干个区域,定义两个区域的距离为这两个区域之间最近点对的距离。求将这些点划分为 k k 个区域,使得最近的两个区域的距离最大值。

    于  BZOJ, JSOI, Kruskal, 最小生成树 继续阅读

  6. 「BZOJ 3744」Gty 的妹子序列 - 分块 + 树状数组

    给一个序列,每次询问 [l,r] [l, r] 的逆序对数,强制在线。

    于  BZOJ, 分块, 树状数组 继续阅读

  7. 「SCOI2016」背单词 - Trie + 贪心

    总共有 n n 个单词,对于一个序号为 x x 的单词(序号 1x1 1 \ldots x - 1 都已经被填入):

    1. 如果存在一个单词是它的后缀,并且当前没有被填入表内,代价为 n×n n \times n 颗泡椒才能学会;
    2. 当它的所有后缀都被填入表内的情况下,如果在 1x1 1 \ldots x - 1 的位置上的单词都不是它的后缀,那么代价为 x x
    3. 当它的所有后缀都被填入表内的情况下,如果 1x1 1 \ldots x - 1 的位置上存在是它后缀的单词,所有是它后缀的单词中,序号最大为 y y ,那么代价为 xy x - y

    于  BZOJ, SCOI, Trie, 字符串, 贪心 继续阅读

  8. 后缀自动机学习笔记

    后缀自动机是一种有限状态自动机,它可以(且仅可以)接受一个字符串的所有后缀

    于  后缀自动机, 字符串, 学习笔记, 算法模板 继续阅读

  9. 「SDOI2014」LIS - 最小割 + 网络流退流

    给定序列 A A ,序列中的每一项 Ai A_i 有删除代价 Bi B_i 和附加属性 Ci C_i 。请删除若干项,使得 A A 的最长上升子序列长度减少至少 1 1 ,且付出的代价之和最小,并输出方案。

    如果有多种方案,请输出将删去项的附加属性排序 Ci C_i 之后,字典序最小的一种。

    于  BZOJ, SDOI, 最小割, 网络流 继续阅读

  10. 「BZOJ 4499」线性函数 - 线段树

    小 C 最近在学习线性函数,线性函数可以表示为 f(x)=kx+b f(x) = kx + b 。现在小 C 面前有 n n 个线性函数 fi(x)=kix+bi f_i(x) = k_ix+b_i ,他对这 n n 个线性函数执行 m m 次操作,每次可以:

    1. M i K B 代表把第 i i 个线性函数改为 fi(x)=kx+b f_i(x) = kx + b
    2. Q l r x 返回

    于  BZOJ, 线段树 继续阅读