ACM_算法实用模板

《ACM_算法实用模板》由会员分享，可在线阅读，更多相关《ACM_算法实用模板（80页珍藏版）》请在装配图网上搜索。

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. Be

2、ll Number6. Stirlings 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 Equati

3、on 模线性方程 (同余方程 )7. Chinese Remainder Theorem中国余数定理五. 图论算法1. 最小生成树 (Kruscal 算法 )2. 最小生成树 (Prim 算法 )3. 单源最短路径 (Bellman-ford 算法 )4. 单源最短路径 (Dijkstra 算法 )5. 全源最短路径 (Folyd 算法 )6. 拓扑排序7. 网络预流和最大流8. 网络最小费用最大流9. 网络最大流 (高度标号预流推进 )10. 最大团11. 最大二分图匹配 (匈牙利算法 )六. 几何算法精彩文档实用标准文案1. 几何模板2. 球面上两点最短距离3. 三点求圆心坐标七. 专题讨

4、论1. 树状数组2. 字典树3. 后缀树4. 线段树5. 并查集6. 二叉堆7. 逆序数 (归并排序 )8. 树状 DP9. 欧拉路10. 八数码11. 高斯消元法12. 字符串匹配 (KMP 算法 )13. 全排列 ,全组合第一章常用函数和STL一 .常用函数#include int getchar( void );/读取一个字符 , 一般用来去掉无用字符精彩文档实用标准文案char *gets( char *str );/读取一行字符串#include void * malloc( size_t size );/动态内存分配 , 开辟大小为 size 的空间void qsort( void

5、 *buf, size_t num, size_t size,int (*compare)(const void *, constvoid*) );/快速排序Sample:int compare_ints( const void * a, const void * b )int* arg1 = ( int*) a;int * arg2 = ( int *) b;if ( *arg1 *arg2 ) return -1;else if ( *arg1 = *arg2 )return 0;else return 1;int array = -2, 99, 0, -743, 2, 3, 4 ;int

6、 array_size = 7;qsort( array, array_size, sizeof(int), compare_ints );#include /求反正弦 , arg-1, 1, 返回值 -pi/2, +pi/2double asin( double arg );/求正弦 , arg 为弧度 , 弧度 =角度 *Pi/180.0, 返回值 -1, 1 double sin( double arg );/求 e 的 arg 次方double exp( double arg );/求 num 的对数 , 基数为 edouble log( double num );/求 num 的根d

7、ouble sqrt( double num );/求 base的 exp 次方double pow( double base,double exp );#include /初始化内存 , 常用来初始化数组void* memset( void * buffer, int ch, size_t count );memset( the_array, 0, sizeof(the_array) );/printf 是它的变形 , 常用来将数据格式化为字符串int sprintf( char *buffer, const char *format, . );sprintf(s, %d%d, 123, 4

8、567);/s=1234567/scanf 是它的变形 , 常用来从字符串中提取数据int sscanf(const char *buffer, const char *format, . );Sample:char result100=24 hello, str100;int num;sprintf( result, %d %s, num,str ); /num=24;str=hello ;/字符串比较 , 返回值 0 代表 str10 代表 str1str2精彩文档实用标准文案int strcmp( constchar *str1, const char *str2 );二 . 常用 ST

9、L标准 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)co

10、py()复制（拷贝）元素 , O(N)remove()移除元素reverse()倒置元素sort()排序 , 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,

11、8, 13, 21, 34, 55, 89, 144, 233, 377, 610Formula:精彩文档实用标准文案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 个数相乘 , 给每两个元素加上括号的不同方法数Sampl

12、e: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)4) 从 n * n 方格的左上角移动到右下角不升路径数Sample:n = 2;精彩文档实用标准文案n = 3;4. Stirling Number(Second Kind)S(n, m)表示含 n 个元素的集合划分为m 个集合的情况数或者是 n 个有标号的球放到 m 个无标号的盒子中 , 要求无一为空 , 其不同的方案数Formula:Spe

13、cial Cases:5. Bell Numbern 个元素集合所有的划分数Formula:6. Stirlings Approximation7. Sum of Reciprocal Approximation精彩文档实用标准文案EulerGamma = 0.57721566490153286060651209;8. Young TableauYoung Tableau(杨式图表 )是一个矩阵 , 它满足条件 :如果格子 i, j 没有元素 , 则 i+1, j 也一定没有元素如果格子 i, j 有元素 ai, j, 则i+1, j 要么没有元素 , 要么 ai+1, j ai, j Yn

14、代表 n 个数所组成的杨式图表的个数Formula:Sample:n = 3;9. 整数划分将整数 n 分成 k 份, 且每份不能为空 , 任意两种分法不能相同1) 不考虑顺序for(int p=1; p=n ;p+)for(int i=p; i=1 ;j-)dpij += dpi-pj-1;cout dpnk endl;2) 考虑顺序dpij = dpi-kj-1; (k=1.i)3) 若分解出来的每个数均有一个上限 m dpij = dpi-k j-1; (k=1.m)10. 错排公式11. 三角形内切圆半径公式精彩文档实用标准文案12. 三角形外接圆半径公式13. 圆內接四边形面积公式1

15、4. 基础数论公式1) 模取幂2) n 的约数的个数若 n 满足, 则 n 的约数的个数为第三章大数模板/* * * * * * Function Name :BigNumber*Description :BigNumbers HPC*Author :HuangWei*Last Edited :07.4.11精彩文档实用标准文案* * * * * */#include #include #include #include #include #define BASE1000/ 基数#define DIG1100/存储using namespacestd;class BigNumberprivat

16、e:int dataDIG;/数据区int len;/记录长度public:BigNumber()len=1;memset(data,0,sizeof(data);data0=1;BigNumber(int);/输入默认十进制BigNumber(char*);BigNumber(const BigNumber &);/ 类型转换BigNumber & Num_BNum( int); / 把一个整数转换成BigNumber 型的BigNumber & Str_BNum( char*); / 把一个字符串类型的转换成BigNumber 型的int Int();string Str();/ HPCB

17、igNumber & Add( const BigNumber &);BigNumber & Sub(const BigNumber &);BigNumber & Mul( const BigNumber &);BigNumber & Div( int);BigNumber & Mod( int);BigNumber & operator=(const BigNumber &);int Bigger(const BigNumber &) const;BigNumber operator + (const BigNumber &);BigNumber operator - (const BigN

18、umber &);BigNumber operator * ( const BigNumber &);BigNumber operator / (int );BigNumber operator % (int);BigNumber & operator += (const BigNumber &);BigNumber & operator -= (const BigNumber &);BigNumber & operator *= ( const BigNumber &);精彩文档实用标准文案BigNumber & operator /= (int);BigNumber & operator

19、%= (int);BigNumber & BigNumber:Num_BNum( int b)len=1;memset(data,0,sizeof(data);data0 = 1;if (b 0) data len+ = b % BASE;b /= BASE;return *this;BigNumber & BigNumber:Str_BNum( char* sb)int t=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=s

20、len-1; i=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()istringstream sin;精彩文档实用标准文案int v;sin.str( this-Str() );sin v;return v; /这个函数的用法还是第一次看到，没看懂string BigNumber:Str()int i,bas

21、e_len=0;ostringstream sout;if (len = 1) sout 0;/sout endl;return sout.str();if (data0 0)sout -;sout 1) base_len+;i /= 10;for(i=len-2; i0 ;i-) sout.width(base_len);sout.fill(0);sout datai;/sout Num_BNum(b);BigNumber:BigNumber( char* sb) this-Str_BNum(sb); / -1 ab BigNumber:BigNumber( const BigNumber

22、& b)len = b.len;memcpy(data,b.data,sizeof(data);int BigNumber:Bigger(const BigNumber & b) const int i,flag;if (data0 =1 & b.data0 =1)flag = 1;精彩文档实用标准文案elseif (data0 =1 & b.data0 =-1)return 1;elseif (data0 =-1 & b.data0 =1)return -1;elseflag = -1;if (len b.len)return flag;elseif (len = b.len) for(i=

23、len-1; i0 ;i-)if (datai b.datai)return flag;if (i = 0)return 0;return -flag; / 比较函数BigNumber & BigNumber:Add( const BigNumber & b)int i;if (data0 * b.data0 != 1) data0 = -data0;Sub(b);data0 = -data0;return * this;len= len b.len ? len : b.len;for(i=1; i= BASE) datai+1+;datai -= BASE;if (datai 0)len =

24、 i+1;return *this; / 加上 b 这个大数BigNumber & BigNumber:Sub( const BigNumber & b)int i;if (data0 * b.data0 != 1) data0 = -data0;Add(b);data0 = -data0;return * this;len= len b.len ? len : b.len;精彩文档实用标准文案for(i=1; ilen ;i+) datai -= b.datai;if(datai 0) datai+1-;datai += BASE;if (datalen 0) for(i=0; i=len

25、;i+)datai = -datai;for(i=1; ilen ;i+)if (datai 0) datai+1-;datai += BASE;while(datalen-1 = 0)len-;return *this;BigNumber & BigNumber:Mul( const BigNumber & b)BigNumber bt;int i,j,up;int temp,temp1;bt.data0 = data0 * b.data0;for(i=1; ilen ;i+) up = 0;for(j=1; j= BASE) temp1 = temp % BASE;up = temp /

26、BASE;bt.datai+j-1 = temp1;else up = 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( int b)BigNumber bt;int i,down = 0;if (b =1 ;i-) bt.datai = (datai + down * BASE) / b;down = datai + down *

27、 BASE - bt.datai * b;bt.len = len;while(bt.databt.len-1 = 0)bt.len-;*this=bt;return *this;BigNumber & BigNumber:Mod( int b)int temp = 0, up = 0, i;for(i=len-1; i=1 ;i-) temp = datai;temp += up * BASE;up = temp % b;if (data0 Add(b);BigNumber & BigNumber: operator -= ( const BigNumber & b) return this

28、-Sub(b);BigNumber & BigNumber: operator *= ( const BigNumber & b) return this-Mul(b);BigNumber & BigNumber: operator /= ( int b) return this-Div(b);BigNumber & BigNumber: operator %= (int b) return this-Mod(b);第四章数论算法1. Greatest Common Divisor最大公约数int GCD(int x, int y)int t;精彩文档实用标准文案while(y 0) t =

29、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)return false;for(int i=3; i = sqrt(u) ;i+=2)if (u%i=0)return false;return true;3. Sieve Prime素数筛法constint M = 1000; / M : sizebool markM; / true : prime numbervoid sieve_prime

30、()memset(mark,true, sizeof(mark);mark0 = mark1 = false;for(int i=2; i = sqrt(M) ;i+) if (marki) for(int j=i*i; j 0/上式等价于二元一次方程ax ny = bvoid modular_linear_equation(int a, int b, int n)int d, x, y, x0;d = extended_euclid(a, n, x, y);if ( b%d = 0) x0 = ( x*(b/d) ) % n; / x0 : basic solutionint ans = n

31、;for(int i=0; i d ;i+) ans = ( x0 + i*(n/d) ) % n;cout ans endl;elsecout no solution 0, 且 w 中任意两个数互质 int chinese_remainder(int b, int w, int len)int i, d, x, y, m, n;精彩文档实用标准文案x = 0;n = 1;for(i=0; i len ;i+)n *= wi;for(i=0; i len ;i+) m = n / wi ;d = extended_euclid(wi, m, x, y);x = (x + y*m*bi) % n

32、;return (n + x%n) % n;第五章图论算法1. 最小生成树 (Kruscal 算法 )/* * * * * * Function Name :最小生成树 (Kruscal 算法 )* Description :ZJU 1203 Swordfish O(E*LogE)精彩文档实用标准文案* * * * * */#include #include #include #include using namespacestd; struct struct_edgesint bv,tv; /bv 起点 tv 终点double w; /权值;struct_edges edges10100;/

33、边集struct struct_adouble x;double y;struct_a arr_xy101;int point101,n,e; /n 顶点数 , e 边数 (注意是无向网络 )double sum;int kruscal_f1(int point, int v)int i = v;while(pointi 0)i = pointi;return i;bool UDlesser(struct_edges a, struct_edges b)return a.w b.w;void kruscal() /只需要准备好 n，e，递增的边集 edges即可使用int v1,v2,i,j;

34、for(i=0; in ;i+)pointi=0;i = j = 0;while(jn-1 & in;k=0;while(n != 0) sum=0;k+;for(i=0; iarr_xyi.xarr_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-a

35、rr_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 算法 )/* * * * * * Function Name :最小生成树 (Prim 算法 )* Description :ZJU 1203 Swordfish O(N2)* * * * * */#include 精彩文档实用标准文案#include #include using namespaces

36、td;double sum, arr_list101101, min;int i, j, k=0, n;struct struct_afloat x;float y;struct_a arr_xy101;struct struct_bint point;float lowcost;struct_b closedge101;void prim(int n) /prim 需要准备： n 顶点数 arr_list 顶点的邻接矩阵也是从 0 开始计数int i,j,k;k=0;for(j=0; jn ;j+) if (j != k) closedgej.point = k;closedgej.lowc

37、ost = arr_listkj;closedgek.lowcost=0;for(i=0; in ;i+) min=10000;for(j=0; jn ;j+) if (closedgej.lowcost != 0 & closedgej.lowcost min) k = j;min = closedgej.lowcost;sum += closedgek.lowcost; /不要改成 sum+=min; sum 即为所求值closedgek.lowcost = 0;for(j=0; jn ;j+) if(arr_listkj n;while(n != 0) sum=0;k+;for(i=0;

38、 iarr_xyi.xarr_xyi.y;for(i=0; in ;i+)for(j=0; jn ;j+) /得到邻接矩阵 arr_listarr_listij=arr_listji=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); prim(n);coutCase #k:n;if (n!=0)printf(n);3. 单源最短路径 (Bellman-ford 算法 )/* * * * * * Function Name :单源最短路径 (Bellman-fo

39、rd 算法 )* Description :可允许有负权* * * * * */#include 精彩文档实用标准文案#define MAX 100#define MAXNUM 1000000typedef struct graphnodeint 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+) sign = 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;ret