ACM算法模板集WisKey免费模板~~~ACMStandardCodeLibraryHuangWeiSoftwareEngineeringComputerandSoftwareCollegeHangzhouDianziUniversityOctober,2008-1-ACM算法模板集WisKeyACM算法模板集Contents一.常用函数与STL二.重要公式与定理1.FibonacciNumber2.LucasNumber3.CatalanNumber4.StirlingNumber(SecondKind)5.BellNumber6.Stirling'sApproximation7.SumofReciprocalApproximation8.YoungTableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三.大数模板，字符读入四.数论算法1.GreatestCommonDivisor最大公约数2.Prime素数判断3.SievePrime素数筛法4.ModuleInverse模逆元5.ExtendedEuclid扩展欧几里德算法6.ModularLinearEquation模线性方程(同余方程)7.ChineseRemainderTheorem中国余数定理(互素与非互素)8.EulerFunction欧拉函数9.Farey总数9.Farey序列构造10.Miller_Rabbin素数测试，Pollard_rho因式分解五.图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径(Bellman-ford算法)-2-ACM算法模板集WisKey4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.最大匹配(Hungary，HopcroftKarp算法)12.带权二分图最优匹配(KM算法)13.强连通分量(Kosaraju算法)14.强连通分量(Gabow算法)15.无向图割边割点和双连通分量16.最小树形图O(N^3)17.最小树形图O(VE)六.几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标4.三角形几个重要的点七.专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配(KMP算法)13.全排列,全组合14.二维线段树15.稳定婚姻匹配16.后缀数组17.左偏树18.标准RMQ-ST19.度限制最小生成树20.最优比率生成树(0/1分数规划)21.最小花费置换22.区间K大数-3-ACM算法模板集WisKey23.LCA-RMQ-ST24.LCA–Tarjan25.指数型母函数26.指数型母函数(大数据)27.AC自动机(字典树+KMP)28.FFT(大数乘法)29.二分图网络最大流最小割30.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数(Burnside引理)34.三分法求函数波峰35.单词计数，DFA自动机，Trie图(完全AC自动机)36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基39.LCSubsequenceO(N^2/logN)40.伸展树41.Treap42.0/1分数规划K约束43.表达式求值44.乘除法博弈,Wythoff博弈45.状态压缩的积木型DP46.解一般线性方程组(消元法)47.块状链表48.FactorOracle-4-ACM算法模板集WisKey第一章常用函数和STL一.常用函数#include<stdio.h>intgetchar(void);//读取一个字符,一般用来去掉无用字符char*gets(char*str);//读取一行字符串#include<stdlib.h>void*malloc(size_tsize);//动态内存分配,开辟大小为size的空间voidqsort(void*buf,size_tnum,size_tsize,int(*compare)(constvoid*,constvoid*));//快速排序Sample:intcompare