Menci

眉眼如初,岁月如故

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


  1. 「NOI2008」糖果雨 - 坐标变换 + 二维树状数组

    在一个长度为 len \mathrm{len} 的区间上,有以下操作:

    1. t t 时刻,出现一条线段 [l,r] [l, r] ,这条线段将要向左或向右移动;
    2. t t 时刻查询与线段 [l,r] [l, r] 有公共点的线段有多少;
    3. t t 时刻某条线段消失。

    每一时刻,每条线段都会移动,线段的左端点最小为 0 0 ,当一条向左移动的线段左端点碰到 0 0 时,下一时刻它会改为向右移动;当一条向右移动的线段左端点碰到 len \mathrm{len} 时,下一时刻它会改为向左移动。

    于  BZOJ, NOI, 二维树状数组, 坐标变换, 树状数组 继续阅读

  2. 「NOI2012」随机数生成器 - 矩阵乘法

    已知

    给定 m,a,c,x0,n,g m, a, c, x_0, n, g ,求

    于  BZOJ, COGS, NOI, 矩阵乘法 继续阅读

  3. 「NOI2011」阿狸的打字机 - AC 自动机

    打字机上只有 28 28 个按键,分别印有 26 26 个小写英文字母和 BP 两个字母。

    经阿狸研究发现,这个打字机是这样工作的:

    • 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
    • 按一下印有 B 的按键,打字机凹槽中最后一个字母会消失。
    • 按一下印有 P 的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

    我们把纸上打印出来的字符串从 1 1 开始顺序编号,一直到 n n 。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数 (x,y) (x, y) (其中 1x,yn 1 \leq x, y \leq n ),打字机会显示第 x x 个打印的字符串在第 y y 个打印的字符串中出现了多少次。

    于  AC 自动机, BZOJ, NOI, 字符串 继续阅读

  4. 「NOI2016」网格 - 图连通性

    在一个 n×m n \times m 的网格上,有 c c 个障碍,其余均为空地。求至少需要将多少空地转化为障碍,可以使得存在两个空地在四连通意义下不在同一连通块中。

    于  BZOJ, NOI, Tarjan, 割点, 图论 继续阅读

  5. 「NOI2016」优秀的拆分 - Hash

    如果一个字符串可以被拆分为 AABB 的形式,其中 A A B B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。

    例如,对于字符串 aabaabaa,如果令 ,我们就找到了这个字符串拆分成 AABB 的一种方式。

    一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 ,也可以用 AABB 表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。

    现在给出一个长度为 n n 的字符串 S S ,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。

    于  BZOJ, Hash, NOI, 字符串 继续阅读

  6. 「NOI2016」区间 - 线段树

    在数轴上有 n n 个闭区间 [l1,r1],[l2,r2],,[ln,rn] [l_1, r_1], [l_2, r_2] , \ldots, [l_n, r_n] 。现在要从中选出 m m 个区间,使得这 m m 个区间共同包含至少一个位置。换句话说,就是使得存在一个 x x ,使得对于每一个被选中的区间 [li,ri] [l_i, r_i] ,都有 lixri l_i \leq x \leq r_i

    对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] [l_i, r_i] 的长度定义为 ,即等于它的右端点的值减去左端点的值。

    求所有合法方案中最小的花费。

    于  BZOJ, NOI, 线段树 继续阅读

  7. 「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, LCT, NOI, 数据结构 继续阅读

  8. 「NOI2014」动物园 - KMP

    对于字符串 S S 的前 i i 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 num(i) \mathrm {num}(i) ,求

    于  BZOJ, KMP, NOI, 字符串 继续阅读

  9. 「NOI2015」寿司晚宴 - 状压 DP

    给定 2 2 ~ n n n1 n - 1 个数,让两个人分别选出一些数,使得对于第一个人选择的任意一个数 a a 和第二个人选择的任意一个数 b b ,有 gcd(a,b)=1 \gcd(a, b) = 1 ,求方案数。

    于  BZOJ, DP, NOI, 状压 DP, 背包 DP 继续阅读

  10. 「NOI2015」荷马史诗 - 哈夫曼树

    n n 种不同的单词,从 1 1 n n 进行编号。其中第 i i 种单词出现的总次数为 Wi W_i 。要用 k k 进制串 Si S_i 来替换第 i i 种单词,满足对于任意的 1i,jn, ij 1 \leq i,j \leq n,\ i \neq j ,都有:Si S_i 不是 Sj S_j 的前缀。

    1. 替换以后得到的新的长度最小为多少;
    2. 在确保总长度最小的情况下,最长的 Si S_i 的最短长度是多少?

    于  BZOJ, NOI, 哈夫曼树, , 数据结构 继续阅读