Menci

眉眼如初,岁月如故

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


  1. 「HNOI2008」神奇的国度 - 最大势

    给一个弦图,求它的最小染色数。

    于  BZOJ, HNOI, 弦图, 最大势 继续阅读

  2. 「HNOI2008」Cards - Burnside 引理

    n n 张牌,3 种颜色,和 m m 种洗牌方案,求本质不同的染色方案数。

    于  BZOJ, Burnside 引理, HNOI, 数学, 群论 继续阅读

  3. 「HNOI2008」明明的烦恼 - Prüfer 序列

    给出标号为 1 1 N N 的点,以及某些点最终的度数,允许在任意两点间连线,求可产生多少棵度数满足要求的树。

    于  BZOJ, HNOI, Prüfer 序列, 数学, 高精度 继续阅读

  4. 「HNOI2008」GT考试 - KMP + 矩阵乘法

    给一个长度为 m m 的字符串 T T ,求长度为 n n 且不包含 T T 的字符串的数量。

    于  BZOJ, DP, HNOI, KMP, 字符串, 快速幂, 矩阵乘法 继续阅读

  5. 「HNOI2004」L语言 - Trie

    我们称一段文章 T T 在某个字典 D D 下是可以被理解的,是指如果文章 T T 可以被分成若干部分,且每一个部分都是字典 D D 中的单词。

    给定一个字典 D D ,你的程序需要判断若干段文章在字典 D D 下是否能够被理解。并给出其在字典 D D 下能够被理解的最长前缀的位置。

    于  BZOJ, HNOI, Trie, 字符串 继续阅读

  6. 「HNOI2012」矿场搭建 - 割点

    煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

    请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

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

  7. 「HNOI2010」合唱队 - 区间 DP

    合唱队的排队方式为:

    1. 第一个人直接插入空的队形中;
    2. 对于第二个人开始的每一个人,如果他比上一个人高,则站到最右边,否则站到最左边。

    求对于某一个排好的序列,可以被多少种初始序列构建出,答案对任意数取模。

    于  BZOJ, DP, HNOI, 区间 DP 继续阅读

  8. 「HNOI2016」树 - 最近公共祖先 + 主席树

    小 A 想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。开始,小 A 只有一棵结点数为 N N 的树,结点的编号为 ,其中结点 1 1 为根;我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下:

    1. 将模板树复制为初始的大树;
    2. 以下 3,4,5 步循环执行 M M 次;
    3. 选择两个数字 a, b a,\ b ,其中 1aN 1 \leq a \leq N 1b 1 \leq b \leq 当前大树的结点数;
    4. 将模板树中以结点 a a 为根的子树复制一遍,挂到大树中结点 b b 的下方(也就是说,模板树中的结点 a a 为根的子树复制到大树中后,将成为大树中结点 b b 的子树);
    5. 将新加入大树的结点按照在模板树中编号的顺序重新编号。例如,假设在进行 4 步之前大树有 L L 个结点,模板树中以 a a 为根的子树共有 C C 个结点,那么新加入模板树的 C C 个结点在大树中的编号将是 ;大树中这 C C 个结点编号的大小顺序和模板树中对应的 C C 个结点的大小顺序是一致的。

    现在他想问你,树中一些结点对的距离是多少。

    于  BZOJ, COGS, HNOI, 主席树, 最近公共祖先, 树链剖分 继续阅读

  9. 「HNOI2016」网络 - 树链剖分 + DFS 序

    一个简单的网络系统可以被描述成一棵无根树。两个服务器进行数据的交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。当路径上的某个服务器出现故障,无法正常运行时,数据便无法交互。此外,每个数据交互请求都有一个重要度。在每一个时刻,只有可能出现下列三种事件中的一种:

    1. 在某两个服务器之间出现一条新的数据交互请求;
    2. 某个数据交互结束请求;
    3. 某个服务器出现故障。

    系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后,这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。你的任务是在每次出现故障时,维护未被影响的请求中重要度的最大值。

    于  BZOJ, COGS, DFS 序, HNOI, 树链剖分 继续阅读

  10. 「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, 分块, 并查集 继续阅读