uniHk

分类

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章（共121篇）

稳定婚姻匹配(Stable Match， HDOJ 1435， HDOJ 1914，详解)

稳定婚姻匹配 HDOJ 1435 Stable Match(此例基于发射点优先的匹配，但题目并未明确表明) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submiss...

2020-01-02

0 601

最大团+极大团计数(HDOJ 1530+POJ 2989, Bron-Kerbosch )

极大团：无法从图中再加入一个顶点使得此顶点集的顶点两两相连的顶点集因此单个顶点也可能是一个极大团最大团：一个包含顶点数最多的极大团最大独立集=补图的最大团定理：最大独立集=补图的最大团，最大团=补图的最大独立集 Bron-kerbosch模板说明 all-已取顶点集，some...

2020-01-02

0 1279

KMP+扩展KMP

KMP(三位发明者名字首字母) next数组表示t[j]以前最长相同前缀后缀若下标从0开始(以下模板就采用这种方式)，next[ i ] 表示前面下标0~i-1的字符串前缀和后缀相等的最大长度为 next[ i ] 。若下标从1开始，则next[ i ] 表示前面下标1~i - 1的字符串中...

2020-01-02

0 553

高斯消元法（模板）

高斯消元法（列选主元法）唯一解：判定存在性并求值 a a a数组存增广矩阵（第 ...

2020-01-02

0 486

树的重心和直径

树的重心性质：最大的子树最小找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样，则这两个点都是重心（即重心可以有两个）把...

2020-01-02

0 474

数位dp练习题

随便记录几个题，防止连数位dp的思路都忘了，2333 数位dp 先将上限各位保存到num数组从高位到低位dfs（暴力）记忆化，优雅的暴力，否则就是O(n)的算法了，对单个数据也有很大的加速 pos为-1时以及记忆存在时可直接返回关键：时刻记住判断条件，做到不重不漏 ...

2020-01-02

0 525

强连通分量-tarjan缩点

强烈推荐的tarjan解释 HDU 3861 The King’s Problem 缩点后得到新图，在新图上跑最小路径覆盖，得到答案 The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/3...

2020-01-02

0 511

数学（杂记）

逆元逆元满足： a ∗ i n v ...

2020-01-02

0 378

概率DP

HDU 4089 Activation(推导公式) Activation Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5214 Ac...

2020-01-02

0 409

线性基(线性无关的基底)

概述所谓线性基，就是线性代数里面的概念。一组线性无关的向量便可以作为一组基底，张起一个线性的向量空间，这个基底又称之为线性基。这个线性基的基底进行线性运算，可以表示向量空间内的所有向量，也即所有向量可以拆成基底的线性组合。定义设数集 ...

2020-01-02

0 595