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篇）

奇偶染色、二分图着色

利用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

牛客-小w的基站网络(计算几何)

链接：https://ac.nowcoder.com/acm/contest/923/D 来源：牛客网题目中隐含条件是给的图是一个 DAG，那么就是一个 DAG上求单源最短路的问题。首先是肯定能写出一个 O ...

2020-01-02

0 349

洛谷-P3975 弦论(后缀自动机板子题)

弦论一道板子题，让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&，导致内存爆了，2333，果然还是传引用好题意：求字典序第K小子串以及本质不同的第K小子串思路：正常的建好后缀自动机由于处理一个节点有多少endpos以及经过一个节点有多少子...

2020-01-02

0 847

树状数组求区间最值

闲谈一下树状数组最基本的功能是加速前缀和的更新。查询一个数组的前缀和本来是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

凸包模板(Graham)

废话不多说，直接上模板 #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 using namespace std; ...

2020-01-02

0 469

树链剖分(洛谷P3384模板题)

题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2：格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3：格式： 3 x z...

2020-01-02

0 501

牛客-game with numbers(筛法)

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

2020-01-02

0 387

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

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

2020-01-02

0 494

计算几何(模板总结)

极为舒服的计算几何终极模板+总结小知识点 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #...

2020-01-02

0 524