河南大学ACM常用算法介绍及模板

目录

一、数学问题.....................................................................4

1.精度计算一一大数阶乘....................................................4

2.精度计算——乘法（大数乘小数）...........................................4

3.精度计算——乘法（大数乘大数）...........................................5

4.精度计算一一加法.........................................................6

5.精度计算——减法..........................................................7

6.精度计算一一除法约分.....................................................8

7.任意进制转换.............................................................11

8.最大公约数、最小公倍数..................................................11

9.组合序列.................................................................12

lO.Ronberg算法计算积分....................................................14

11.行列式计算..............................................................14

12.求排列组合数............................................................15

二、计算几何....................................................................15

1.叉乘法求任意多边形面积...................................................15

2.求三角形面积.............................................................16

3.求多边形重心.............................................................17

4.两矢量间角度.............................................................17

5.两点距离（2D、3D）......................................................18

6.射向法判断点是否在多边形内部............................................18

7.判断点是否在线段上.......................................................19

8.判断两线段是否相交......................................................20

9.判断线段与直线是否相交..................................................21

10.点到线段最短距离.......................................................21

11.求两直线的交点..........................................................22

12.判断一个封闭图形是凹集还是凸集.........................................23

13.Graham扫描法寻找凸包..................................................24

三、数论........................................................................27

1.x的二进制长度...........................................................27

2.返回x的二进制表示中从低到高的第i位....................................27

3.模取幕运算（反复平方法求数的幕）........................................27

4.求解模线性方程..........................................................29

5.求解模线性方程组（中国余数定理）..........................................29

6.筛法素数产生器...........................................................31

7.判断一个数是否素数......................................................32

8.初等数论里的欧拉公式：..................................................32

9.数的分解.................................................................35

10.关于数的阶乘............................................................36

11.母函数..................................................................37

12.特殊的数................................................................39

13.组合公式...............................................................40

14.置换群与Polya定理.....................................................40

2008

河南大学

/

四、图论........................................................................43

1.深度优先搜索............................................................43

2.边分类算法..............................................................45

3.连通性..................................................................45

4.Kosaraju算法求强连通分支...............................................46

5.无向图的割顶和桥.......................................................50

6.欧拉图..................................................................52

1）消圈法（逐步插入回路法）.......................................53

2）Fleury算法（能不走桥就不走桥）：................................55

7.最小生成树...............................................................60

l）.Prim算法（邻接矩阵，无优化）：.................................60

2）.Prim算法（邻接表+Heap优先队列优化）：.........................61

3）Kruskal算法：...................................................65

8.Dijkstra算法求单源最短路径...............................................67

1）.邻接矩阵，无优化..............................................67

2）.邻接链表，用优先队列（STL）优化..............................70

9.Bellman-ford算法求单源最短路径............................................72

10.Floyd-Warshall算法求每对节点间最短路径...................................74

五、最大流......................................................................75

1.最大流算法（Ford-Fulkerson）.........................................................................................75

2.最大二分匹配（最大流算法）............................................76

3.最大二分匹配（匈牙利算法）............................................78

4.最佳二分匹配（KM算法）...............................................79

5.最小路径覆盖（最大流算法）.............................................83

6.最小路径覆盖（匈牙利算法）............................................85

7.关于匹配................................................................86

六、排序/查找...................................................................87

1.快速排序.................................................................87

2.希尔排序.................................................................88

3.选择法排序...............................................................88

4.二分查找.................................................................89

七.数据结构....................................................................90

1.并查集..................................................................90

2.串的匹配（KMP算法）：.................................................95

3.字典树（字符串的储存与查找）：..........................................96

4.二叉堆（用二叉堆排序及构建优先队列）..................................98

5.二叉查找树（可作为优先队列）..........................................100

6.红黑树.................................................................104

7.树状数组...............................................................111

1）.一维数组代码（子段和）：.....................................112

2）.二维数组代码（子阵和）：.....................................113

8.线段树.................................................................114

9.归并树.................................................................118

10.后缀数组（SuffixArray）....................................................................................................121

2

A.博弈问题例题分析..........................................................124

例1.POJ1740ANewStoneGame.............................................................................................124

例2.MIPT100NimGame—whoisthewinner?.......................................................................125

例3.POJ1704GeorgiaandBob..................................................................................................126

例4,pojl067取石子游戏......................................................126

例4的另种解法：...........................................................127

单堆博弈问题：.............................................................128

九.其它算法...................................................................129

1.LCS算法...............................................................129

2.背包问题...............................................................130

3.回溯法.................................................................133

4.RMQ问题的ST算法....................................................134

5.最近公共祖先（LCA）问题..............................................136

1）.RMQ求法.....................................................137

2）.Tarjan的脱机（离线）算法.....................................137

6.扫描线.................................................................141

十.杂谈.......................................................................144

I.国际象棋..................................................................144

2.STL常用结构简单用法.....................................................144

3.图的度序列..............................................................147

4.数学的转化..............................................................147

2008

河南大学

/

一、数学问题

1.精度计算一一大数阶乘

语法：intresult=factorial(intn);

参数：

n：n的阶乘

返回值：阶乘结果的位数

注意：

本程序直接输出n!的结果，需要返回结果请保留longa[]

需要math,h

源程序：

intfactorial(intn)

(

longa[10000];

inti,j,1,c,m=0,w;

a[0]=l;

for(i=l;i<=n;i++)

(

c=0;

for(j=0;j<=m;j++)

(

a[j]=a[j]*i+c;

c=a[j]/10000;

a[j]=a[j]%10000;

)

if(c>0){m++;a[m]=c;}

w=m*4+logl0(a[m])+l;

printfC/\n%ld/，,a[m]);

for(i=m-l;i>=0;i-)printf(〃％4.41d〃，a[i]);

returnw;

2.精度计算一一乘法(大数乘小数)

语法:mult(charc[],chart[],intm);

参数：

c[]：被乘数，用字符串表示，位数不限

t□:结果，用字符串表示

m：乘数，限定10以内

4

返回值：null

注意：

需要string,h

源程序：

voidmult(charc[],chart[],intm)

(

inti,1,k,flag,add=0;

chars[100];

l=strlen(c);

for(i=0;i<l;i++)

s[『iT]=c[i],O';

for(i=0;i<l;i++)

(

k=s[i]*m+add;

if(k>=10){s[i]=k%10;add=k/10;flag=l;}else{s[i]=k;flag=0;add=0;}

)

if(flag){l=i+l;s[i]=add;}elsel=i;

for(i=0;i<l;i++)

t[l-l-i]=s[i]+,0*;

)

3.精度计算一一乘法(大数乘大数)

#include<iostream>

#include<sstream>

#include<vector>

usingnamespacestd;

intcount(strings)

(

intcount=0;

for(inti=0;i<s.length();i++)

if(s[i]==03

count++;

elsebreak;

returncount;

}

stringmuling(stringsi,strings2)

(

stringcheng(sl.length()+s2.length。，'O');

for(intn2=s2.length()-1;n2>=0;n2一)

if(s2[n2])

for(intnl=sl.length()-1,n=n2+sl.length();nl>=0;—nl,—n)

2008

河南大学

inttemp=(sl[nl]-'O')*(s2[n2]」O');

cheng[nT]=char(cheng[nT]+(cheng[n]+temp-'O')/10);

cheng[n]=char((cheng[n]+temp-，O')%10+'O');

)

if(count(cheng)==cheng.length())

return〃0〃；

returncheng.substr(cheng.find_first_not_ofCO'));

)

intmain()

(

for(stringsi,s2;cin>>sl»s2;)

cout<<muling(sl,s2)«endl;

return0;

)

4.精度计算一一加法

#include<sstream>

#include<iostream>

usingnamespacestd;

stringsum(stringsi,strings2)

(

if(sl.length()<s2.lengthO)

(

stringtemp=si;

sl=s2;

s2=temp;

)

for(intnl=sl.length()-1,n2=s2.length()-1;nl>=0;nl一,n2一)

(

si[nl]=char(si[nl]+(n2>=0?s2[n2]-'O':0));

if(sl[nl]-0'>=10)

(

si[nl]=char((si[nl]-'O')%10+'O');

if(nl)

sl[nl-l]++;〃想想为什么？如果不是十进制呢？

else

sl="I*+sl;

)

)

returnsi;

)

intmainO

6

for(stringsi,s2;cin>>sl»s2;)

cout«sum(sl,s2)<<endl;

return0;

)

5.精度计算一一减法

#include<sstream>

#include<iostream>

usingnamespacestd;

boolcompare(stringsi,strings2)

(

if(si.length()<s2.length())

returntrue;

if(si.length()==s2.length())

for(inti=0;i<sl.length();i++)

(

if(si[i]<s2[i])

returntrue;

}

returnfalse;

}〃===—===—=

stringsubing(stringsi,strings2)

(

boolsign=0;

if(sl==s2)

return〃0〃;〃所以有0-0结果仍正确！

if(compare(si,s2))

(

stringtemp=si;

sl=s2;

s2=temp;

sign=l;

)

for(intnl=sl.length()-1,n2=s2.length()-1;nl>=0;nl—,n2一)

(

si[nl]=char(si[nl]-(n2>=0?s2[n2]->:0));

if(sl[nl]<，0，)

(

si[nl]+=10;

si[nl-1]一;

)

}

if(sign)

2008

河南大学

/

return'+sl.substr(si.find_first_not_ofCO'));

returnsi.substr(si.find_first_not_of(*O'));

)

//=========================================================

intmain()

(

for(stringsi,s2;cin>>sl>>s2;)

cout«subing(sl,s2)<<endl;

return0;

6.精度计算一一除法约分

#include<iostream>

#include<sstream>

usingnamespacestd;

〃===========================

typedefstructData

(

stringsi,s2;

}Data;

〃两正的大数比较大小前者大返回1相等返回0后者大返回T

intMoreThan(stringsi,strings2)

(

if(sl.length()>s2.lengthO)

return1;

if(sl.length()<s2.lengthO)

return-1;

inti;

for(i=0;i<sl.lengthO；i++)

(

if(sl[i]!=s2[i])

(

if(sl[i]>s2[i])

return1;

else

return-1;

)

}

return0;

}

〃=============大数减法============

stringOpsitionSub(stringsi,strings2)

}

//******************以下是添力口的代码**************************************

〃二二二=二大数除法================

Datachu(stringsi,strings2)//chu的si是结果s2余数

(

Datad;

boolsign=false,signl=false;

if(sl[0]==-)

(

sign=!sign;

signl=true;

si.erase(si.begin());

}

if(s2[0]==-)

(

sign=!sign;

s2.erase(s2.begin());

)

if(MoreThan(sl,s2)==0)

(

//cout«，，equal，/«endl;

d.sl=(sign?〃T〃：〃l〃)；

d.s2=〃0〃；

returnd;

}

if(MoreThan(sl,s2)==~1)

(

d.si=〃0〃；

d.s2=(signl?"-"："〃)+sl;

returnd;

}

intl=s2.length();

stringtemps=sl.substr(0,1);

for(inti=0;i<=sl.length()-1;i++)

(

inttemp=0;

while(MoreThan(temps,s2)!=-l)

(

temps=0psitionSub(temps,s2);

temp++;

)

d.sl+=，O'+temp;

if(i!=sl.length()-l)

temps+=sl[i+1];

2008

河南大学

/

intas=temps.find_first_not_ofCO');

if(as==-l)

(

stringsi;

temps=si;

}

else

temps二temps,substr(as);

}

d.s2=(temps,length()?temps:〃O〃)；

d.si=d.si.substr(d.si.find_first_not_of('O'));

if(sign&&d.si.length())

d.si='+d.si;

if(signl&&d,s2.length()&&d.s2!="0")

d.s2='+d.s2;

returnd;

)

stringhcf(stringsi,strings2)〃求最大公约数

(

stringr;

while(s2!=//0/z)

(

r=chu(sl,s2).s2;

sl=s2;

s2=r;

)

return(si);

)

voiddiv(string&si,string&s2)〃约分

(

strings=hcf(si,s2);

sl=chu(sl,s).si;

s2=chu(s2,s).si;

)

intmain()〃测试

stringsi,s2;

while(cin»sl»s2)

div(sl,s2);

cout<<sl«，z，z«s2<<endl

}

)

10

7.任意进制转换

语法：conversion(charsi[],chars2[],longdl,longd2);

参数：

s[]：原进制数字，用字符串表示

s2[]：转换结果，用字符串表示

dl：原进制数

d2：需要转换到的进制数

返回值：null

注意：

高于9的位数用大写‘A'〜'Z'表示，2〜16位进制通过验证

源程序：

voidconversion(chars[],chars2[],longdl,longd2)

{

longi,j,t,num;

charc;

num=0;

for(i=0;s[i]!=,\0,;i++)

(

if(s[i]<='9'&&s[i]>='O')t=elset=s[i]-，A*+10;

num二num*dl+t;

)

i=0;

while(1)

(

t=num%d2;

if(t<=9)s2[i]=t+'O';elses2[i]=t+'A'TO;

num/=d2;

if(num==0)break;

i++；

)

for(j=0;j<i/2;j++)

{c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}

s2[i+l]=\0';

8.最大公约数、最小公倍数

语法：resulet=hcf(inta,intb)、result=lcd(inta,intb)

参数：

a：inta,求最大公约数或最小公倍数

b：intb,求最大公约数或最小公倍数

返回值：返回最大公约数(hcf)或最小公倍数(led)

注意：

led需要连同hcf使用

2008

河南大学

源程序：

inthcf(inta,intb)

(

intr=0;

while(b!=0)

(

r=a%b;

a=b;

b=r;

)

return(a);

)

led(intu,intv,inth)

{

return(u*v/h);

)

9.组合序列

语法：mofn(intm,intnl,intml,int*a,inthead)

参数：

m：组合数C的上参数

nl：组合数C的下参数

ml：组合数C的上参数，递归之用

*a：1〜n的整数序列数组

head：头指针

返回值：null

注意：

*a需要自行产生

初始调用时,m=mKhead=0

调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);

源程序：

voidm_of_n(intm,intnl,intml,int*a,inthead)

(

inti,t;

if(ml<0ml>nl)return;

if(ml==nl)

(

for(i=0;i<m;i++)cout«a[i]<<，*;//输出序列

cout<<，\n;

return;

)

m_of_n(m,nl-1,ml,a,head);//递归调用

t=a[head];a[head]=a[nl-l+head];a[nl-l+head]=t;

m_of_n(m,nl-1,ml-1,a,head+1);//再次递归调用

t=a[head];a[head]=a[nl-l+head];a[nl-l+head]=t;

}

〃回溯法(2)============

#include<iostream>

#include<vector>

usingnamespacestd;

intmain()

(

intn,r;

while(cin»n»r)

(

vector<int>res(r+1);

res[O]=O;

res[l]=l;

intm=l;

intci=l;

while(m)

(

if(res[m]<=n­(r-m))

(

if(m==r)

(

cout<<〃第〃<<ci++<<〃组：〃；

for(inti=l;i<=r;i++)

cout«res[i]<</z，z;

cout<<endl;

res[m]++;

)

else

(

m++;

res[m]=res[m-l]+l;

)

)

else

(

m——;

res[m]++；

)

)

return0;

}

2008

河南大学

/

lO.Ronberg算法计算积分

doublerectangle(doublea,doubleb,函数f())

(

doublew=b-a,sumNew=w*(f(a)+f(b))/2,sum01e=0;

for(intn=l;abs(sumNew-sumOld)>=le-4;n*=2)

sum01d=sumNew;

sumNew=0;

for(inti=0;i<n;i++)

sumNew+=f(a+w*(i+0.5)/n);

sumNew*=w/n;

)

returnsumNew;

)

11.行列式计算

语法：result=js(ints[][],intn)

参数：

行列式存储数组

n：行列式维数，递归用

返回值：行列式值

注意：

函数中常数N为行列式维度，需自行定义

源程序：

intjs(s,n)

ints[][N],n;

(

intz,j,k,r,total=0;

intb[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/

if(n>2)

(

for(z=0;z<n;z++)

(

for(j=0;j<n-l;j++)

for(k=0;k<n-l;k++)

if(k>=z)b[j][k]=s[j+l][k+l]：elseb[j][k]=s[j+l][k];

if(z%2==0)r=s[0][z]*js(b,n-l);/*递归调用*/

elser=(-l)*s[0][z]*js(b,n-l);

total=total+r;

)

)

elseif(n==2)

total=s[0][0]*s[l][l]-s[0][l]*s[l][0]

14

returntotal;

}

12.求排列组合数

m：排列组合的上系数

n：排列组合的下系数

返回值：排列组合数

注意：符合数学规则：m<=n

源程序：

longlongA(longlongn,longlongm)

(

longlongres=l;

for(inti=0;i<m;i++,n一)

res*二n;

returnres;

}

longlongC(longlongn,longlongm)

(

inti;

longlongres=l;

for(inti=0;i<m;i++)

res=res*(n-i)/(i+1);〃不能写res*=(n-i)/(i+l)

returnres;

)

二、计算几何

1.叉乘法求任意多边形面积

语法：resu1t=po1ygonarea(Point"polygon,intN);

参数：

"polygon：多变形顶点数组

N：多边形顶点数目

返回值：多边形面积

注意：

支持任意多边形，凹、凸皆可

多边形顶点输入时按顺(逆)时针顺序排列

源程序：

typedefstruct{

doublex,y;

}Point;

doublepolygonarea(Point*polygon,intN)

inti,j;

河南大学

j=(i+1)%N;

area+=polygon[i].x*polygon[j].y;

area-=polygon[i].y*polygon[j].x;

}

area/=2;

return(area<0?-area:area);

2.求三角形面积

语法：result=area3(floatxl,floatyl,floatx2,floaty2,floatx3,floaty3);

参数：

xl〜3：三角形3个顶点x坐标

yl~3：三角形3个顶点y坐标

返回值：三角形面积

注意：

需要math.h

源程序：

floatarea3(floatxl,floatyl,floatx2,floaty2,floatx3,floaty3)

(

doublea,b,c,p,s;

a=sqrt((xl-x2)*(xl-x2)+(yl-y2)*(yl-y2));

b=sqrt((xl-x3)*(xl-x3)+(yl-y3)*(yl-y3));

c=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));

p=(a+b+c)/2;

s=sqrt(p*(p-a)*(p-b)*(p-c));

returns;

)

方法II：

■Area(A,B^C)=1/2*(TAB)X(TAC)

XhX.YbYTI/

I*Vn/£

以上同阿是有同曲叔(有他饭》!

故任意多边形面积为(可能为负)：

A=sigma(Ai)<i=l...N>

即：Am*口:—|/2

ti=l...N

16

3.求多边形重心

三角形的重心是：

X=(xl+x2+x3)/3,Y=(yl+y2+y3)/3

但不能推广为：

Sigma(xi)/N.sigma(yi)/N(i=l...N)???

分析：

如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。

但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的!

稍微改一改，改成加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形,

其质量就是该三角形的面积(有向面积！)，一一这就是权！

可得：

■C=slgma(Af*Ct)/A

■CI=Centrold(/\OP.P+“

■=+个+个%])/3

■C■党区个科+个Pi.iM个PiX个

4.两矢量间角度

语法：result=angle(doublexl,doubleyl,doublex2,doubley2);

参数：

x/yl~2：两矢量的坐标

返回值：两的角度矢量

注意：

返回角度为弧度制，并且以逆时针方向为正方向

需要math,h

源程序：

MefinePI3.1415926

doubleangle(doublexl,doubleyl,doublex2,doubley2)

doubledtheta,thetal,theta2;

thetal=atan2(yl,xl);

theta2=atan2(y2,x2);

dtheta=theta2-thetal;〃说明：以逆时针方向为正方向

while(dtheta>PI)

dtheta-=PI*2;

while(dtheta<-PI)

dtheta+=PI*2;

return(dtheta);

}

2008

河南大学

5.两点距离(2D、3D)

语法：result=distance_2d(floatxl,floatx2,floatyl,floaty2);

参数：

x/y/zl〜2：各点的x、y、z坐标

返回值：两点之间的距离

注意：

需要m