ACM_算法模板集史上最完整收藏版223页全免费版

ACM算法模板集WisKey-1-免费模板~~~~~~~~~~~~ACMACMACMACMStandardStandardStandardStandardCodeCodeCodeCodeLibraryLibraryLibraryLibraryHuangWeiSoftwareEngineeringComputerandSoftwareCollegeHangzhouDianziUniversityOctober,2008ACM算法模板集WisKey-2-ACMACMACMACM算法模板集算法模板集算法模板集算法模板集ContentsContentsContentsContents一....常用函数与STLSTLSTLSTL二....重要公式与定理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算法)ACM算法模板集WisKey-3-4.单源最短路径(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大数ACM算法模板集WisKey-4-23.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.FactorOracleACM算法模板集WisKey-5-第一章第一章第一章第一章常用函数和常用函数和常用函数和常用函数和STLSTLSTLSTL一一一一....常用函数常用函数常用函数常用函数#includestdio.hintgetchar(void);//读取一个字符,一般用来去掉无用字符char*gets(char*str);//读取一行字符串#includestdlib.hvoid*malloc(size_tsize);//动态内存分配,开辟大小为size的空间voidqsort(void*buf,size_tnum,size_tsize,int(*compare)(constvoid*,constvoid*));//快速排序Sample:intcompare_ints(constvoid*a,constvoid*b){int*arg1=(int*)a;int*arg2=(int*)b;if(*arg1*arg2)return-1;elseif(*arg1==*arg2)return0;elsereturn1;}intarray[]={-2,99,0,-743,2,3,4};intarray_size=7;qsort(array,array_size,sizeof(int),compare_ints);#includemath.h//求反正弦,arg∈[-1,1],返回值∈[-pi/2,+pi/2]doubleasin(doublearg);//求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值∈[-1,1]doublesin(doublearg);//求e的arg次方doubleexp(doublearg);//求num的对数,基数为edoublelog(doublenum);//求num的根doublesqrt(doublenum);//求base的exp次方doublepow(doublebase,doubleexp);#includestring.h//初始化内存,常用来初始化数组void*memset(void*buffer,intch,size_tcount);memset(the_array,0,sizeof(the_array));//printf是它的变形,常用来将数据格式化为字符串intsprintf(char*buffer,constchar*format,...);sprintf(s,%d%d,123,4567);//s=1234567ACM算法模板集WisKey-6-//scanf是它的变形,常用来从字符串中提取数据intsscanf(constchar*buffer,constchar*format,...);Sample:charresult[100]=24hello,str[100];intnum;sprintf(result,%d%s,num,str);//num=24;str=hello;//字符串比较,返回值0代表str1str2,=0代表str1=str2,0代表str1str2intstrcmp(constchar*str1,constchar*str2);二二二二....常用常用常用常用STLSTLSTLSTL[[[[标准containercontainercontainercontainer概要]]]]vectorT大小可变的向量,类似数组的用法,容易实现删除listT双向链表queueT队列,empty(),front(),pop(),push()stackT栈,empty(),top(),pop(),push()priority_queueT优先队列,empty(),top(),pop(),push()setT集合mapkey,val关联数组,常用来作hash映射[[[[标准algorithmalgorithmalgorithmalgorithm摘录]]]]for_each()对每一个元素都唤起（调用）一个函数find()查找第一个能与引数匹配的元素replace()用新的值替换元素,O(N)copy()复制（拷贝）元素,O(N)remove()移除元素reverse()倒置元素sort()排序,O(Nlog(N))partial_sort()部分排序binary_search()二分查找merge()合并有序的序列,O(N)[C++[C++[C++[C++StringStringStringString摘录]]]]copy()从别的字符串拷贝empty()判断字符串是否为空erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串ACM算法模板集WisKey-7-第二章第二章第二章第二章重要公式与定理重要公式与定理重要公式与定理重要公式与定理1.FibonacciFibonacciFibonacciFibonacciNumberNumberNumberNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610…Formula:Formula:Formula:Formula:011211(15)(15)1152255iiinnnnnFFFFFF−−===+⎡⎤⎛⎞+−−+⎢⎥==⎜⎟⎜⎟⎢⎥⎝⎠⎣⎦2.2.2.2.LucasLucasLucasLucasNumberNumberNumberNumber1,3,4,7,11,18,29,47,76,123...Formula:Formula:Formula:Formula:151522nnnL⎛⎞⎛⎞+−=+⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠3.3.3.3.CatalanCatalanCatalanCatalanNumberNumberNumberNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012…Formula:Formula:Formula:Formula:110(2,)1*nnniniiCnnCatnCatCatCat−−−==+=∑Application:Application:Application:Application:1)将n+2边形沿弦切割成n个三角形的不同切割数Sample:n=2;n=3;2)n+1个数相乘,给每两个元素加上括号的不同方法数Sample:ACM算法模板集WisKey-8-n=2;(1(23)),((12)3)n=3;(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)3)n个节点的不同形状的二叉树数(严《数据结构》P.155)4)从n*n方格的左上角移动到右下角不升路径数Sample:n=2;n=3;4.4.4.4.StirlingStirlingStirlingStirlingNumber(SecondNumber(SecondNumber(SecondNumber(SecondKind)Kind)Kind)Kind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中,要求无一为空,其不同的方案数Formula:Formula:Formula:Formula:,1,11,0(0||)(1)nmnmnmmnmSSmSnm−−−=⎧⎨+×≥⎩,01(1)(,)()!minnmiSCmimim==−××−∑SpecialSpecialSpecialSpecialCases:Cases:Cases:Cases:,0,11,2,3,1,01211(3323)6(,2)1nnnnnnnnnnnSSSSSCnS−−===−=−×+==5.5.5.5.BellBel