acm程序算法模板

剑云雨啸 ACM算法总结ACM程序算法模板目录一、组合数学11.1、重复性全排列算法11.2、C（m,n）11.3、无重复全组合21.4、大数相加3二、数论52.1、最大公约数52.2、乘方取余52.3、进制转换52.4、素数表62.5、素数表精简72.6、N阶乘最后非0位72.7、约瑟夫环（不带路径）82.8、约瑟夫环（带路径）82.9、质因数分解92.10、判断是否为质数92.11、欧拉函数10三、数据结构113.1、最小代价生成树普利姆算法11四、动态规划124.1、LIS最长不下降序列的算法124.2、交通最短路径算法144.3、数塔最大值算法154.4、最小代价字母树154.5、最长公共字串LCS164.6、可中断最长字串174.7、从数组中取定值184.8、最近点对194.9、24点214.10、01背包 极大界定 原始算法234.11、01背包 极大界定 空间优化264.12、01背包 恰好装满 附带组成274.13、01背包 恰好装满 空间优化304.14、完全背包 恰好装满 买咖啡题314.15、完全背包 极大界定 原始算法334.16、背包扩展 等价匹配种数统计34五、串355.1、KMP算法35六、高精度算法366.1通用函数366.2、高精度加法376.3、高精度减法386.4、高精度乘法-高精度乘以低精度406.5、高精度乘法-高精度乘以高精度416.6、整型常量的阶乘416.7、整型常量的阶乘和426.8、高精度的乘方，幂数为整型常量426.9、高精度除法-高精度除以低精度，只产生余数436.10、高精度除法-高精度除以高精度，只产生余数44七、排序搜索457.1、插入排序457.2、堆排序467.3、合并排序（分治）477.4、计数排序487.5、冒泡排序497.6、快速排序497.7、二分搜索50八、技巧508.1、输入技巧508.2、递归518.3、位运算518.4、字典序518.5、省略末尾零51一、组合数学1.1、重复性全排列算法#include <iostream>#include <algorithm>using namespace std;int main() char s101; while(gets(s) int n=strlen(s); sort(s, s+n); puts(s); while(next_permutation(s, s+n) puts(s); return 0;1.2、C（m,n）int combination(int m,int n)/m为下标，n为上标 if(m <0|n <0|m <n) return -1; n=n <(m-n)?n:m-n;if(n=0) return 1; int result=m;for(int i=2,j=result-1;i <=n;i+,j-) result=result*j/i; return result; 1.3、无重复全组合#include <stdio.h>#define MAX_N 10int n, m; /输入n个数，其中本质不同的有m个int rcdMAX_N; /记录每个位置填的数int usedMAX_N; /标记m个数可以使用的次数int numMAX_N; /存放输入中本质不同的m个数void unrepeat_combination(int l, int p) int i; for (i=0; i<l; i+) /每次都输出 printf("%d", rcdi);if (i < l-1)printf(" "); printf("n"); for (i=p; i<m; i+) /循环依旧从p开始，枚举剩下的本质不同的数if (usedi > 0) /若还可以用，则usedi-; /可用次数减1rcdl = numi; /在l位置放上该数unrepeat_combination(l+1, i); /填下一个位置usedi+; /可用次数恢复int read_data() int i, j, val; if (scanf("%d", &n) = EOF)return 0; m = 0; for (i=0; i<n; i+) scanf("%d", &val);for (j=0; j<m; j+)if (numj = val)usedj+;break;if (j = m)numm = val;usedm = 1;m+; return 1;int main() while (read_data()unrepeat_combination(0, 0); return 0;1.4、大数相加#include<stdio.h>#include<string.h>#define max 1000int nummax;char charAmax;char charBmax;char charCmax;void numsum(char charA,char charB,int num) /两个要相加的数和最后的结果保存的数组,并且结果存放在C中memset(num,0,sizeof(num);int lengthA=strlen(charA);int lengthB=strlen(charB);int lengthC=lengthA>lengthB?lengthA:lengthB;int i,j;int k=lengthC-1;i=lengthA-1;j=lengthB-1;while(i>=0&&j>=0)numk=charAi+charBj-96;k-;j-;i-;while(i>=0)numk=charAi-48;k-;i-;while(j>=0)numk=charBj-48;k-;j-;for(i=lengthC-1;i>0;i-)numi-1=numi-1+numi/10;numi=numi%10;for(i=1;i<=lengthC;i+)charCi=numi-1+48;charC0=(charC1-48)/10+48;charC1=(charC1-48)%10+48;if(charC0!='0')printf("%c",charC0);for(i=1;i<=lengthC;i+)printf("%c",charCi);printf("n");int main()while(scanf("%s%s",charA,charB)!=EOF)numsum(charA,charB,num);return 0;二、数论2.1、最大公约数int gcd(int n,int m) /两个数字为参数，输出最大公约数if(m=0)return n;return gcd(m,n%m);2.2、乘方取余long long exp_mod(long long a,long long n,long long k) /an%k，返回余数 long long t; if(n=0)return 1; if(n=1)return a%k; a%=k; t=exp_mod(a,n>>1,k); t=(t*t)%k; if(n%2=0) return t; return (t*a)%k;2.3、进制转换/10?其他int trans(int n,int d,char s) /数值n，转换成d(2-16)进制表示的字符串sstatic char digits="0123456789ABCDEF"char buf20;int j,i=19;if(d<2|d>16)s0='0'return 0;bufi='0'dobuf-i=digitsn%d;n/=d;while(n);for(j=0;(sj=bufi)!='0'i+,j+);return j;/其他?10int n2ten(char *x,int n)/其它进制转化成十进制char *a;int i,j,s=0,m=1;for(i=0;xi;i+);a=(char *)malloc(i+1)*sizeof(char);ai='0'for(j=0,i-;i>=0;i-,j+)aj=xi;for(j=0;aj;j+)29s+=(int)(aj-'0')*m;m*=n;return s;2.4、素数表bool primes100000001; void makeprimes() /素数表的产生，false是素数，这里0，1，2,3默认是。可自己改动memset(primes, 0, sizeof(primes);int i,j;for(j = 4; j < 1001; j += 2)primesj = true;for(i =