uniHk
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)
归档
标签
去牛客网
登录
/
注册
uniHk的博客
Universe of Hawking
全部文章
/ 算法(Lazy)
(共38篇)
树状数组(一维+二维)
树状数组 原理思想 利用二进制提高对大数组的操作速度,但存储空间不变,依旧需要开出原数组大小。 可当做一种快速的前缀和。 每次更新与每次查找都是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
二分图匹配(持续更新)
二分匹配核心算法:匈牙利算法(最大流的写法后续更新) 注意:匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值 先上匈牙利算法基础模板(求最大匹配数) 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
稳定婚姻匹配(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
首页
上一页
1
2
3
4
下一页
末页