《上海交通大学ACM算法模板》由会员分享，可在线阅读，更多相关《上海交通大学ACM算法模板（90页珍藏版）》请在金锄头文库上搜索。
1、ACM 算法模板集Contents一.常用函数与STL二.重要公式与定理1.Fibonacci Number2.Lucas Number3.Catalan Number4.Stirling Number（Second Kind）5.Bell Number6.Stirlings Approximation7.Sum of Reciprocal Approximation8.Young Tableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆内接四边形面积公式14.基础数论公式三.大数模板，字符读入四.数论算法1.Greatest Common Divi
2、sor 最大公约数2.Prime素数判断3.Sieve Prime素数筛法4.Module Inverse 模逆元5.Extended Euclid扩展欧几里德算法6.Modular Linear Equation模线性方程（同余方程）7.Chinese Remainder Theorem中国余数定理（互素于非互素）8.Euler Function 欧拉函数9.Farey 总数9.Farey序列构造10.Miller_Rabbin 素数测试，Pollard_rho 因式分解五.图论算法1.最小生成树（Kruscal算法）2.最小生成树（Prim算法）3.单源最短路径（Bellman-ford算
3、法）4.单源最短路径（Dijkstra算法）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.树
4、状 DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配（KMP算法）13.全排列，全组合14.二维线段树15.稳定婚姻匹配16.后缀数组17.左偏树18.标准 RMQ-ST19.度限制最小生成树20.最优比率生成树（0/1分数规划）21.最小花费置换22.区 间 K 大数23.LCA-RMQ-ST24.LCA-Tarjan25.指数型母函数26.指数型母函数(大数据)27.单词前缀树(字典树+KMP)28.FFT(大数乘法)29.二分图网络最大流最小割30.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数(Burnside引理)34.三分法求函数波峰
5、35.单词计数，矩阵乘法36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基第一章常用函数和STL一.常用函数#include int getchar(void);读取一个字符:，一般用来去掉无用字符char*gets(char*str);读取一行字符串#include void*malloc(size_t size);动态内存分配，开辟大小为size的空间void qsort(void*bufz size_t num,size_t size,int(*compare)(const void*,constvoid*);快速排序Sample:int compare_i
6、nts(const void*a,const void*b)int*argl=(int*)a;int*arg2=(int*)b;if(*argl *arg2)return-1;else if(*argl=*arg2)return 0;else return 1;int array=-2,99,0,-743,2,3,4;int array_size=7;qsort(array,array_size,sizeof(int),comparejnts);#include 求反正弦，arge-l,1,返回值 -pi/2,+pi/2double asin(double arg);求正弦，arg为弧度,弧度
7、=角度*Pi/180.0,返回值e-1,1double sin(double arg);求e 的 arg次方double exp(double arg);求 num的对数，基数为edouble log(double num);求 num的根double sqrt(double num);求base的exp次方double pow(double base,double exp);#include 初始化内存，常用来初始化数组void*memset(void*buffer;int chz size_t count);memset(the_array,0,sizeof(the_array);prin
8、tf是它的变形，常用来将数据格式化为字符串int sprintf(char*buffer,const char*format,.);sprintf(s,%d%d,123,4567);/s=1234567Hscanf是它的变形，常用来从字符串中提取数据int sscanf(const char*buffer,const char format,.);Sample:char result100=24 hello,str100;int num;sprintf(result,%d%s”,numzstr);/num=24;str=,hello;字符串比较，返回值v 0代表strl 0代表strl st2
9、int strcmp(const char*strl,const char*str2);常用STL 标准container概要vectorlistqueuestackpriori ty_queuesetmap大小可变的向量，类似数组的用法，容易实现删除双向链表队列，empty()z front(),pop(),push()栈,empty(),top(),pop(),push()优先队列,empty(),top(),pop(),push()集合关联数组，常用来作hash映射标准algorithm摘录for_each()find()replace()copy()remove()reverse()s
10、ort()partial_sort()binary _search()merge()对每一个元素都唤起(调用)一个函数查找第一个能与引数匹配的元素用新的值替换元素，O(N)复制(拷 贝)元 素，O(N)移除元素倒置元素排序，O(N log(N)部分排序二分查找合并有序的序列，O(N)C+String 摘录copy()empty()从别的字符串拷贝判断字符串是否为空erase()find()insert()length()replace()substr()swap()从字符串移除元素查找元素插入元素字符串长度替换元素取子字符串交换字符串第二章重要公式与定理1.Fibonacci Number0,
11、1,1,2,3,5,8,13,21,34,55,89,144,233,377,610.Formula:F0=0;Fl=1；Fi=F i-ll+F i-2；pFn(i+V i)n-(i-V )1+275V5Lucas Number1,3,4,7,11,18,29,47z 76,123.Formula:Ln1+V5-1-7 53.Catalan Number1,2,5,14,42,132,429,1430z 4862,16796,58786,208012.Formula:Application:1）将n+2边形沿弦切割成n个三角形的不同切割数Sample:n=3;2)n+1 个数相乘，给每两个元素
12、加上括号的不同方法数Sample:n=2;(1(2 3),(1 2)3)n=3；(1(2(3 4),(1(2 3)4),(1 2)(3 4),(1(2 3)4),(1 2)3)4)3)n 个节点的不同形状的一叉树数(严 数据结构P.155)4)从 n*n 方格的左上角移动到右下角不升路径数Sample:4.Stirling Number(Second Kind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或 者 是n个有标号的球放到m个无标号的盒子中，要求无一为空，其不同的方案数Formula:0(m=0 or n m 之 1)S(n,m)=2 (T)，*C(m,i)*(m-i)nm
13、!=oSpecial Cases:S(n,0)=0S(n,1)=1S(n,2)=2n l-lS(n,3)=(3n-3w2n+3)6S(n,n-1)=C(nf 2)S(n,n)=15.Bell Numbern 个元素集合所有的划分数Formula:nBn=2s(n，*1=06.Stirlings Approximationn=怎G7.Sum of Reciprocal ApproximationEulerGamma=0.57721566490153286060651209;A 1 =lii(n)+EiilrGanma;(n-co)i=l 18.Young TableauYoung Tableau
14、(杨式图表)是一个矩阵，它满足条件：如果格子i,j没有元素，贝 盯 i+1,j也一定没有元素如果格子i,j有元素ai,j,则i+1,j要么没有元素,要么ai+l,j ai,jYn代 表 n 个数所组成的杨式图表的个数Formula:Yl=1;Y2=2;Yn=Y n-1+(n-1)*Yn-2;(n 2)9.整数划分将整数n 分 成 k 份，且每份不能为空，任意两种分法不能相同1)不考虑顺序for(int p=l;p=n;p+)for(int i=p;i=l;j-)dpiU+=dpi-pU-l;cout dpnk 0;V/=Base)DataLen+=V%Base;xnum(char S);xnu
15、m&operator=(const xnum&V)Len=V.Len;memcpy(Dataz V.Data,Len*sizeof*Data);return*this;int&operator(int Index)return DataIndex;int operator(int Index)const return DataIndex;void print()printf(%dzLen=0?0:Data Len-1);for(int i=Len-2;i=0;i)for(int j=Base/10;j0;j/=10)printf(%dzDatai/j%10);xnum:xnum(char S)
16、int I,J;DataLen=0=0;J=1;for(I=strlen(S)-l;I=0;I-)DataLen+=(SI-0)*J;J*=10;if(J=Base)J=1,Data+Len=0;if(DataLen 0)Len+;int compare(const xnum&A,const xnum&B)(int I;if(A.Len!=B.Len)return A.Len B.Len?1:-1;for(I=A.Len-1;I=0&AI=BI;I-);if(I BI?1 :-1;xnum operator+(const xnum&A,const xnum&B)xnum R;int I;int Carry=0;for(I=0;I A.Len 1 1 I 0;I+)if(I A.Len)Carry+=AI;if(I B.Len)Carry+=BI;RI=Carry%Base;Carry/=Base;R.Len=I;return R;xnum operator-(const xnum&A,const xnum&B)xnum R;int Carry=0;R.Len=A.Len;int I;f
