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

字典树（Trie树）

字典树（Trie树，单词查找树）基本要点根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。基本操作查找、插入、删除实现过程从根节点开始...

2020-01-02

0 726

树状数组（一维+二维）

树状数组原理思想利用二进制提高对大数组的操作速度，但存储空间不变，依旧需要开出原数组大小。可当做一种快速的前缀和。每次更新与每次查找都是O(logn)，即更新变慢，但查找速度得到极大的提高。缺点：无法删除和插入元素主要函数（lowbit、add、sum） 1....

2020-01-02

0 508

最短路(最长路)

Dijkstra 补充：求次短路，只需要多维护一个“短路”就行了；但在维护次短路时，要记得把更新前的最短路与更新后的最短路swap一下，留着给次短路更新；注意：不能处理负边权，有负边权就换SPFA，当然也不能求最长路。以下代码以HDOJ 1874(畅通工程续) 为例题目链接简洁好...

2020-01-02

1 571

线段树（附究极详解）

详解请点击此处 http://blog.csdn.net/zearot/article/details/48299459 递归版（我的)线段树要点开数组的时候开到4*n即可。若只涉及线段树的点修改或要进行单点查询，则要记录每个单点区间的编号（用fat数组），并在修改此单点区间后...

2020-01-02

0 461

欧拉筛+欧拉函数+莫比乌斯函数

原理、思想通过已知素数及当前自然数筛掉后面的合数。同时让每一个合数只被筛去一次，摒弃重复的筛除操作。记忆要点两个数组：一个vis[]，一个prime[]。循环从2开始，直到所给的上限n处（或者直接maxn）。无论当前数是否是质数，都要进行后续合数的...

2020-01-02

0 515

二分图匹配（持续更新）

二分匹配核心算法：匈牙利算法（最大流的写法后续更新）注意：匈牙利算法也适用于没有强连通分量的图的最大匹配求值先上匈牙利算法基础模板（求最大匹配数） bool lj[MAXN][MAXN], vis[MAXN]; int link[MAXN]; int n; bool find(...

2020-01-02

0 595

网络流（持续更新）

最大流模板（含三种模板）最后一种最快，前两种彼此彼此紫书模板 #include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #include<cstrin...

2020-01-02

0 475

图论(要点)

独立集独立集是指图的顶点集的一个子集,该子集的导出子图不含边.如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集.一个图中包含顶点数目最多的独立集称为最大独立集。最大独立集一定是极大独立集，但是极大独立集不一定是最大的独立集。支配集与独立集相对应的就是支配集，支配...

2020-01-02

0 758

2-Sat

2-Sat 算法简介什么是2-SAT呢？就是有一些集合，每个集合中有且仅有两个元素，同时每个集合需要选择一个作为代表，集合间的元素存在一定的选择关系，求解可行性及可行方案。关键：连边(从"一定不能"中产生出"一定能") 2-SAT算法本身并不难，...

2020-01-02

0 615

拓扑排序总结(Kahn算法)

随便记录点东西在拓扑排序中，排序结果唯一当且仅当所有顶点间具有全序关系。快速排序不是稳定的（偏序关系），因为相同元素之间的关系无法确定。插入排序是稳定的（全序关系），因为相同元素可以通过位置的先后增加关系。检测某DAG是否为全序关系，只需先进行拓扑排序，再检测结果中所有相...

2020-01-02

0 837