ACM 算法模板

1、ACM Standard Code LibraryHuang WeiComputer Science and EngineeringAssociation of ProgramingInformation Engineering CollegeHangzhou Dianzi UniversityApril, 2007ACM 算法模板集Contents一. 常用函数与STL二. 重要公式与定理1.Fibonacci Number2.Lucas Number3.Catalan Number4.Stirling Number(Second Kind)5.Bell Number6.Stirlings

2、Approximation7.Sum of Reciprocal Approximation8.Young Tableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三. 大数模板四. 数论算法1.Greatest Common Divisor最大公约数2.Prime素数判断3.Sieve Prime素数筛法4.Module Inverse模逆元 5.Extended Euclid扩展欧几里德算法6.Modular Linear Equation模线性方程(同余方程)7.Chinese Remainder Theor

3、em中国余数定理五. 图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径(Bellman-ford算法)4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.最大二分图匹配(匈牙利算法)六. 几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标七. 专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配(KMP算法)13

4、.全排列,全组合第一章 常用函数和STL一. 常用函数#includeintgetchar(void);/读取一个字符,一般用来去掉无用字符char*gets(char*str);/读取一行字符串#includevoid*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*

5、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);#include/求反正弦,arg-1,1,返回值-pi/2,+pi/2doubleasin(doublearg);/求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值-1,1doublesin(doublearg);/求e的arg次方doubleexp(

6、doublearg);/求num的对数,基数为edoublelog(doublenum);/求num的根doublesqrt(doublenum);/求base的exp次方doublepow(doublebase,doubleexp);#include/初始化内存,常用来初始化数组void*memset(void*buffer,intch,size_tcount);memset(the_array,0,sizeof(the_array);/printf是它的变形,常用来将数据格式化为字符串intsprintf(char*buffer,constchar*format,.);sprintf(s,

7、%d%d,123,4567);/s=1234567/scanf是它的变形,常用来从字符串中提取数据intsscanf(constchar*buffer,constchar*format,.);Sample:charresult100=24hello,str100;intnum;sprintf(result,%d%s,num,str);/num=24;str=hello;/字符串比较,返回值0代表str10代表str1str2intstrcmp(constchar*str1,constchar*str2);二. 常用STL标准container概要vector大小可变的向量, 类似数组的用法,

8、容易实现删除list双向链表queue队列, empty(), front(), pop(), push()stack栈, empty(), top(), pop(), push()priority_queue 优先队列, empty(), top(), pop(), push()set集合map关联数组, 常用来作hash映射标准algorithm摘录for_each()对每一个元素都唤起（调用）一个函数find() 查找第一个能与引数匹配的元素replace() 用新的值替换元素, O(N)copy() 复制（拷贝）元素, O(N)remove()移除元素reverse()倒置元素sort

9、() 排序, O(N log(N)partial_sort() 部分排序binary_search()二分查找merge() 合并有序的序列, O(N)C+ String摘录copy() 从别的字符串拷贝empty() 判断字符串是否为空erase() 从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr() 取子字符串swap()交换字符串第二章 重要公式与定理1. Fibonacci Number0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 Fo

10、rmula:2. Lucas Number1, 3, 4, 7, 11, 18, 29, 47, 76, 123.Formula:3. Catalan Number1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012Formula:Application:1) 将 n + 2 边形沿弦切割成 n个三角形的不同切割数Sample:n = 2;n = 3;2) n + 1个数相乘, 给每两个元素加上括号的不同方法数Sample:n = 2; (1 (2 3),(1 2) 3)n = 3; (1 (2 (3 4), (1 (2 3)

11、4) , (1 2) (3 4), (1 (2 3) 4), (1 2) 3) 4)3) n 个节点的不同形状的二叉树数(严数据结构P.155)4) 从n * n 方格的左上角移动到右下角不升路径数Sample:n = 2;n = 3;4. Stirling Number(Second Kind)S(n, m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m 个无标号的盒子中, 要求无一为空, 其不同的方案数Formula:Special Cases:5. Bell Numbern 个元素集合所有的划分数Formula:6. Stirlings Approximation7

12、. Sum of Reciprocal ApproximationEulerGamma = 0.57721566490153286060651209;8. Young TableauYoung Tableau(杨式图表)是一个矩阵, 它满足条件:如果格子i, j没有元素, 则i+1, j也一定没有元素如果格子i, j有元素ai, j,则i+1, j要么没有元素, 要么ai+1, j ai, jYn代表n个数所组成的杨式图表的个数Formula:Sample:n = 3;9. 整数划分将整数n分成k份, 且每份不能为空, 任意两种分法不能相同1) 不考虑顺序for(intp=1;p=n;p+)f

13、or(inti=p;i=1;j-)dpij+=dpi-pj-1;coutdpnkendl;2) 考虑顺序dpij = dpi-kj-1; (k=1.i)3) 若分解出来的每个数均有一个上限mdpij = dpi-k j-1; (k=1.m)10. 错排公式11. 三角形内切圆半径公式12. 三角形外接圆半径公式13. 圆內接四边形面积公式14. 基础数论公式1) 模取幂 2) n的约数的个数若n满足, 则n的约数的个数为第三章 大数模板/*FunctionName :BigNumber*Description :BigNumbersHPC*Author :HuangWei*LastEdited

14、 :07.4.11*/#include#include#include#include#include#defineBASE1000/ 基数#defineDIG1100/ 存储usingnamespacestd;classBigNumberprivate:intdataDIG;/ 数据区intlen;/ 记录长度public:BigNumber()len=1;memset(data,0,sizeof(data);data0=1;BigNumber(int);/ 输入默认十进制BigNumber(char*);BigNumber(constBigNumber&);/ 类型转换BigNumber&

15、Num_BNum(int); /把一个整数转换成BigNumber型的BigNumber&Str_BNum(char*); /把一个字符串类型的转换成BigNumber型的intInt();stringStr();/ HPCBigNumber&Add(constBigNumber&);BigNumber&Sub(constBigNumber&);BigNumber&Mul(constBigNumber&);BigNumber&Div(int);BigNumber&Mod(int);BigNumber&operator=(constBigNumber&);intBigger(constBigNu

16、mber&)const;BigNumberoperator+(constBigNumber&);BigNumberoperator-(constBigNumber&);BigNumberoperator*(constBigNumber&);BigNumberoperator/(int);BigNumberoperator%(int);BigNumber&operator+=(constBigNumber&);BigNumber&operator-=(constBigNumber&);BigNumber&operator*=(constBigNumber&);BigNumber&operator

17、/=(int);BigNumber&operator%=(int);BigNumber&BigNumber:Num_BNum(intb) len=1;memset(data,0,sizeof(data);data0=1;if(b0)datalen+=b%BASE;b/=BASE;return*this;BigNumber&BigNumber:Str_BNum(char*sb)intt=0,d=1,b=0,slen=strlen(sb),i;len=1;memset(data,0,sizeof(data);data0=1;if(sb0=-)data0=-1,b=1;for(i=slen-1;i=

18、b;i-)while(t=BASE|dBASE)datalen+=t%BASE;t/=BASE;d=10;t+=(sbi-0)*d;d*=10;while(t0)datalen+=t%BASE;t/=BASE;return*this;intBigNumber:Int()istringstreamsin;intv;sin.str(this-Str();sinv;returnv; /这个函数的用法还是第一次看到，没看懂stringBigNumber:Str()inti,base_len=0;ostringstreamsout;if(len=1)sout0;/soutendl;returnsout.

19、str();if(data00)sout-;sout1)base_len+;i/=10;for(i=len-2;i0;i-)sout.width(base_len);sout.fill(0);soutdatai;/soutNum_BNum(b);BigNumber:BigNumber(char*sb)this-Str_BNum(sb);/ -1abBigNumber:BigNumber(constBigNumber&b)len=b.len;memcpy(data,b.data,sizeof(data);intBigNumber:Bigger(constBigNumber&b)constinti

20、,flag;if(data0=1&b.data0=1)flag=1;elseif(data0=1&b.data0=-1)return1;elseif(data0=-1&b.data0=1)return-1;elseflag=-1;if(lenb.len)returnflag;elseif(len=b.len)for(i=len-1;i0;i-)if(dataib.datai)returnflag;if(i=0)return0;return-flag; /比较函数BigNumber&BigNumber:Add(constBigNumber&b)inti;if(data0*b.data0!=1)d

21、ata0=-data0;Sub(b);data0=-data0;return*this;len=lenb.len?len:b.len;for(i=1;i=BASE)datai+1+;datai-=BASE;if(datai0)len=i+1;return*this; /加上b这个大数BigNumber&BigNumber:Sub(constBigNumber&b)inti;if(data0*b.data0!=1)data0=-data0;Add(b);data0=-data0;return*this;len=lenb.len?len:b.len;for(i=1;ilen;i+)datai-=b

22、.datai;if(datai0)datai+1-;datai+=BASE;if(datalen0)for(i=0;i=len;i+)datai=-datai;for(i=1;ilen;i+)if(datai0)datai+1-;datai+=BASE;while(datalen-1=0)len-;return*this;BigNumber&BigNumber:Mul(constBigNumber&b)BigNumberbt;inti,j,up;inttemp,temp1;bt.data0=data0*b.data0;for(i=1;ilen;i+)up=0;for(j=1;j=BASE)te

23、mp1=temp%BASE;up=temp/BASE;bt.datai+j-1=temp1;elseup=0;bt.datai+j-1=temp;if(up!=0)bt.datai+j-1=up;bt.len=i+j;while(bt.databt.len-1=0)bt.len-;*this=bt;return*this;BigNumber&BigNumber:Div(intb)BigNumberbt;inti,down=0;if(b=1;i-)bt.datai=(datai+down*BASE)/b;down=datai+down*BASE-bt.datai*b;bt.len=len;whi

24、le(bt.databt.len-1=0)bt.len-;*this=bt;return*this;BigNumber&BigNumber:Mod(intb)inttemp=0,up=0,i;for(i=len-1;i=1;i-)temp=datai;temp+=up*BASE;up=temp%b;if(data0Add(b);BigNumber&BigNumber:operator-=(constBigNumber&b)returnthis-Sub(b);BigNumber&BigNumber:operator*=(constBigNumber&b)returnthis-Mul(b);Big

25、Number&BigNumber:operator/=(intb)returnthis-Div(b);BigNumber&BigNumber:operator%=(intb)returnthis-Mod(b);第四章 数论算法1. Greatest Common Divisor最大公约数intGCD(intx,inty)intt;while(y0)t=x%y;x=y;y=t;returnx;2. Prime素数判断boolis_prime(intu)if(u=0|u=1)returnfalse;if(u=2)returntrue;if(u%2=0)returnfalse;for(inti=3;

26、i=sqrt(u);i+=2)if(u%i=0)returnfalse;returntrue;3. Sieve Prime素数筛法constintM=1000;/M:sizeboolmarkM;/true:primenumbervoidsieve_prime()memset(mark,true,sizeof(mark);mark0=mark1=false;for(inti=2;i=sqrt(M);i+)if(marki)for(intj=i*i;j 0/上式等价于二元一次方程ax ny = bvoidmodular_linear_equation(inta,intb,intn)intd,x,y

27、,x0;d=extended_euclid(a,n,x,y); if(b%d=0)x0=(x*(b/d)%n; /x0 : basic solutionintans=n;for(inti=0;id;i+)ans=(x0+i*(n/d)%n;coutansendl;elsecoutnosolution0,且w中任意两个数互质intchinese_remainder(intb,intw,intlen)inti,d,x,y,m,n;x=0;n=1;for(i=0;ilen;i+)n*=wi;for(i=0;ilen;i+)m=n/wi;d=extended_euclid(wi,m,x,y);x=(x

28、+y*m*bi)%n;return(n+x%n)%n;第五章 图论算法1. 最小生成树(Kruscal算法)/*FunctionName:最小生成树(Kruscal算法)*Description:ZJU1203Swordfish O(E*LogE)*/#include#include#include#includeusingnamespacestd;structstruct_edgesintbv,tv;/bv起点tv终点doublew;/权值;struct_edgesedges10100;/边集structstruct_adoublex;doubley;struct_aarr_xy101;in

29、tpoint101,n,e;/n顶点数,e边数(注意是无向网络)doublesum;intkruscal_f1(intpoint,intv)inti=v;while(pointi0)i=pointi;returni;boolUDlesser(struct_edgesa,struct_edgesb)returna.wb.w;voidkruscal()/只需要准备好n，e，递增的边集edges即可使用intv1,v2,i,j;for(i=0;in;i+)pointi=0;i=j=0;while(jn-1∈k=0;while(n!=0)sum=0;k+;for(i=0;iarr_xyi.xar

30、r_xyi.y;e=0;for(i=0;in;i+)/从0开始计数for(j=i+1;jn;j+)/注意是无向网络if(i=j)continue;edgese.bv=i;edgese.tv=j;edgese.w=sqrt(arr_xyi.x-arr_xyj.x)*(arr_xyi.x-arr_xyj.x)+(arr_xyi.y-arr_xyj.y)*(arr_xyi.y-arr_xyj.y);e+;sort(edges,edges+e,UDlesser);/得到一个递增的边集，注意是从0开始计数kruscal();printf(Case#%d:n,k);/coutCase#k:n;if(n!=0)printf(n);2. 最小生成树(Prim算法)/*FunctionName:最小生成树(Prim算法)*Description:ZJU1203Swordfish O(N2)*/#include#include#includeusingnamespacestd;doublesum,arr_list101101,min;inti,j,k=0,n;structstruct_afloatx;floaty;struct_aarr_xy101;structstruct_bintpoint;floatlowcost;st