PKU代码与ACM算法模板

本科参加ACM竞赛的过程中积累下来的一部分算法模板，和自己在PKU上面做的一部分题目。 模板目录结构： 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸多边形面积 半平面交 计算几何库 数据结构 闭散列法整数hash 开散列法整数hash 字符串hash 堆 二维树状数组 Trie树 二叉查找树 线段树 RMQ LCA+RMQ SB-Tree 数论 生成紧凑素数表 分解质因子 最大公约数 a^b mod n 扩张欧几里德算法 素数表质因子分解 Stirling公式 中国剩余定理 欧拉数(递推法) 欧拉数(公式法) 十进制转负进制 归并排序求逆序数 Pell方程 Catalan数,100以内 欧拉函数讲解 组合计数 组合数计算(double) 组合数计算(高精度) r-组合生成算法 r-排列生成算法 r-错位排列生成算法 图论 传递闭包 欧拉回路判定 有向图欧拉路径 二分图最大匹配 匈牙利算法 二分图最大匹配 HK算法 二分图最大权匹配 KM算法 割边 强连通分量 缩点 Kosaraju算法 最大团 最小树形图 无向图全局最小割 stoer-wagner O(n^3) 最短路径优先算法 SPFA 网络流 最大流：Ford&Fulkerson算法 最大流：Dinic算法 最大流：ek算法 最大流：dsp算法 最大流：hlpp算法 最小费用最大流：bellman_ford找增广路 最小费用最大流：ssp算法 字符串 KMP 通配符匹配 最小表示法 后缀数组 倍增算法 基于多串匹配的有限状态自动机 未分类 归并排序 星期几的计算 N皇后构造法 几个常用的位操作 最大最小定理总结 0/1分数规划总结 (by yxysdcl 2008/11/19) 代码目录结构： 目录: 动态规划 钉子和小球 Hash+dp分词(摩尔电码) 火柴棒等式 DAG图DP,老鼠打洞 最短子路径 最少回文数 矩阵链乘 树形DP 最少的石子填到根节点 树种删除最少的边使刚好剩下P个点 树的支配集 最优连通子集 带背包的树形DP 最小顶点覆盖,判唯一 用最少的点覆盖所有的边 DAG上的记忆化树形DP,博弈 有限状态自动机+树形DP 状态压缩DP 炮兵阵地 Help Bob,买匹萨 匹配数量 堆筛子 全排列式状态DP 计算几何 多边形地图染色 数据结构 Hash 枚举+hash,方程解数 点集对称中心 字符hash,统计出现最多的单词 类此The Happy worm 数据结构 树状数组 覆盖某区间数量统计 Cows Stars 两个树桩数组 二维树状数组 数据结构 双端队列 Sliding Window 数据结构 线段树 Cows 线段染色 排队问题 第K大的数 离散化+线段树 灯光投影 网络赛取连续子序列问题 线段树+树状数组+并查集,转化为排队问题 离散化 离散化矩形切割,矩形覆盖面积统计 覆盖矩形周长统计 离散化矩形切割 灯光投影 搜索 导弹 Bfs+hash状态的抽象,模关系 Bfs变形,钥匙与门 双向广搜 迭代加深 优先队列搜索,过最少的门救人,建图 A*搜索 图论 差分约束 Intervals bellman_ford Intervals SPFA 出纳员的雇佣 不等式组 图论 割边 图染色 拓扑 树 欧拉路径) 割点+统计删除后剩下多少连通图 删除一个点使得连通分量最多 图染色 拓扑排序全部序列 最大生成树 有向图欧拉路径 字典序最小的有向图欧拉路径 图论 匹配 完美匹配FBI Koning定理,泥地 二分图最大独立集 通讯站天线覆盖 二分图拆分后匹配 二分图某边唯一匹配 最小权匹配 海上矿工 floyd预处理 最大权匹配,需要非完全图转完全图 传递闭包+最小路径覆盖 可以重复经过点 图论 网络流 Adding-the-maximum-flow arc 增量网络流 区间枚举,猴子语言+网络流 最小费用最大流 最大流最小割定理 摧毁伞兵 最大流最小割定理 泥地 图论 最短路径 Dijkstra+heap 昂贵的聘礼 最短路变形 树中任意点对最短路和 Bellman_ford 货率 限制长度最短路，负环判连通，点权变边权，改变正负号 表达式求值 算法优先算法求表达式的值 词法分析与算法优先算法，集合运算：差集，并集，交集 矩阵乘法 线段覆盖数量 矩阵构造,nlogn矩阵乘法 2-SAT XOR AND OR 变量逻辑表达式可满足性 钥匙开门，二分+2-SAT判定 枚举 两维枚举，一维用二分 实数二分 0/1分数规划 剔除k个后分式最大 最优比率生成树，二分逼近 最优比率生成树，迭代算法 环的最大平均长度，bellman_ford判负环 环的最大平均长度，SPFA判负环 字符串 Power String 枚举+kmp判定，最长公共子串 铺砖，KMP好题 后缀数组，最长公共子串 后缀数组，最长不相交子串 后缀数组，取出字典序最小的序列 后缀数组，分三段，分别倒转，字典序最小 AC自动机实现多串匹配