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

树状数组（一维+二维）

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

2020-01-02

0 509

最短路(最长路)

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

2020-01-02

1 572

线段树（附究极详解）

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

2020-01-02

0 464

二分图匹配（持续更新）

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

2020-01-02

0 596

网络流（持续更新）

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

2020-01-02

0 476

图论(要点)

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

2020-01-02

0 759

2-Sat

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

2020-01-02

0 619

拓扑排序总结(Kahn算法)

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

2020-01-02

0 840

稳定婚姻匹配(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 602

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

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

2020-01-02

0 1280