ACM模板浙大版.docx
《ACM模板浙大版.docx》由会员分享，可在线阅读，更多相关《ACM模板浙大版.docx（184页珍藏版）》请在冰点文库上搜索。
ACM模板浙大版
目录
一．几何4
1.1注意4
1.2几何公式4
1.3多边形6
1.4多边形切割9
1.5浮点函数10
1.6面积15
1.7球面16
1.8三角形17
1.9三维几何19
1.10凸包27
1.11网格28
1.12圆28
1.13整数函数30
二．组合33
2.1组合公式33
2.2排列组合生成33
2.3生成gray码35
2.4置换（polya）35
2.5字典序全排列36
2.6字典序组合36
三．结构37
3.1并查集37
3.2堆38
3.3线段树39
3.4子段和44
3.5子阵和45
四．数论45
4.1阶乘最后非0位45
4.2模线性方程组46
4.3素数47
4.4欧拉函数49
4.5定积分计算（Romberg）49
4.6多项式求根（牛顿法）51
4.7周期性方程（追赶法）52
五．图论53
5.1NP搜索53
5.1.1最大团53
5.1.2最大团（n<64）（faster）54
5.2连通性56
5.2.1无向图关键点（dfs邻接阵）56
5.2.2无向图关键边（dfs邻接阵）57
5.2.3无向图的块（bfs邻接阵）58
5.2.4无向图连通分支（dfs/bfs邻接阵）59
5.2.5有向图强连通分支（dfs/bfs邻接阵）60
5.2.6有向图最小点基（邻接阵）62
5.3匹配62
5.3.1二分图最大匹配（hungary邻接表）62
5.3.2二分图最大匹配（hungary邻接阵）63
5.3.3二分图最大匹配（hungary正向表）63
5.3.4二分图最佳匹配（kuhn_munkras邻接阵）64
5.3.5一般图匹配（邻接表）65
5.3.6一般图匹配（邻接阵）66
5.3.7一般图匹配（正向表）67
5.4网络流68
5.4.1最大流（邻接阵）68
5.4.2上下界最大流（邻接阵）69
5.4.3上下界最小流（邻接阵）69
5.4.4最大流无流量（邻接阵）70
5.4.5最小费用最大流（邻接阵）71
5.5应用72
5.5.1欧拉回路（邻接阵）72
5.5.2树的前序表转化72
5.5.3树的优化算法73
5.5.4拓扑排序（邻接阵）75
5.5.5最佳边割集75
5.5.6最佳点割集76
5.5.7最小边割集78
5.5.8最小点割集79
5.5.9最小路径覆盖80
5.6支撑树81
5.6.1最小生成树（kruskal邻接表）81
5.6.2最小生成树（kruskal正向表）82
5.6.3最小生成树（prim+binary_heap邻接表）83
5.6.4最小生成树（prim+binary_heap正向表）85
5.6.5最小生成树（prim+mapped_heap邻接表）86
5.6.6最小生成树（prim+mapped_heap正向表）87
5.6.7最小生成树（prim邻接阵）88
5.6.8最小树形图（邻接阵）89
5.7最短路径90
5.7.1最短路径（单源bellman_ford邻接阵）90
5.7.2最短路径（单源dijkstra+bfs邻接表）91
5.7.3最短路径（单源dijkstra+bfs正向表）91
5.7.4最短路径（单源dijkstra+binary_heap邻接表）92
5.7.5最短路径（单源dijkstra+binary_heap正向表）93
5.7.6最短路径（单源dijkstra+mapped_heap邻接表）94
5.7.7最短路径（单源dijkstra+mapped_heap正向表）95
5.7.8最短路径（单源dijkstra邻接阵）96
5.7.9最短路径（多源floyd_warshall邻接阵）97
六．应用98
6.1Joseph问题98
6.2N皇后构造解98
6.3布尔母函数99
6.4第k元素100
6.5幻方构造100
6.6模式匹配（kmp）101
6.7逆序对数102
6.8字符串最小表示102
6.9最长公共单调子序列103
6.10最长子序列104
6.11最大子串匹配105
6.12最大子段和106
6.13最大子阵和107
七．其它108
7.1大数（只能处理正数）108
7.2分数113
7.3矩阵115
7.4线性方程组117
7.5线性相关119
7.6日期120
一．几何
1.1注意
1.注意舍入方式（0.5的舍入方向）;防止输出-0.
2.几何题注意多测试不对称数据.
3.整数几何注意xmult和dmult是否会出界;
符点几何注意eps的使用.
4.避免使用斜率;注意除数是否会为0.
5.公式一定要化简后再代入.
6.判断同一个2*PI域内两角度差应该是
abs（a1-a2）pi+pi-beta;
相等应该是
abs（a1-a2）pi+pi-eps;
7.需要的话尽量使用atan2,注意:
atan2（0,0）=0,
atan2（1,0）=pi/2,atan2（-1,0）=-pi/2,atan2（0,1）=0,atan2（0,-1）=pi.
8.crossproduct=|u|*|v|*sin（a）
dotproduct=|u|*|v|*cos（a）
9.（P1-P0）x（P2-P0）结果的意义:
正:
在顺时针（0,pi）内
负:
在逆时针（0,pi）内
0:
,共线,夹角为0或pi
10.误差限缺省使用1e-8!
1.2几何公式
三角形:
1.半周长P=（a+b+c）/2
2.面积S=aHa/2=absin（C）/2=sqrt（P（P-a）（P-b）（P-c））
3.中线Ma=sqrt（2（b^2+c^2）-a^2）/2=sqrt（b^2+c^2+2bccos（A））/2
4.角平分线Ta=sqrt（bc（（b+c）^2-a^2））/（b+c）=2bccos（A/2）/（b+c）
5.高线Ha=bsin（C）=csin（B）=sqrt（b^2-（（a^2+b^2-c^2）/（2a））^2）
6.内切圆半径r=S/P=asin（B/2）sin（C/2）/sin（（B+C）/2）
=4Rsin（A/2）sin（B/2）sin（C/2）=sqrt（（P-a）（P-b）（P-c）/P）
=Ptan（A/2）tan（B/2）tan（C/2）
7.外接圆半径R=abc/（4S）=a/（2sin（A））=b/（2sin（B））=c/（2sin（C））
四边形:
D1,D2为对角线,M对角线中点连线,A为对角线夹角
1.a^2+b^2+c^2+d^2=D1^2+D2^2+4M^2
2.S=D1D2sin（A）/2
（以下对圆的内接四边形）
3.ac+bd=D1D2
4.S=sqrt（（P-a）（P-b）（P-c）（P-d））,P为半周长
正n边形:
R为外接圆半径,r为内切圆半径
1.中心角A=2PI/n
2.内角C=（n-2）PI/n
3.边长a=2sqrt（R^2-r^2）=2Rsin（A/2）=2rtan（A/2）
4.面积S=nar/2=nr^2tan（A/2）=nR^2sin（A）/2=na^2/（4tan（A/2））
圆:
1.弧长l=rA
2.弦长a=2sqrt（2hr-h^2）=2rsin（A/2）
3.弓形高h=r-sqrt（r^2-a^2/4）=r（1-cos（A/2））=atan（A/4）/2
4.扇形面积S1=rl/2=r^2A/2
5.弓形面积S2=（rl-a（r-h））/2=r^2（A-sin（A））/2
棱柱:
1.体积V=Ah,A为底面积,h为高
2.侧面积S=lp,l为棱长,p为直截面周长
3.全面积T=S+2A
棱锥:
1.体积V=Ah/3,A为底面积,h为高
（以下对正棱锥）
2.侧面积S=lp/2,l为斜高,p为底面周长
3.全面积T=S+A
棱台:
1.体积V=（A1+A2+sqrt（A1A2））h/3,A1.A2为上下底面积,h为高
（以下为正棱台）
2.侧面积S=（p1+p2）l/2,p1.p2为上下底面周长,l为斜高
3.全面积T=S+A1+A2
圆柱:
1.侧面积S=2PIrh
2.全面积T=2PIr（h+r）
3.体积V=PIr^2h
圆锥:
1.母线l=sqrt（h^2+r^2）
2.侧面积S=PIrl
3.全面积T=PIr（l+r）
4.体积V=PIr^2h/3
圆台:
1.母线l=sqrt（h^2+（r1-r2）^2）
2.侧面积S=PI（r1+r2）l
3.全面积T=PIr1（l+r1）+PIr2（l+r2）
4.体积V=PI（r1^2+r2^2+r1r2）h/3
球:
1.全面积T=4PIr^2
2.体积V=4PIr^3/3
球台:
1.侧面积S=2PIrh
2.全面积T=PI（2rh+r1^2+r2^2）
3.体积V=PIh（3（r1^2+r2^2）+h^2）/6
球扇形:
1.全面积T=PIr（2h+r0）,h为球冠高,r0为球冠底面半径
2.体积V=2PIr^2h/3
1.3多边形
#include
#include
#defineMAXN1000
#defineoffset10000
#defineeps1e-8
#definezero（x）（（（x）>0?
（x）:
-（x））#define_sign（x）（（x）>eps?
1:
（（x）<-eps?
2:
0））
structpoint{doublex,y;};
structline{pointa,b;};
doublexmult（pointp1,pointp2,pointp0）{
return（p1.x-p0.x）*（p2.y-p0.y）-（p2.x-p0.x）*（p1.y-p0.y）;
}
//判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线
intis_convex（intn,point*p）{
inti,s[3]={1,1,1};
for（i=0;is[_sign（xmult（p[（i+1）%n],p[（i+2）%n],p[i]））]=0;
returns[1]|s[2];
}
//判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线
intis_convex_v2（intn,point*p）{
inti,s[3]={1,1,1};
for（i=0;is[_sign（xmult（p[（i+1）%n],p[（i+2）%n],p[i]））]=0;
returns[0]&&s[1]|s[2];
}
//判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
intinside_convex（pointq,intn,point*p）{
inti,s[3]={1,1,1};
for（i=0;is[_sign（xmult（p[（i+1）%n],q,p[i]））]=0;
returns[1]|s[2];
}
//判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0
intinside_convex_v2（pointq,intn,point*p）{
inti,s[3]={1,1,1};
for（i=0;is[_sign（xmult（p[（i+1）%n],q,p[i]））]=0;
returns[0]&&s[1]|s[2];
}
//判点在任意多边形内,顶点按顺时针或逆时针给出
//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限
intinside_polygon（pointq,intn,point*p,inton_edge=1）{
pointq2;
inti=0,count;
while（ifor（count=i=0,q2.x=rand（）+offset,q2.y=rand（）+offset;iif（zero（xmult（q,p[i],p[（i+1）%n]））&&（p[i].x-q.x）*（p[（i+1）%n].x-q.x）returnon_edge;
elseif（zero（xmult（q,q2,p[i]）））
break;
elseif（xmult（q,p[i],q2）*xmult（q,p[（i+1）%n],q2）<-eps&&xmult（p[i],q,p[（i+1）%n]）*xmult（p[i],q2,p[（i+1）%n]）<-eps）
count++;
returncount&1;
}
inlineintopposite_side（pointp1,pointp2,pointl1,pointl2）{
returnxmult（l1,p1,l2）*xmult（l1,p2,l2）<-eps;
}
inlineintdot_online_in（pointp,pointl1,pointl2）{
returnzero（xmult（p,l1,l2））&&（l1.x-p.x）*（l2.x-p.x）}
//判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
intinside_polygon（pointl1,pointl2,intn,point*p）{
pointt[MAXN],tt;
inti,j,k=0;
if（!
inside_polygon（l1,n,p）||!
inside_polygon（l2,n,p））
return0;
for（i=0;iif（opposite_side（l1,l2,p[i],p[（i+1）%n]）&&opposite_side（p[i],p[（i+1）%n],l1,l2））
return0;
elseif（dot_online_in（l1,p[i],p[（i+1）%n]））
t[k++]=l1;
elseif（dot_online_in（l2,p[i],p[（i+1）%n]））
t[k++]=l2;
elseif（dot_online_in（p[i],l1,l2））
t[k++]=p[i];
for（i=0;ifor（j=i+1;jtt.x=（t[i].x+t[j].x）/2;
tt.y=（t[i].y+t[j].y）/2;
if（!
inside_polygon（tt,n,p））
return0;
}
return1;
}
pointintersection（lineu,linev）{
pointret=u.a;
doublet=（（u.a.x-v.a.x）*（v.a.y-v.b.y）-（u.a.y-v.a.y）*（v.a.x-v.b.x））
/（（u.a.x-u.b.x）*（v.a.y-v.b.y）-（u.a.y-u.b.y）*（v.a.x-v.b.x））;
ret.x+=（u.b.x-u.a.x）*t;
ret.y+=（u.b.y-u.a.y）*t;
returnret;
}
pointbarycenter（pointa,pointb,pointc）{
lineu,v;
u.a.x=（a.x+b.x）/2;
u.a.y=（a.y+b.y）/2;
u.b=c;
v.a.x=（a.x+c.x）/2;
v.a.y=（a.y+c.y）/2;
v.b=b;
returnintersection（u,v）;
}
//多边形重心
pointbarycenter（intn,point*p）{
pointret,t;
doublet1=0,t2;
inti;
ret.x=ret.y=0;
for（i=1;iif（fabs（t2=xmult（p[0],p[i],p[i+1]））>eps）{
t=barycenter（p[0],p[i],p[i+1]）;
ret.x+=t.x*t2;
ret.y+=t.y*t2;
t1+=t2;
}
if（fabs（t1）>eps）
ret.x/=t1,ret.y/=t1;
returnret;
}
1.4多边形切割
//多边形切割
//可用于半平面交
#defineMAXN100
#defineeps1e-8
#definezero（x）（（（x）>0?
（x）:
-（x））structpoint{doublex,y;};
doublexmult（pointp1,pointp2,pointp0）{
return（p1.x-p0.x）*（p2.y-p0.y）-（p2.x-p0.x）*（p1.y-p0.y）;
}
intsame_side（pointp1,pointp2,pointl1,pointl2）{
returnxmult（l1,p1,l2）*xmult（l1,p2,l2）>eps;
}
pointintersection（pointu1,pointu2,pointv1,pointv2）{
pointret=u1;
doublet=（（u1.x-v1.x）*（v1.y-v2.y）-（u1.y-v1.y）*（v1.x-v2.x））
/（（u1.x-u2.x）*（v1.y-v2.y）-（u1.y-u2.y）*（v1.x-v2.x））;
ret.x+=（u2.x-u1.x）*t;
ret.y+=（u2.y-u1.y）*t;
returnret;
}
//将多边形沿l1,l2确定的直线切割在side侧切割,保证l1,l2,side不共线
voidpolygon_cut（int&n,point*p,pointl1,pointl2,pointside）{
pointpp[100];
intm=0,i;
for（i=0;iif（same_side（p[i],side,l1,l2））
pp[m++]=p[i];
if（!
same_side（p[i],p[（i+1）%n],l1,l2）&&!
（zero（xmult（p[i],l1,l2））&&zero（xmult（p[（i+1）%n],l1,l2））））
pp[m++]=intersection（p[i],p[（i+1）%n],l1,l2）;
}
for（n=i=0;iif（!
i||!
zero（pp[i].x-pp[i-1].x）||!
zero（pp[i].y-pp[i-1].y））
p[n++]=pp[i];
if（zero（p[n-1].x-p[0].x）&&zero（p[n-1].y-p[0].y））
n--;
if（n<3）
n=0;
}
1.5浮点函数
//浮点几何函数库
#include
#defineeps1e-8
#definezero（x）（（（x）>0?
（x）:
-（x））structpoint{doublex,y;};
structline{pointa,b;};
//计算crossproduct（P1-P0）x（P2-P0）
doublexmult（pointp1,pointp2,pointp0）{
return（p1.x-p0.x）*（p2.y-p0.y）-（p2.x-p0.x）*（p1.y-p0.y）;
}
doublexmult（doublex1,doubley1,doublex2,doubley2,doublex0,doubley0）{
return（x1-x0）*（y2-y0）-（x2-x0）*（y1-y0）;
}
//计算dotproduct（P1-P0）.（P2-P0）
doubledmult（pointp1,pointp2,pointp0）{
return（p1.x-p0.x）*（p2.x-p0.x）+（p1.y-p0.y）*（p2.y-p0.y）;
}
doubledmult（doublex1,doubley1,doublex2,doubley2,doublex0,doubley0）{
return（x1-x0）*（x2-x0）+（y1-y0）*（y2-y0）;
}
//两点距离
doubledistance（pointp1,pointp2）{
returnsqrt（（p1.x-p2.x）*（p1.x-p2.x）+（p1.y-p2.y）*（p1.y-p2.y））;
}
doubledistance（doublex1,doubley1,doublex2,doubley2）{
returnsqrt（（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2））;
}
//判三点共线
intdots_inline（pointp1,pointp2,pointp3）{
returnzero（xmult（p1,p2,p3））;
}
intdots_inline（doublex1,doubley1,doublex2,doubley2,doublex3,doubley3）{
returnzero（xmult（x1,y1,x2,y2,x3,y3））;
}
//判点是否在线段上,包括端点
intdot_online_in（pointp,li
升级会员 