上海交通大学ACM算法模板gai

ACM算法模板集-PAGE\*MERGEFORMAT#-ACM算法模板集Contents一.常用函数与STL重要与定理FibonacciNumberLucasNumberCatalanNumberStirlingNumber（SecondKind）BellNumberStirling'sApproximationSumofReciprocalApproximationYoungTableau整数划分错排公式三角形内切圆半径公式三角形外接圆半径公式圆内接四边形面积公式基础数论公式大数模板，字符读入数论算法GreatestCommonDivisor最大公约数Prime素数判断SievePrime素数筛法ModuleInverse模逆元ExtendedEuclid扩展欧几里德算法ModularLinearEquation模线性方程（同余方程）ChineseRemainderTheorem中国余数定理（互素丁非互素）EulerFunction欧拉函数Farey总数Farey序歹U构造Miller_Rabbin素数测试，Pollard_rho因式分解图论算法最小生成树（Kruscal算法）最小生成树（Prim算法）单源最短路径（Bellman-ford算法）单源最短路径（Dijkstra算法）全源最短路径（Folyd算法）拓扑排序网络预流和最大流网络最小费用最大流网络最大流（高度标号预流推进）最大团二分图最大匹配（匈牙利算法）带权二分图最优匹配（KM算法）强连通分量（Kosaraju算法）强连通分量（Gabow算法）无向图割边割点和双连通分量最小树形图O（M3）最小树形图O（VE）几何算法几何模板球面上两点最短距离三点求圆心坐标三角形几个重要的点专讨论树状数组字典树后缀树线段树并查集二义堆逆序数（归并排序）树状DP欧拉路八数码高斯消元法字符申匹配（KMP算法）全排列，全组合二维线段树稳定婚姻匹配后缀数组左偏树RMQ-ST度限制最小生成树最优比率生成树（0/1分数）最小花费置换区间K大数LCA-RMQ-STLCA-Tarjan指数型母函数指数型母函数（大数据）单词前缀树（字典树+KMP）FFT（大数乘法）二分图网络最大流最小割混合图欧拉回路无源汇上下界网络流二分图最小点权覆盖带约束的轨道计数（Burnside引理）三分法求函数波峰单词计数，矩阵乘法字符申和数值hash滚动队列，前向星表示法最小点基，最小权点基第一章常用函数和STL常用函数//读取一个字符，一般用来去掉无用字符//读取一行字符串//动态内存分配，开辟大小为size的空间#includeintgetchar(void);char*gets(char*str);#includevoid*malloc(size_tsize);voidqsort(void*buf,size_tnum,size_tsize,int(*compare)(constvoid*,constvoid*));〃快速排序Sample:intcompare_ints(constvoid*a,constvoid*b)(int*argl=(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);#include//求反正弦,argG[-1,1],返回值C[-pi/2,+pi/2]doubleasin(doublearg);返回值c[-1,1]//求正弦，arg为弧度，弧度=角度*Pi/180.0,doublesin(doublearg);//求e的arg次方doubleexp(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,"%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";代表str1>str2//字符串比较，返回值<0代表str10intstrcmp(constchar*str1,constchar*str2);二.常用STL[标准container概要］vector大小可变的向量，类似数组的用法，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()排序,O(Nlog(N))partial_sort()部分排序binary_search()二分查找merge()合并有序的序列，O(N)[C++String摘录]copy()从别的字符串拷贝empty()判断字符串是否为空容易实现删除erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理FibonacciNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610Formula:F(0]二0;F[1]=1;F[il=F[i-1]+F[i-2]F[n]LucasNumber1,3,4,7,11,18,29,47,76,123...Formula:L|n]=CatalanNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012Formula:C(2n,n)C[n]=——Application:1)将n+2边形沿弦切割成n个三角形的不同切割数n=3;n+1个数相乘，给每两个元素加上括号的不同方法数Sample:n=2;(1(23)),((12)3)((1(23))4),n=3;(1(2(34))),(1((23)4)),((12)(34)),(((12)3)4)n个节点的不同形状的二叉树数(严《数据结构》P.155)从n*n方格的左上角移动到右下角不升路径数Sample:n=2;n=3;StirlingNumber(SecondKind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中，要求无一为空，其不同的

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

数Formula:0(m=0n(in,土)*(m-±1TH!SpecialCases:S(n,0|=0S(nf1)=1S(n,2)=2n11S(nf3j=—(3It-3#2n+3)S(nrii-1)=C2)S(n*n|=1BellNumbern个元素集合所有的划分数Formula:nB[n]=»Sm,1)i=0Stirling'sApproximationn!二V2jtn{—jSumofReciprocalApproximationEulerGamma=0.57721566490153286060651209;A1>—=lii(n)+EitJja^airinA;(ntco)i=l1YoungTableauYoungTableau(杨式图表)是一个矩阵，它满足条件：如果格子[i,j]没有元素，则[i+1,j]也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素，要么a[i+1,j]>a[i,j]Y[n]代表n个数所组成的杨式图表的个数Formula:Y[l]=1；Y[2]=2；Y[n]=Y[n-1]+(n-1)*Y|n-2];(n>2)Sample:n=3;232整数划分将整数n分成k份，且每份不能为空，任意两种分法不能相同不考虑顺序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];cout<0;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()(printf("%d",Len==0?0:Data[Len-1]);for(inti=Len-2;i>=0;i--)for(intj=Base/10;j>0;j/=10)printf("%d",Data[i]/j%10);});xnum::xnum(charS[])(intI,J;Data[Len=0]=0;J=1;for(I=strlen(S)-1;I>=0;I--)(Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=0;)if(Data[Len]>0)Len++;)intcompare(constxnum&A,constxnum&B)(intI;if(A.Len!=B.Len)returnA.Len>B.Len?1:-1;for(I=A.Len-1;I>=0&&A[I]==B[I];I--);if(I<0)return0;returnA[I]>B[I]?1:-1;)xnumoperator+(constxnum&A,constxnum&B)(xnumR;intI;intCarry=0;for(I=0;I0;I++)(if(I0&&R[R.Len-1]==0)R.Len--;returnR;)xnumoperator*(constxnum&A,constintB)(intI;if(B==0)return0;xnumR;hugeintCarry=0;for(I=0;I0;I++)(if(I0;J++)(if(J=R.Len)R[R.Len++]=Carry%Base;elseR[I+J]=Carry%Base;Carry/=Base;}}returnR;}xnumoperator/(constxnum&A,constintB)(xnumR;intI;hugeintC=0;for(I=A.Len-1;I>=0;I--)(C=C*Base+A[I];R[I]=C/B;C%=B;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;returnR;}//divxnumoperator/(constxnum&A,constxnum&B)(intI;xnumR,Carry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I--)(Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left0&&R[R.Len-1]==0)R.Len--;returnR;}//modxnumoperator%(constxnum&A,constxnum&B)(intI;xnumR,Carry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I--)(Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left0&&R[R.Len-1]==0)R.Len--;returnCarry;}istream&operator>>(istream&In,xnum&V)(charCh;for(V=0;In>>Ch;)(V=V*10+(Ch-'0');if(cin.peek()<=returnIn;}ostream&operator<<(ostream&Out,constxnum&V){intI;Out<<(V.Len==0?0:V[V.Len-1]);for(I=V.Len-2;I>=0;I--)for(intJ=Base/10;J>0;J/=10)Out<=n-m+1;i--)sum=sum*i;(i=1;i<=m;i++)sum=sum/i;MAXN9999returnsum;}#defineDLEN4classBigNum(private:inta[1000];//可以控制大数的位数intlen;//大数长度public:BigNum(){len=1;memset(a,0,BigNum(BigNum(constint);BigNum(constconstBigNum&);BigNum&sizeof(a));}char*);operator=(constBigNum&);BigNumoperator+(constBigNum&)const;BigNumoperator-(constBigNum&)const;BigNumoperator*(constBigNum&)const;BigNumoperator/(constint&)const;BigNumoperatorA(constint&)const;intoperator%(constint&)const;booloperator>(constBigNum&T)const;voidprint();};BigNum::BigNum(constwhile(d>MAXN){c=d-(d/(MAXN+a[len++]=d;}intb)(intc,d=b;len=0;memset(a,0,1))*(MAXN+1);d=d/(MAXN+1);a[len++]=c;}sizeof(a));char*s)(intt,k,index,l,i;sizeof(a));l=strlen(s);len=l/DLEN;BigNum::BigNum(constmemset(a,0,if(l%DLEN)len++;index=0;for(i=l-1;i>=0;i-=DLEN){t=0;k=i-DLEN+1;if(k<0)k=0;for(intj=k;j<=i;j++)t=t*10+s[j]-'0';a[index++]=t;}}BigNum::BigNum(constBigNum&T):len(T.len){inti;memset(a,0,sizeof(a));for(i=0;ilen?T.len:len;for(i=0;iMAXN)(t.a[i+1]++;t.a[i]-=MAXN+1;})if(t.a[big]!=0)t.len=big+1;elset.len=big;returnt;}BigNumBigNum::operator-(constBigNum&T)const(inti,j,big;boolflag;BigNumt1,t2;if(*this>T)(t1=*this;t2=T;flag=0;}else(t1=T;t2=*this;flag=1;}big=t1.len;for(i=0;ii)t1.a[j--]+=MAXN;t1.a[i]+=MAXN+1-t2.a[i];}elset1.a[i]-=t2.a[i];}t1.len=big;while(t1.a[len-1]==0&&t1.len>1)(t1.len--;big--;}if(flag)t1.a[big-1]=0-t1.a[big-1];returnt1;}BigNumBigNum::operator*(constBigNum&T)const(BigNumret;inti,j,up;inttemp,temp1;for(i=0;iMAXN)(temp1=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+1);ret.a[i+j]=temp1;}else(up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;}ret.len=i+j;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}BigNumBigNum::operator/(constint&b)const(BigNumret;inti,down=0;for(i=len-1;i>=0;i--)(ret.a[i]=(a[i]+down*(MAXN+1))/b;down=a[i]+down*(MAXN+1)-ret.a[i]*b;}ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}intBigNum::operator%(constint&b)const(inti,d=0;for(i=len-1;i>=0;i--)(d=((d*(MAXN+1))%b+a[i])%b;)returnd;)BigNumBigNum::operatorA(constint&n)const(BigNumt,ret(1);if(n<0)exit(-1);if(n==0)return1;if(n==1)return*this;intm=n;while(m>1)(t=*this;inti;for(i=1;i<<1<=m;i<<=1)(t=t*t;)m-=i;ret=ret*t;if(m==1)ret=ret*(*this);)returnret;)boolBigNum::operator>(constBigNum&T)const(intIn;if(len>T.len)returntrue;elseif(len==T.len)(ln=len-1;while(a[ln]==T.a[ln]&&ln>=0)ln--;if(ln>=0&&a[ln]>T.a[ln])returntrue;elsereturnfalse;)elsereturnfalse;)voidBigNum::print()(inti;cout<=0;i--)(cout.width(DLEN);cout.fill('0');cout<do(ret=ret*10+ch-)while((ch=getchar())<=returnok;)//带负数intget_val(int&ret)(ret=0;while(((ch=getchar())>charch;'9'||ch<'0');'0';'9'&&ch>='0');charch;boolneg=false;'9'||ch<'0')&&ch!='-');if(ch=='-')(neg=true;while((ch=getchar())>'9'||ch<'0');)do(ret=ret*10+ch-'0';)while((ch=getchar())<='9'&&ch>='0');ret=(neg?-ret:ret);returnok;)//读取整数，可判EOF和EOLconstinteof=-1;constinteol=-2;intget_val(int&ret)(ret=0;charch;while(((ch=getchar())>'9'||ch<'0')&&ch!=EOF);if(ch==EOF)returneof;do(ret=ret*10+ch-'0';)while((ch=getchar())<='9'&&ch>='0');if(ch=='\n')returneol;returnok;)//读取浮点数intget_val(double&ret)(ret=0;doublebase=0.1;charch;booldot=false,neg=false;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');if(ch=='-')(neg=true;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');)do(if(ch=='.')(dot=true;continue;)if(dot)(ret+=(ch-'0')*base;base*=0.1;)elseret=ret*10+(ch-'0');)while(((ch=getchar())<='9'&&ch>='0')||ch=='.');ret=(neg?-ret:ret);returnok;)第四章数论算法GreatestCommonDivisor最大公约数intGCD(intx,inty)(intt;while(y>0)(t=x%y;x=y;y=t;)returnx;)Prime素数判断boolis_prime(intu)(if(u==0||u==1)returnfalse;if(u==2)returntrue;if(u%2==0)returnfalse;for(inti=3;i<=sqrt(u);i+=2)if(u%i==0)returnfalse;returntrue;)SievePrime素数筛法constintM=1000;//M:sizeboolmark[M];//true:primenumbervoidsieve_prime()(memset(mark,true,sizeof(mark));mark[0]=mark[1]=false;for(inti=2;i<=sqrt(M);i++)(if(mark[i])(for(intj=i*i;j0//上式等价于二元一次方程axny=bvoidmodular_linear_equation(inta,intb,intn){intd,x,y,x0,gcd;//可以减少扩展欧几里德溢出的可能gcd=GCD(a,n);if(b%gcd!=0){cout<<"nosolution"<0,且w[]中任意两个数互质intchinese_remainder(intb[],intw[],intlen){inti,d,x,y,m,n;ret=0;n=1;for(i=0;i1)(ans*=n-1;}returnans;}Farey总数//求MAX以内所有Farey的总数constintMAX=1000100;intn;boolnum[1100];//sqrt(MAX)intprime[1100],total;__int64f[MAX],inc[MAX];voidcal_prime()(inti,j;memset(num,false,sizeof(num));total=0;for(i=2;i<1100;i++)(if(!num[i])(prime[total++]=i;j=i+i;while(j<1100)(num[j]=true;j+=i;}}}}voidcal_farey()(inti,j,k;inc[1]=1;for(i=2;in||y1+y2>n)return;make_farey_seq(x1,y1,x1+x2,y1+y2);total++;farey[0][total]=x1+x2;farey[1][total]=y1+y2;make_farey_seq(x1+x2,y1+y2,x2,y2);)intmain()(intt;scanf("%d%d",&n,&t);total=1;farey[0][1]=0;farey[1][1]=1;make_farey_seq(0,1,1,1);farey[0][total+1]=1;farey[1][total+1]=1;total++;while(t--)(scanf("%d",&k);if(k>total)puts("NoSolution");elseprintf("%d/%d\n",farey[0][k],farey[1][k]);}}Miller_Rabbin素数测试，Pollard_rho因式分解typedef__int64I64;constchar*pformat="%I64d";I64big_rand(I64m)(I64x=rand();x*=rand();if(x<0)x=-x;returnx%=m;}//x*y%nI64mod_mul(I64x,I64y,I64n)(if(x==0||y==0)return0;return(((x&1)*y)%n+(mod_mul(x>>1,y,n)<<1)%n)%n;}//xAy%nI64mod_exp(I64x,I64y,I64n)(I64ret=1;while(y)(if(y&1)ret=mod_mul(ret,x,n);x=mod_mul(x,x,n);y>>=1;}returnret;}boolMiller_Rabbin(I64n)(//O(times*(logN)A3)I64i,j,x,m,k;if(n==2)returntrue;if(n<2||!(n&1))returnfalse;m=n-1;k=0;while(!(m&1))m>>=1,k++;//binaryscanfor(i=0;i<4;i++)(//testtimesx=big_rand(n-2)+2;x=mod_exp(x,m,n);if(x==1)continue;for(j=0;j=k)returnfalse;}returntrue;/*lrjP.218for(i=0;i<20;i++)(x=big_rand(n-2)+2;if(mod_exp(x,n-1,n)!=1)returnfalse;}returntrue;*/}I64gcd(I64x,I64y)(if(x>y)std::swap(x,y);while(x)(I64t=y%x;y=x;x=t;}returny;}I64func(I64x,I64m)(return(mod_mul(x,x,m)+1)%m;}I64Pollard(I64n)(if(Miller_Rabbin(n))returnn;if(!(n&1))return2;I64i,x,y,ret;i=1;while(true)(x=i++;y=func(x,n);ret=gcd(y-x,n);while(ret==1)(x=func(x,n);y=func(func(y,n),n);ret=gcd((y-x+n)%n,n)%n;}if(00)putchar('');printf(pformat,factor[i]);}puts("");}constI64lim=100000;intmain()(I64n,t,i;srand((unsigned)time(NULL));scanf(pformat,&t);while(t--)(scanf(pformat,&n);if(Miller_Rabbin(n))puts("Prime");else(if(!(n&1))puts("2");else(for(minfac=3;minfac=lim)(I64rn=sqrt(1.0*n);if(rn*rn==n)(minfac=rn;cal_factor(rn);}else(minfac=n;cal_factor(n);}}printf(pformat,minfac);puts("");}}}}第五章图论算法1.最小生成树（Kruscal算法）/***FunctionName:最小生成树（Kruscal算法）***********************Description:**/ZJU1203SwordfishO(E*LogE)**********************#include#include#include#includeusingnamespacestd;structstruct_edges{intbv,tv;//bv起点tv终点doublew;//权值);struct_edgesedges[10100];//边集structstruct_a{doublex;doubley;);struct_aarr_xy[101];intpoint[101],n,e;//n顶点数，e边数(注意是无向网络)doublesum;intkruscal_f1(intpoint[],intv){inti=v;while(point[i]>0)i=point[i];returni;)boolUDlesser(struct_edgesa,struct_edgesb){returna.w>n;k=0;while(n!=0){sum=0;k++;for(i=0;i>arr_xy[i].x>>arr_xy[i].y;e=0;for(i=0;i>n;if(n!=0)printf("\n");}}2.最小生成树(Prim算法)/*************************FunctionName:*Description:最小生成树(Prim算法)ZJU1203SwordfishO(NA2)**/#include#include#includeusingnamespacestd;doublesum,arr_list[101][101],min;inti,j,k=0,n;structstruct_a{floatx；floaty;};struct_aarr_xy[101];structstruct_b{intpoint;floatlowcost;};顶点的邻接矩阵也是从0开始struct_bclosedge[101];voidprim(intn)//prim需要准备：n顶点数arr_list[][]计数{inti,j,k;k=0;for(j=0;j>n;while(n!=0){sum=0;k++;for(i=0;i>arr_xy[i].x>>arr_xy[i].y;for(i=0;i>n;if(n!=0)printf("\n");}}3.单源最短路径(Bellman-ford算法)structnode{inte,v;node(inta=0,intb=0):e(a),v(b){}};vector>path;intn,p,q;intdist[1000100];/*SPFA(ShortestPathFasterAlgorithm)Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算返回值为false,说明队列不为空，存在负权环*/boolSPFA(){inti,j,k,now,l;nodenext;bitset<1000100>vis;queueSQ;memset(dist,-1,sizeof(dist));SQ.push(1);vis[1]=true;dist[1]=0;for(i=0;i<=n;i++){l=SQ.size();if(l==0)break;while(l--){now=SQ.front();SQ.pop();vis[now]=false;for(j=path[now].size()-1;j>=0;j--){next=path[now][j];if(dist[next.e]==-1||dist[next.e]>dist[now]+next.v){dist[next.e]=dist[now]+next.v;if(!vis[next.e]){SQ.push(next.e);vis[next.e]=true;}}}}}returnSQ.empty();}4.单源最短路径(Dijkstra算法)/*************************FunctionName:*Description:************************/intmatrix[200][200],n;其值为边的权值单源最短路径（Dijkstra算法）贪心，O（M2）,不能有负权//matrix[][],30000表示无限大，即无边.否则为有边voidDijkstra(intx,inty)//起点Vx终点Vy{inti,j,k,