acm-算法模板
程序设计协会 ACM 算法模板集- 1 -ACM Standard Code LibraryHuang WeiComputer Science and EngineeringAssociation of ProgramingInformation Engineering CollegeHangzhou Dianzi UniversityApril, 2007ACM 算法模板集算法模板集Contents程序设计协会 ACM 算法模板集- 2 -一一. 常用函数与常用函数与 STL二二. 重要公式与定理重要公式与定理1.Fibonacci Number 2.Lucas Number 3.Catalan Number 4.Stirling Number(Second Kind) 5.Bell Number 6.Stirling's 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 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. 最大二分图匹配(匈牙利算法)六六. 几何算法几何算法程序设计协会 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 -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 *) ); /快速排序 Sample: int compare_ints( const void* a, const void* b ) int* arg1 = (int*) a; int* arg2 = (int*) b; if( *arg1 /求反正弦, 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 的对数, 基数为 e double 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(the_array) ); /printf 是它的变形, 常用来将数据格式化为字符串 int sprintf( char *buffer, const char *format, . ); sprintf(s, “%d%d“, 123, 4567); /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 代表 str1>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关联数组, 常用来作 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() 从字符串移除元素 find()查找元素 insert()插入元素 length()字符串长度 replace()替换元素 substr() 取子字符串 swap()交换字符串 第二章第二章 重要公式与定理重要公式与定理1.Fibonacci Number0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 Formula:程序设计协会 ACM 算法模板集- 6 -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, 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) 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 Numbern 个元素集合所有的划分数 Formula:6.Stirling's Approximation7.Sum of Reciprocal Approximation程序设计协会 ACM 算法模板集- 8 -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代表 n 个数所组成的杨式图表的个数 Formula:Sample:n = 3;9.整数划分整数划分将整数 n 分成 k 份, 且每份不能为空, 任意两种分法不能相同 1) 不考虑顺序 for(int p=1; p=1 ;j-)dpij += dpi-pj-1; cout #include #include #include #include #define BASE 1000/ 基数 #define DIG1100/ 存储 using namespace std;class BigNumber private:int dataDIG;/ 数据区int len;/ 记录长度 public:BigNumber() len=1;memset(data,0,sizeof(data);data0=1;BigNumber(int); / 输入默认十进制BigNumber(char*);BigNumber(const BigNumber / 类型转换BigNumber /把一个整数转换成 BigNumber 型的BigNumber /把一个字符串类型的转换成 BigNumber 型 的int Int();string Str();/ HPCBigNumber BigNumber BigNumber BigNumber BigNumber BigNumber int Bigger(const BigNumber BigNumber operator + (const BigNumber BigNumber operator - (const BigNumber BigNumber operator * (const BigNumber BigNumber operator / (int);BigNumber operator % (int);BigNumber BigNumber 程序设计协会 ACM 算法模板集- 11 -BigNumber BigNum
