ACM_算法模板.doc

1、程序设计协会 ACM 算法模板集 - 1 - ACM Standard Code Library Huang Wei Computer Science and Engineering Association of Programing Information Engineering College Hangzhou Dianzi University April, 2007 ACM 算法模板集 Contents 程序设计协会 ACM 算法模板集 - 2 - 一. 常用函数与 STL 二. 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catala

2、n Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirlings Approximation 7. Sum of Reciprocal Approximation 8. Young Tableau 9. 整数划分 10. 错排公式 11. 三角形内切圆半径公式 12. 三角形外接圆半径公式 13. 圆內接四边形面积公式 14. 基础数论公式 三. 大数模板 四. 数论算法 1. Greatest Common Divisor 最大公约数 2. Prime 素数判断 3. Sieve Prime 素数筛法 4. Module

3、 Inverse 模逆元 5. Extended Euclid 扩展欧几里德算法 6. Modular Linear Equation 模线性方程( 同余方程) 7. Chinese Remainder Theorem 中国余数定理 五. 图论算法 1. 最小生成树(Kruscal 算法) 2. 最小生成树(Prim 算法) 3. 单源最短路径(Bellman-ford 算法) 4. 单源最短路径(Dijkstra 算法) 5. 全源最短路径(Folyd 算法) 6. 拓扑排序 7. 网络预流和最大流 8. 网络最小费用最大流 9. 网络最大流(高度标号预流推进) 10. 最大团 11. 最大

4、二分图匹配(匈牙利算法) 六. 几何算法 程序设计协会 ACM 算法模板集 - 3 - 1. 几何模板 2. 球面上两点最短距离 3. 三点求圆心坐标 七. 专题讨论 1. 树状数组 2. 字典树 3. 后缀树 4. 线段树 5. 并查集 6. 二叉堆 7. 逆序数(归并排序) 8. 树状 DP 9. 欧拉路 10. 八数码 11. 高斯消元法 12. 字符串匹配(KMP 算法) 13. 全排列,全组合 第一章 常用函数和 STL 一. 常用函数 #include int getchar( void ); /读取一个字符, 一般用来去掉无用字符 程序设计协会 ACM 算法模板集 - 4 - c

5、har *gets( char *str ); /读取一行字符串 #include void * malloc( size_t size ); /动态内存分配, 开辟大小为 size 的空间 void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) ); /快速排序 Sample: int compare_ints( const void* a, const void* b ) int* arg1 = (int*) a; int* arg2 = (int*) b; if(

6、 *arg1 str2 程序设计协会 ACM 算法模板集 - 5 - int strcmp( const char *str1, const char *str2 ); 二. 常用 STL 标准 container 概要 vector 大小可变的向量, 类似数组的用法, 容易实现删除 list 双向链表 queue 队列, empty(), front(), pop(), push() stack 栈, empty(), top(), pop(), push() priority_queue 优先队列, empty(), top(), pop(), push() set 集合 map 关联数组

7、, 常用来作 hash 映射 标准 algorithm 摘录 for_each() 对每一个元素都唤起（调用）一个函数 find() 查找第一个能与引数匹配的元素 replace() 用新的值替换元素, O(N) copy() 复制（拷贝）元素, O(N) remove() 移除元素 reverse() 倒置元素 sort() 排序, O(N log(N) partial_sort() 部分排序 binary_search() 二分查找 merge() 合并有序的序列, O(N) C+ String 摘录 copy() 从别的字符串拷贝 empty() 判断字符串是否为空 erase() 从字

8、符串移除元素 find() 查找元素 insert() 插入元素 length() 字符串长度 replace() 替换元素 substr() 取子字符串 swap() 交换字符串 第二章 重要公式与定理 1. Fibonacci Number 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 Formula: 程序设计协会 ACM 算法模板集 - 6 - 2. Lucas Number 1, 3, 4, 7, 11, 18, 29, 47, 76, 123. Formula: 3. Catalan Number 1, 2,

9、 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012 Formula: 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) 4) , (1 2) (3 4), (1 (2 3) 4), (1 2) 3) 4) 3) n 个节点的不同形状的二叉树数(严数据结构P.155)

10、 4) 从 n * n 方格的左上角移动到右下角不升路径数 Sample: n = 2; 程序设计协会 ACM 算法模板集 - 7 - n = 3; 4. Stirling Number(Second Kind) S(n, m)表示含 n 个元素的集合划分为 m 个集合的情况数 或者是 n 个有标号的球放到 m 个无标号的盒子中, 要求无一为空, 其不同 的方案数 Formula: Special Cases: 5. Bell Number n 个元素集合所有的划分数 Formula: 6. Stirlings Approximation 7. Sum of Reciprocal Approx

11、imation 程序设计协会 ACM 算法模板集 - 8 - EulerGamma = 0.57721566490153286060651209; 8. Young Tableau Young Tableau(杨式图表)是一个矩阵, 它满足条件: 如果格子i, j没有元素, 则i+1, j也一定没有元素 如果格子i, j有元素 ai, j,则i+1, j要么没有元素, 要么 ai+1, j ai, j Yn代表 n 个数所组成的杨式图表的个数 Formula: Sample: n = 3; 9. 整数划分 将整数 n 分成 k 份, 且每份不能为空, 任意两种分法不能相同 1) 不考虑顺序 f

12、or(int p=1; p=b ;i-) while(t = BASE | d BASE) data len+ = t % BASE; t /= BASE; d = 10; t += (sbi-0) * d; d *= 10; while(t 0) data len+ = t % BASE; t /= BASE; return *this; int BigNumber:Int() 程序设计协会 ACM 算法模板集 - 12 - istringstream sin; int v; sin.str( this-Str() ); sin v; return v; /这个函数的用法还是第一次看到，没看

13、懂 string BigNumber:Str() int i,base_len=0; ostringstream sout; if(len = 1) sout 0 ;i-) sout.width(base_len); sout.fill(0); sout Str_BNum(sb); / -1 ab BigNumber:BigNumber(const BigNumber memcpy(data,b.data,sizeof(data); int BigNumber:Bigger(const BigNumber 程序设计协会 ACM 算法模板集 - 13 - if(data0 =1 else if(

14、data0 =1 else if(data0 =-1 else flag = -1; if(len b.len) return flag; else if(len = b.len) for(i=len-1; i0 ;i-) if(datai b.datai) return flag; if(i = 0) return 0; return -flag; /比较函数 BigNumber if(data0 * b.data0 != 1) data0 = -data0; Sub(b); data0 = -data0; return *this; len= len b.len ? len : b.len

15、; for(i=1; i= BASE) datai+1+; datai -= BASE; if(datai 0) len = i+1; return *this; /加上 b 这个大数 BigNumber if(data0 * b.data0 != 1) data0 = -data0; Add(b); data0 = -data0; return *this; 程序设计协会 ACM 算法模板集 - 14 - len= len b.len ? len : b.len; for(i=1; i=1 ;i-) temp = datai; temp += up * BASE; up = temp % b

16、; if(data0 Add(b); BigNumber BigNumber BigNumber BigNumber 第四章 数论算法 1. Greatest Common Divisor 最大公约数 int GCD(int x, int y) 程序设计协会 ACM 算法模板集 - 17 - int t; while(y 0) t = x % y; x = y; y = t; return x; 2. Prime 素数判断 bool is_prime(int u) if(u = 0 | u = 1) return false; if(u = 2) return true; if(u%2 = 0

17、) return false; for(int i=3; i 0) i = pointi; return i; bool UDlesser(struct_edges a, struct_edges b) return a.w arr_xyi.xarr_xyi.y; e=0; for(i=0; in; if(n != 0) printf(“n“); 2. 最小生成树(Prim 算法) /* * * * * * * Function Name : 最小生成树 (Prim 算法) * Description : ZJU 1203 Swordfish O(N2) 程序设计协会 ACM 算法模板集 -

18、22 - * * * * * */ #include #include #include using namespace std; double sum, arr_list101101, min; int i, j, k=0, n; struct struct_a float x; float y; ; struct_a arr_xy101; struct struct_b int point; float lowcost; ; struct_b closedge101; void prim(int n) /prim 需要准备： n 顶点数 arr_list顶点的邻接矩阵也是 从 0 开始计数

19、 int i,j,k; k=0; for(j=0; jn; while(n != 0) sum=0; k+; for(i=0; iarr_xyi.xarr_xyi.y; for(i=0; in; if(n!=0) printf(“n“); 3. 单源最短路径(Bellman-ford 算法) /* * * * * * * Function Name : 单源最短路径 (Bellman-ford 算法) * Description : 可允许有负权 程序设计协会 ACM 算法模板集 - 24 - * * * * * */ #include #define MAX 100 #define MAXN

20、UM 1000000 typedef struct graphnode int vexnum; /顶点数 int arcnum; /边数 int graMAXMAX; /图 Graph; Graph *G; /arc 数组中存储的第一个顶点到其他顶点的最短路径 /结果存在 dis 数组中 int disMAX; int arcMAXMAX; void bellman(Graph *G) int i,j; bool sign; for(i=0; i vexnum ;i+) disi=MAXNUM; dis1 = 0; sign = true; for(i=1; i vexnum ;i+) sig

21、n = false; for(j=0; j arcnum ;j+) if(dis arcj0 dis arcj0 + G-gra arcj0 arcj1 ) dis arcj1 =dis arcj0 + G-gra arcj0 arcj1 ; sign = true; return; 4. 单源最短路径(Dijkstra 算法) /* * * * * * * Function Name : 单源最短路径 (Dijkstra 算法) * Description : 贪心, O(N2), 不能有负权 程序设计协会 ACM 算法模板集 - 25 - * * * * * */ int matrix20

22、0200,n; /matrix, 30000 表示无限大,即无边.否则为有 边,其值为边的权值 void Dijkstra(int x,int y) /起点 Vx 终点 Vy int i,j,k,path40000,mark40000; int min,dist40000; for(i=1;i 0 else i+; int Relabel_To_Front(int s,int d) /s 为源点，d 为汇点 int u,i,old_h; list l; list:iterator iter; Init_Preflow(s); iter = l.begin(); 程序设计协会 ACM 算法模板集

23、 - 33 - for(i = 0 ; i old_h) l.erase(iter); l.insert(l.begin(),u); iter = l.begin(); iter+; return ever - 1; 10. 最大团 /* * * * * * * Function Name : 最大团 * Description : ZJU 1492 Maximum Clique * 团: 指 G 的一个完全子图, 该子图不包含在任何其他的完全子图当中 * 最大团: 指其中包含顶点最多的团 * * * * * */ #include #include int joint5050; int Si

24、ze, MAX, DP50; bool find; /返回1 表示邻接顶点集已经为空集,否则返回第一个公共顶点 int reachEnd(int start, int sets) int lp; for(lp=start; lp MAX) MAX = depth; find = true; return ; while(first != -1) if(depth + Size - start Bmap; int n, m, k, nm; int markMax; bool flagMax; bool dfs(int pos) int i, pre, tp; for(i=0; i 0)?(x):

25、(-(x) /用 Abs()这个宏定义一个绝对值函数 #define Sgn(x) (x)(b)?(a):(b) /取大值 #define Min(a,b) (a)a) and (o-b) / 叉乘 TYPE Cross(const POINT /叉积模板 / planar points distance / 两个点的距离 TYPE Distance(const POINT struct LINE POINT a; POINT b; 程序设计协会 ACM 算法模板集 - 39 - LINE() ; LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) ; ;

26、/直线由两点决定 /点到直线距离 double PointToLine(POINT p0 ,POINT p1 ,POINT p2 ,POINT double s = Cross(p1 ,p2 ,p0) / d; cp.x = p0.x + s*( p2.y-p1.y) / d; cp.y = p0.y - s*( p2.x-p1.x) / d; return Abs(s); / 返回直线 Ax + By + C =0 的系数 void Coefficient(const LINE B = L.a.x - L.b.x; C = L.b.x * L.a.y - L.a.x * L.b.y; voi

27、d Coefficient(const POINT B = Sin(a); C = - (p.y * B + p.x * A); / 线段 struct SEG POINT a; POINT b; SEG() ; SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) ; ; / 圆 struct CIRCLE TYPE x; TYPE y; TYPE r; 程序设计协会 ACM 算法模板集 - 40 - CIRCLE() CIRCLE(TYPE _x_, TYPE _y_, TYPE _r_) : x(_x_), y(_y_), r(_r_) ; /圆由圆心和半径组成

28、 POINT Center(const CIRCLE /返回的是一个 POINT 类型的对象，他这里 没有直接设出一个具体的对象，而是直接用类名来实现，也是可以的，而且他 这里是把对象传递进来，返回的是他的圆心 /圆的面积 TYPE Area(const CIRCLE /两个圆的公共面积 TYPE CommonArea(const CIRCLE const CIRCLE const CIRCLE /按照圆半径的大小来把圆区分开来 TYPE D = Distance(Center(M), Center(N); if (D M.r - N.r) /判断出两个圆之间的关系是相交的 TYPE cosM

29、 = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D); TYPE cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D); TYPE alpha = 2.0 * ArcCos(cosM); TYPE beta = 2.0 * ArcCos(cosN); TYPE TM = 0.5 * M.r * M.r * Sin(alpha); TYPE TN = 0.5 * N.r * N.r * Sin(beta); TYPE FM = (alpha / 360.0) * Area(M); TY

30、PE FN = (beta / 360.0) * Area(N); area = FM + FN - TM - TN; /相交圆的公共部分的面积就是通过一个扇形的面积减去三角形积 ，然后把 这两个部分相加得到 else if (D pi) dlng = pi + pi - dlng; lat1 *= pi / 180, lat2 *= pi / 180; return acos( cos(lat1)*cos(lat2)*cos(dlng) + sin(lat1)*sin(lat2) ); / 计算距离, r 为球半径 double line_dist(double r, double lng1

31、, double lat1, double lng2, double lat2) double dlng = fabs(lng1 - lng2) * pi / 180; while(dlng = pi+pi) dlng -= pi+pi; if(dlng pi) dlng = pi + pi - dlng; lat1 *= pi / 180, lat2 *= pi / 180; return r * sqrt( 2 - 2*( cos(lat1)*cos(lat2)*cos(dlng) + sin(lat1)*sin(lat2) ) ); / 计算球面距离, r 为球半径 double sph

32、ere_dist(double r, double lng1, double lat1, double lng2, double lat2) return r * angle(lng1, lat1, lng2, lat2); 2. 三点求圆心坐标 double GetRadiusBy3Points(double x1, double y1, double x2, double y2, double x3, double y3, double 程序设计协会 ACM 算法模板集 - 51 - double d, d1, d2 ; a11 = 2 * ( x3 - x2 ); a12 = 2 * (

33、 y3 - y2 ); a21 = 2 * ( x2 - x1 ); a22 = 2 * ( y2 - y1 ); b1 = x3*x3 - x2*x2 + y3*y3 - y2*y2; b2 = x2*x2 - x1*x1 + y2*y2 - y1*y1; d = a11*a22 - a12*a21; d1 = b1*a22 - a12*b2; d2 = a11*b2 - b1*a21; / x , y 是圆心坐标 x = d1 / d; y = d2 / d; return (x1 - x)*(x1 - x) + (y1 - y)*(y1 - y); 第七章 专题讨论 1. 树状数组 /*

34、 * * * * * * Function Name : 树状数组 * Description : HDOJ 1166 敌兵布阵 * 减少冗余统计, 是线段树的一种变化 * * * * * */ #include int data50001, s50001, T50001; inline int lowbit(int t) return t inline int sum(int end) int sum = 0; while(end 0) 程序设计协会 ACM 算法模板集 - 52 - sum += Tend; end -= lowbit(end); return sum; inline vo

35、id plus(int pos, int num, int count) while(pos next xi-a ) s=s-next xi-a ; else t=newnode(); s-next xi-a =t; s=t; /for s-index=pos; void deltrie(trie * s) int i; for(i=0; i nexti ) deltrie(s-nexti); free(s); s=NULL; int find(trie *s, char x) int i; if(x0 = 0) return -1; for(i=0; xi ; i+) if( s-next

36、xi-a ) s=s-next xi-a ; else break; if(xi=0) return s-index; else return -1; int main() int t,n,i,j,all; char word20,mars20,ch; thead=newnode(); while(scanf(“%s“,word)=1) if(word0=S) break; i=1; while(scanf(“%s“,dici)=1 insert(thead,mars,i); i+; all=i; while(scanf(“%s“,word)=1) if(word0=S) break; get

37、char(); j=0; while(scanf(“%c“, else if(mars0!=0) printf(“%s“,mars); printf(“%c“,ch); /while deltrie(thead); 3. 后缀树 /* * * * * * * Function Name : 后缀树 * Description : PKU 2774 Long Long Message * 有效的支持字符串匹配和查询 * * * * * */ #include #include #define NUM 27 #define STARTCHAR a #define SPECIALCHAR #defi

38、ne ERROR -1 #define TYPE1 1 #define TYPE2 2 #define LEAF 1 #define NOTLEAF 2 struct SuffixTrie int Start, End; SuffixTrie * NextNUM; SuffixTrie * Link; SuffixTrie * Father; int Flag; int Length; ; 程序设计协会 ACM 算法模板集 - 56 - char str100010, buf100010; SuffixTrie head; SuffixTrie*P, *G, *U, *V, *q; int W

39、3, len, len2; void CreateNode(SuffixTrie * Node = (SuffixTrie * ) malloc(sizeof(SuffixTrie); Node - Start = Node - End = Node - Length = ERROR; for (i = 0; i Nexti = NULL; Node - Link = Node - Father = NULL; Node - Flag = LEAF; void Init(SuffixTrie h.Start = h.End = ERROR; for (i = 0; i NextsW0 - ST

40、ARTCHAR; old = 0; while (W2 (t - End) - (t - Start) + 1 + old) old += (t - End - t - Start + 1); t = t - NextsW0 + old - STARTCHAR; if (W2 = (t - End) - (t - Start) + 1 + old) V = t; P - Link = V; return TYPE1; else 程序设计协会 ACM 算法模板集 - 57 - CreateNode(newt); newt - Start = t - Start; newt - End = t -

41、 Start + W2 - old - 1; newt - Father = t - Father; newt - Length = newt - Father - Length + newt - End - newt - Start + 1; t - Father - Nextst - Start - STARTCHAR = newt; t - Start = newt - End + 1; newt - Nextst - Start - STARTCHAR = t; t - Father = newt; V = newt; P - Link = V; return TYPE2; int I

42、nsert(SuffixTrie * Node, int start, char s) int i, posbegin, posend; SuffixTrie * t; if (Node - Nextsstart - STARTCHAR = NULL) CreateNode(Node - Nextsstart - STARTCHAR); Node - Nextsstart - STARTCHAR - Start = start; Node - Nextsstart - STARTCHAR - End = len - 1; Node - Nextsstart - STARTCHAR - Fath

43、er = Node; Node - Nextsstart - STARTCHAR - Length = Node - Length + len - start; Node - Flag = NOTLEAF; P = Node; return TYPE1; else posbegin = Node - Nextsstart - STARTCHAR - Start; posend = Node - Nextsstart - STARTCHAR - End; for (i = posbegin; i Nextsstart - STARTCHAR, start + i - posbegin, s);

44、else CreateNode(t); t - Start = posbegin; t - End = i - 1; t - Flag = NOTLEAF; 程序设计协会 ACM 算法模板集 - 58 - Node - Nextsstart - STARTCHAR - Start = i; t - Nextsi - STARTCHAR = Node - Nextsstart - STARTCHAR; t - Nextsi - STARTCHAR - Father = t; Node - Nextsstart - STARTCHAR = t; t - Father = Node; t - Len

45、gth = Node - Length + t - End - t - Start + 1; Insert(t, start + i - posbegin, s); G = Node; P = t; return TYPE2; int Select(int start, char s, int type) int result1, result2, result; if (type = TYPE1) U = P - Link; result = Insert(U, start + U - Length, s); else U = G - Link; if (G - Link = G) W0 = P - Start + 1; W1 = P - End; W2 = P - End - P - Start; else W0 = P - Start; W1 = P - End; W2 = P - End - P - Start + 1; if (W2 = 0) V = G; P - Link = V; result = Insert(V, start, s); else result1 = FindV(s); result2 = Insert(V, start + V - Length, s);