uniHk

算法(Lazy)

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) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 算法(Lazy) （共38篇）

树的重心和直径

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

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

奇偶染色、二分图着色

利用DFS 由于每个顶点和每条边都只访问了一次，因此复杂度为O(V+E) const int maxn = 1e4+10; vector<int> g[maxn]; int n; //顶点数 int color[maxn]; //顶点i的颜色，1 or -1 bool dfs(...

2020-01-02

0 510

树状数组求区间最值

闲谈一下树状数组最基本的功能是加速前缀和的更新。查询一个数组的前缀和本来是O(1)的复杂度，用树状数组则为O(logn)。但树状数组优点在于单点更新时复杂度为O(logn)，而正常的为O(n)，这也就使得树状数组能够进行大规模的更新。虽然查询速度(O(logn))稍有些慢(相对于O(1)...

2020-01-02

0 845

LCA(最近公共祖先)

洛谷最近公共祖先模板题题目描述：给出一棵有 N N N个节点的树，有 ...

2020-01-02

0 413

牛客-game with numbers(筛法)

game with numbers 给定大小为 n n n的集合 S ...

2020-01-02

0 387

洛谷-食物链(扩展域并查集)

原题地址食物链动物王国中有三类动物 A , B , ...

2020-01-02

0 494

洛谷-P1169 棋盘制作(悬线法)

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8 × 8 ...

2020-01-02

0 423

牛客多校2019-7H-Pair（两个数的数位DP）

Pair 考场上加了各种各样的优化也没能由T变AC。。。赛后题解“直接数位DP就行” 题意：给定 A , B ...

2020-01-02

0 334