ACM算法模板

ACM算法模板集-1-ACM算法模板集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算法)4.单源最短路径(Dijkstra算法)ACM算法模板集-2-5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.二分图最大匹配(匈牙利算法)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大数23.LCA-RMQ-STACM算法模板集-3-24.LCA–Tarjan25.指数型母函数26.指数型母函数（大数据）27.单词前缀树（字典树+KMP）28.FFT（大数乘法）29.二分图网络最大流最小割30.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数(Burnside引理)34.三分法求函数波峰35.单词计数，矩阵乘法36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基八、学习专题1、著名的北邮acm训练队推荐50题2、ACM国际大学生程序设计竞赛题解（1-2）3、高手给的训练计划4、题目分类5、竞赛训练6、程序设计竞赛长期规划7、ACM竞赛之新人向导8、acmer必看的26个对acm态度9、上海交大ACM队长建议——谈谈ACM比赛中的代码能力10、JavainACM11、ACM训练方案12、杭电ACM题目分类ACM算法模板集-4-第一章常用函数和STL一.常用函数#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=1234567//scanf是它的变形,常用来从字符串中提取数据intsscanf(constchar*buffer,constchar*format,...);Sample:charresult[100]=24hello,str[100];intnum;sprintf(result,%d%s,num,str);//num=24;str=hello;ACM算法模板集-5-//字符串比较,返回值0代表str1str2,=0代表str1=str2,0代表str1str2intstrcmp(constchar*str1,constchar*str2);二.常用STL[标准container概要]vectorT大小可变的向量,类似数组的用法,容易实现删除listT双向链表queueT队列,empty(),front(),pop(),push()stackT栈,empty(),top(),pop(),push()priority_queueT优先队列,empty(),top(),pop(),push()setT集合mapkey,val关联数组,常用来作hash映射[标准algorithm摘录]for_each()对每一个元素都唤起（调用）一个函数find()查找第一个能与引数匹配的元素replace()用新的值替换元素,O(N)copy()复制（拷贝）元素,O(N)remove()移除元素reverse()倒置元素sort()排序,O(Nlog(N))partial_sort()部分排序binary_search()二分查找merge()合并有序的序列,O(N)[C++String摘录]copy()从别的字符串拷贝empty()判断字符串是否为空erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理1.FibonacciNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610…Formula:ACM算法模板集-6-2.LucasNumber1,3,4,7,11,18,29,47,76,123...Formula:3.CatalanNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012…Formula:Application:1)将n+2边形沿弦切割成n个三角形的不同切割数Sample:n=2;n=3;2)n+1个数相乘,给每两个元素加上括号的不同方法数Sample: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;ACM算法模板集-7-n=3;4.StirlingNumber(SecondKind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中,要求无一为空,其不同的方案数Formula:SpecialCases:5.BellNumbern个元素集合所有的划分数Formula:6.Stirling'sApproximation7.SumofReciprocalApproximationACM算法模板集-8-EulerGamma=0.57721566490153286060651209;8.YoungTableauYoungTableau(杨式图表)是一个矩阵,它满足条件:如果格子[i,j]没有元素,则[i+1,j]也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素,要么a[i+1,j]a[i,j]Y[n]代表n个数所组成的杨式图表的个数Formula:Sample:n=3;9.整数划分将整数n分成k份,且每份不能为空,任意两种分法不能相同1)不考虑顺序for(intp=1;p=n;p++)for(inti=p;i=n;i++)for(intj=k;j=1;j--)dp[i][j]+=dp[i-p][j-1];coutdp[n][k]endl;2)考虑顺序dp[i][j]=dp[i-k][j-1];(k=1..i)3)若分解出来的每个数均有一个上限mdp[i][j]=dp[i-k][j-1];(k=1..m)10.错排公式11.三角形内切圆半径公式ACM算法模板集-9-12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式1)模取幂2)n的约数的个数若n满足,则n的约数的个数为第三章大数模板typedefinthugeint;//应不大于,以防乘法时溢出constintBase=1000;constintCapacity=1000;structxnum{intLen;intData[Capacity];xnum():Len(0){}xnum(constxnum&V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}xnum(intV):Len(0){for(;V0;V/=Base)Data[Len++]=V%Base;}xnum(charS[]);xnum&operator=(constxnum&V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return*this;}int&operator[](intIndex){returnData[Index];}intoperator[](intIndex)const{returnData[Index];}voidprint(){ACM算法模板集-10-printf(%d,Len==0?0:Data[Len-1]);for(inti=Len-2;i=0;i--)for(intj=Base/10;j0;j/=10)printf(%d,D