树状数组 原理思想 利用二进制提高对大数组的操作速度，但存储空间不变，依旧需要开出原数组大小。 可当做一种快速的前缀和。 每次更新与每次查找都是O(logn)，即更新变慢，但查找速度得到极大的提高。 缺点：无法删除和插入元素 主要函数（lowbit、add、sum） 1.lowbit(int a) 用途：提取数字a的最低位1； 原理：理解a&-a； 代码： int lowbit(int i) { return i&-i; } 2.add(int x, int d) 用途：在下标x处增加d（可正可负）； 原理：利用二进制依次向上...

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

详解请点击此处 http://blog.csdn.net/zearot/article/details/48299459 递归版 （我的)线段树要点 开数组的时候开到4*n即可。 若只涉及线段树的点修改或要进行单点查询，则要记录每个单点区间的编号（用fat数组），并在修改此单点区间后向上更新。 若涉及到线段树的区间修改，且不涉及单点查询，则不需要记录单点区间编号，并且更新过程利用lazy标记从上往下，直至区间刚好吻合。 区间合并时注意细节 基本函数 自定义： #define ls l,m,now<<1 #define rs m+1,r,now&lt...

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

二分匹配核心算法：匈牙利算法（最大流的写法后续更新） 注意：匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值 先上匈牙利算法基础模板（求最大匹配数） bool lj[MAXN][MAXN], vis[MAXN]; int link[MAXN]; int n; bool find(int x) { //算法核心，深搜操作 for(int i=0; i<n; ++i) { if(lj[x][i]&&!vis[i]) { vis[i]=1; if(link[i]==-1||find(l...

最大流模板（含三种模板） 最后一种最快， 前两种彼此彼此 紫书模板 #include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #include<cstring> #include<cctype> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<i...

独立集 独立集是指图的顶点集的一个子集,该子集的导出子图不含边.如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集.一个图中包含顶点数目最多的独立集称为最大独立集。最大独立集一定是极大独立集，但是极大独立集不一定是最大的独立集。 支配集 与独立集相对应的就是支配集，支配集也是图顶点集的一个子集，设S 是图G 的一个支配集，则对于图中的任意一个顶点u，要么属于集合s, 要么与s 中的顶点相邻。在s中除去任何元素后s不再是支配集，则支配集s是极小支配集。称G的所有支配集中顶点个数最少的支配集为最小支配集，最小支配集中的顶点个数成为支配数。 最小点的覆盖 最小点的覆...

2-Sat 算法 简介 什么是2-SAT呢？就是有一些集合，每个集合中有且仅有两个元素，同时每个集合需要选择一个作为代表，集合间的元素存在一定的选择关系，求解可行性及可行方案。 关键：连边(从"一定不能"中产生出"一定能") 2-SAT算法本身并不难，关键是连边，不过只需要充分理解好边的概念：a->b即选a必选b。 （也即连单向边） a、b不能同时选：选了a就要选b’，选了b就要选a’。 a、b必须同时选：选了a就要选b，选了b就要选a，选了a’就要选b’，选了b’就要选a’。 a、b必须选一个：选了a就要选b’，选了b就要...

随便记录点东西 在拓扑排序中，排序结果唯一当且仅当所有顶点间具有全序关系。 快速排序不是稳定的（偏序关系），因为相同元素之间的关系无法确定。 插入排序是稳定的（全序关系），因为相同元素可以通过位置的先后增加关系。 检测某DAG是否为全序关系，只需先进行拓扑排序，再检测结果中所有相邻顶点是否有一致的关系，若都存在正确的关系，则为全序（即此图存在哈密顿路径）。 正如下面的伪码，如果跑了一遍Kahn后还有点没有排好序，那么说明出现了环，即这个这不是个DAG。 Kahn算法 复杂度 O(E+V) 以下例题均采用此方法，并且此方法可以判断是否为DAG。 HDOJ 48...

稳定婚姻匹配 HDOJ 1435 Stable Match(此例基于发射点优先的匹配，但题目并未明确表明) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1236 Accepted Submission(s): 583 Special Judge Problem Description Network 公司的BOSS 说现在他们公司建立的信号发射站和接收站经常出现信号发送接收不稳定的问题,信号的稳定度被定义为发射点到接收点的距离,距...

极大团：无法从图中再加入一个顶点使得此顶点集的顶点两两相连的顶点集 因此单个顶点也可能是一个极大团 最大团：一个包含顶点数最多的极大团 最大独立集=补图的最大团 定理：最大独立集=补图的最大团，最大团=补图的最大独立集 Bron-kerbosch模板 说明 all-已取顶点集，some-未处理顶点集(初始状态是全部顶点)，none-不取的顶点集，g-边， S-极大团数量，ans-最大团结点数； 结点编号1~n，0用于辅助，表示被删除； 求最大团顶点数时只要some；要求记录路径时要all； 求极大团数量要some、none；要求记录路径时要all； 极大团计数 输入：some...

KMP(三位发明者名字首字母) next数组表示t[j]以前最长相同前缀后缀 若下标从0开始(以下模板就采用这种方式)，next[ i ] 表示前面下标0~i-1的字符串前缀和后缀相等的最大长度为 next[ i ] 。 若下标从1开始，则next[ i ] 表示前面下标1~i - 1的字符串中前缀和后缀相等的最大长度为 next[ i ] - 1 两种方式当s[i]与t[j]不同时j都应该移动到next[j] #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) ...

高斯消元法（列选主元法） 唯一解：判定存在性并求值 a a a数组存增广矩阵（第 n + 1 n+1 n+1列为...

树的重心 性质： 最大的子树最小 找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样，则这两个点都是重心（即重心可以有两个） 把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上 一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置 一棵树最多有两个重心，且相邻。 思路： 任选节点r为根节点做dfs，dfs的同时即更新所有的d(当前子树的大小)，以及最小的最大子树，注意当前子树的最大子树要...