资源描述：
《ACM_算法模板.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、程序设计协会ACM算法模板集ACMStandardCodeLibraryHuangWeiComputerScienceandEngineeringAssociationofProgramingInformationEngineeringCollegeHangzhouDianziUniversityApril,2007ACM算法模板集Contents-80-程序设计协会ACM算法模板集一.常用函数与STL二.重要公式与定理1.FibonacciNumber2.LucasNumber3.CatalanN
2、umber4.StirlingNumber(SecondKind)5.BellNumber6.Stirling'sApproximation7.SumofReciprocalApproximation8.YoungTableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三.大数模板四.数论算法1.GreatestCommonDivisor最大公约数2.Prime素数判断3.SievePrime素数筛法4.ModuleIn
3、verse模逆元5.ExtendedEuclid扩展欧几里德算法6.ModularLinearEquation模线性方程(同余方程)7.ChineseRemainderTheorem中国余数定理五.图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径(Bellman-ford算法)4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.最大
4、二分图匹配(匈牙利算法)六.几何算法-80-程序设计协会ACM算法模板集1.几何模板2.球面上两点最短距离3.三点求圆心坐标一.专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配(KMP算法)13.全排列,全组合第一章常用函数和STL一.常用函数#include int getchar( void ); //读取一个字符, 一般用来去掉无用字符-8
5、0-程序设计协会ACM算法模板集char *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 *) ); //快
6、速排序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 array_size
7、 = 7; qsort( array, array_size, sizeof(int), compare_ints ); #include //求反正弦, arg∈[-1, 1], 返回值∈[-pi/2, +pi/2]double asin( double arg );//求正弦, arg为弧度, 弧度=角度*Pi/180.0, 返回值∈[-1, 1]double sin( double arg );//求e的arg次方double exp( double arg );//求num的
8、对数, 基数为edouble log( double num );//求num的根double 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(th
