9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

ACM程序算法模板



剑云雨啸

ACM 算法总结

ACM 程序算法模板

剑云雨啸

ACM 算法总结

目录
一、组合数学..................................................................................

................................................. 1 1.1、重复性全排列算法 .......................................................................................................... 1 1.2、C(m,n) ......................................................................................................................... 1 1.3、无重复全组合.................................................................................................................. 2 1.4、大数相加.......................................................................................................................... 3 二、数论........................................................................................................................................... 5 2.1、最大公约数...................................................................................................................... 5 2.2、乘方取余.......................................................................................................................... 5 2.3、进制转换.......................................................................................................................... 5 2.4、素数表.............................................................................................................................. 6 2.5、素数表精简...................................................................................................................... 7 2.6、N 阶乘最后非 0 位 .......................................................................................................... 7 2.7、约瑟夫环(不带路径) .................................................................................................. 8 2.8、约瑟夫环(带路径) ...................................................................................................... 8 2.9、质因数分解...................................................................................................................... 9 2.10、判断是否为质数 ............................................................................................................ 9 2.11、欧拉函数 ...................................................................................................................... 10 三、数据结构................................................................................................................................. 11 3.1、最小代价生成树—普利姆算法 ............................................................................ 11 四、动态规划................................................................................................................................. 12 4.1、LIS 最长不下降序列的算法 ......................................................................................... 12 4.2、交通最短路径算法 ........................................................................................................ 14 4.3、数塔最大值算法 ............................................................................................................ 15 4.4、最小代价字母树 ............................................................................................................ 15 4.5、最长公共字串 LCS ....................................................................................................... 16 4.6、可中断最长字串 ............................................................................................................ 17 4.7、从数组中取定值 ............................................................................................................ 18 4.8、最近点对........................................................................................................................ 19 4.9、24 点............................................................................................................................... 21 4.10、01 背包 极大界定 原始算法 ..................................................................................... 23 4.11、01 背包 极大界定 空间优化 ..................................................................................... 26 4.12、01 背包 恰好装满 附带组成 ..................................................................................... 27 4.13、01 背包 恰好装满 空间优化 ..................................................................................... 30 4.14、完全背包 恰好装满 买咖啡题 .................................................................................. 31 4.15、完全背包 极大界定 原始算法 .................................................................................. 33 4.16、背包扩展 等价匹配种数统计 .................................................................................... 34 五、串 ............................................................................................................................................ 35 5.1、KMP 算法 ...................................................................................................................... 35 六、高精度算法............................................................................................................................. 36 6.1 通用函数........................................................................................................................... 36

剑云雨啸

ACM 算法总结

6.2、高精度加法.................................................................................................................... 37 6.3、高精度减法.................................................................................................................... 38 6.4、高精度乘法--高精度乘以低精度 ................................................................................. 40 6.5、高精度乘法--高精度乘以高精度 ................................................................................. 41 6.6、整型常量的阶乘 ............................................................................................................ 41 6.7、整型常量的阶乘和 ........................................................................................................ 42 6.8、高精度的乘方,幂数为整型常量 ................................................................................ 42 6.9、高精度除法--高精度除以低精度,只产生余数 ......................................................... 43 6.10、高精度除法--高精度除以高精度,只产生余数 ....................................................... 44 七、排序搜索................................................................................................................................. 45 7.1、插入排序........................................................................................................................ 45 7.2、堆排序............................................................................................................................ 46 7.3、合并排序(分治) ........................................................................................................ 47 7.4、计数排序........................................................................................................................ 48 7.5、冒泡排序........................................................................................................................ 49 7.6、快速排序........................................................................................................................ 49 7.7、二分搜索........................................................................................................................ 50 八、技巧......................................................................................................................................... 50 8.1、输入技巧................................................................................................................ 50 8.2、递归........................................................................................................................ 51 8.3、位运算.................................................................................................................... 51 8.4、字典序.................................................................................................................... 51 8.5、省略末尾零 ............................................................................................................ 51

剑云雨啸

ACM 算法总结

一、组合数学
1.1、重复性全排列算法
#include <iostream> #include <algorithm> using namespace std; int main() { char s[101]; 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

剑云雨啸

ACM 算法总结

1.3、无重复全组合
#include <stdio.h> #define MAX_N 10 int n, m; //输入 n 个数,其中本质不同的有 m 个 int rcd[MAX_N]; //记录每个位置填的数 int used[MAX_N]; //标记 m 个数可以使用的次数 int num[MAX_N]; //存放输入中本质不同的 m 个数 void unrepeat_combination(int l, int p) { int i; for (i=0; i<l; i++) //每次都输出 { printf("%d", rcd[i]); if (i < l-1) printf(" "); } printf("\n"); for (i=p; i<m; i++) //循环依旧从 p 开始,枚举剩下的本质不同的数 if (used[i] > 0) //若还可以用,则 { used[i]--; //可用次数减 1 rcd[l] = num[i]; //在 l 位置放上该数 unrepeat_combination(l+1, i); //填下一个位置 used[i]++; //可用次数恢复 } } 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 (num[j] == val) { used[j]++; break; } if (j == m) {
2

剑云雨啸

ACM 算法总结

num[m] = val; used[m] = 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 1000 int num[max]; char charA[max]; char charB[max]; char charC[max]; 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) { num[k]=charA[i]+charB[j]-96; k--; j--; i--;
3

剑云雨啸

ACM 算法总结

} while(i>=0) { num[k]=charA[i]-48; k--; i--; } while(j>=0) { num[k]=charB[j]-48; k--; j--; } for(i=lengthC-1;i>0;i--) { num[i-1]=num[i-1]+num[i]/10; num[i]=num[i]%10; } for(i=1;i<=lengthC;i++) { charC[i]=num[i-1]+48; } charC[0]=(charC[1]-48)/10+48; charC[1]=(charC[1]-48)%10+48; if(charC[0]!='0') printf("%c",charC[0]); for(i=1;i<=lengthC;i++) printf("%c",charC[i]); printf("\n"); } int main() { while(scanf("%s%s",charA,charB)!=EOF) { numsum(charA,charB,num); } return 0; }

4

剑云雨啸

ACM 算法总结

二、数论
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) //a^n%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)进制表示的字符串 s { static char digits[]="0123456789ABCDEF"; char buf[20]; int j,i=19; if(d<2||d>16) { s[0]='\0'; return 0; }
5

剑云雨啸

ACM 算法总结

buf[i]='\0'; do { buf[--i]=digits[n%d]; n/=d; }while(n); for(j=0;(s[j]=buf[i])!='\0';i++,j++); return j; } //其他??10 int n2ten(char *x,int n)//其它进制转化成十进制 { char *a; int i,j,s=0,m=1; for(i=0;x[i];i++); a=(char *)malloc((i+1)*sizeof(char)); a[i]='\0'; for(j=0,i--;i>=0;i--,j++) a[j]=x[i]; for(j=0;a[j];j++) 29{ s+=(int)(a[j]-'0')*m; m*=n; } return s; }

2.4、素数表
bool primes[100000001]; void makeprimes() //素数表的产生,false 是素数,这里 0,1,2,3 默认是。可自己改动 { memset(primes, 0, sizeof(primes)); int i,j; for(j = 4; j < 1001; j += 2) primes[j] = true; for(i = 3; i < 1001; i+=2) if(primes[i] == false) { j = i*i; if(j < i) break;
6

剑云雨啸

ACM 算法总结

for(; j < 1001; j += 2*i) primes[j] = true; } }

2.5、素数表精简
bool primes2[10001]; void makeprimes2() //true 则是说明是素数 { memset(primes2,1,sizeof(primes2)); primes2[0]=primes2[1]=false; int i,j; for(i=2;i<=10001;i++) { for(j=i+i;j<=10001;j+=i) { if(primes2[j]) primes2[j]=false; } } }

2.6、N 阶乘最后非 0 位
#define MAXN 1000 int lastdigit(char* buf) { const int mod[20] = {1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; int len=strlen(buf),a[MAXN],i,c,ret=1; if (len == 1) return mod[buf[0]-'0']; for (i=0; i<len; i++) a[i] = buf[len-1-i]-'0'; for (; len; len-=!a[len-1]){ ret = ret*mod[a[1]%2*10+a[0]]%5; for (c=0,i=len-1; i>=0; i--) c = c*10+a[i], a[i] = c/5, c%=5; }
7

剑云雨啸

ACM 算法总结

return ret+ret%2*5; }

2.7、约瑟夫环(不带路径)
int YueSeFu(int n,int m) /* 输入几个人和每次退出的第几个,返回最后胜利者的编号 */ { int s=0; int i; for(i=2; i<=n; i++) s=(s+m)%i; return s+1; }

2.8、约瑟夫环(带路径)
#include<stdio.h> #define MAX 10000 int a[MAX]; int m,n,x; /* n 为总人数,从第 x 个人开始从 1 到 m 报数。 */

int main() { int i,j; scanf("%d%d%d",&n,&x,&m); for(i=1;i<=n;i++) a[i]=i; for(;n>0;n--) { x=(x+m+n-1)%n; if(x==0)x=n; printf("%d ",a[x]); for(j=x;j<n;j++)a[j]=a[j+1]; } return 0; }

8

剑云雨啸

ACM 算法总结

2.9、质因数分解
void solve(int n) { int key=0,i; if(n<0) { key=1; n=n*-1; } for(i=2; i<=n/2; i++) { if(n%i==0) { if(key==1) { printf("-"); key=0; } printf("%d ", i); n = n / i; i--; } } if(n>1) printf("%d\n", n); }

2.10、判断是否为质数
bool is_prime(int n) { if( n==1 ) return true; int k=sqrt( (double)n ); int i; for(i=2;i<=k;++i) if( n%i==0 ) return false; return true; }

9

剑云雨啸

ACM 算法总结

2.11、欧拉函数
#include<iostream> #include<cmath> using namespace std; #include<stdio.h> bool is_prime(int n) { if( n==1 ) return true; int k=sqrt( (double)n ); int i; for(i=2;i<=k;++i) if( n%i==0 ) return false; return true; } int main() { int n; while( cin>>n && n ) { if( is_prime(n) ) cout<<n-1<<endl; else { double ans=n; int d=2; while( n!=1 ) { int f=0; while( n%d==0 ) { f=1; n=n/d; } if( f ) ans*=(double)(1-(double)1/(double)d); if( d==2 ) d++; else d+=2; } printf("%.0lf\n",ans); }
10

剑云雨啸

ACM 算法总结

} return 0; }

三、数据结构
3.1、最小代价生成树—普利姆算法
float prim(int n) /* n 是顶点的个数,然后所有的顶点之间的距离保存在 matrix 中间 */ { float lowcost[101]; bool uset[101]={true}; int i,j,k,t; float min,sum=0; for(i=0;i<n;i++) { lowcost[i]=matrix[0][i]; } k=0; for(i=1;i<n;i++) { min=INT_MAX; for(j=0;j<n;j++) { if(lowcost[j]<min&&!uset[j]) { min=lowcost[j]; t=j; } } sum+=min; uset[t]=true; k=t; for(j=0;j<n;j++) { if(!uset[j]&&lowcost[j]<INT_MAX&&lowcost[j]>matrix[k][j]) { lowcost[j]=matrix[k][j]; } } }
11

剑云雨啸

ACM 算法总结

return sum; }

四、动态规划
4.1、LIS 最长不下降序列的算法
#include<stdio.h> #define MAX 50 int num[MAX]; int result[MAX]; int Longest_Increasing(int num[],int n) //输入数组和其长度,result 存放结果数组,返回结果 长度 { int lis[MAX],i,j; for(i=0;i<n;i++) { lis[i]=1; for(j=0;j<i;j++) if(num[i]>num[j]&&lis[j]+1>lis[i]) lis[i]=lis[j]+1; } int maxn=0; for(i=0;i<n;i++) if(maxn<lis[i]) maxn=lis[i]; int max=maxn; for(i=MAX-1;i>=0;i--) { if(lis[i]==maxn) { result[maxn-1]=num[i]; maxn--; } }
12

剑云雨啸

ACM 算法总结

return max; }

#include<stdio.h> #include<string.h> int max; #define max 100020 int a[max]; int B[max]; int result[max]; int len; int LIS(int d[], int n) //输入数组和其长度,result 存放结果数组,返回结果长度,下标 1 开始 { memset(B,0,sizeof(B)); int left,right,mid,i,j; len=1; B[1]=d[1]; for(i=2;i<=n;++i) { left=1,right=len; while(left<=right) { mid=(left+right)/2; if(B[mid]<d[i])left=mid+1; else right=mid-1; } B[left]=d[i]; if(left>len) len++; } for(i=1;i<len;i++) { for(j=1;j<n;j++) { if(a[j]>=B[i]&&a[j]<=B[i+1]) { result[i]=a[j]; break;
13

剑云雨啸

ACM 算法总结

} } } result[i]=B[i]; return len; } int main() { int n,i,t; scanf("%d",&t); while(t--&&scanf("%d",&n)) { for(i=1;i<=n;i++) scanf("%d",&a[i]); printf("%d\n",LIS(a,n)); for(i=1;i<=len;i++) { printf("%d ",result[i]); } } return 0; }

4.2、交通最短路径算法
int M[7][7] = { 0, 5, 2, 0, 0, 0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0, 7, 4, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0 }; int sum=0,min=10000; int MD(int place) //place 是到达的最末端,以此开始往前推,M 数组是全局变量,存放每个 点之间的关系 { int i,j; i=place;
14

剑云雨啸

ACM 算法总结

if(i<=0) { if(sum<min) min=sum; return 0; } for(j=0;j<i;j++) { if(M[j][i]!=0) { sum+=M[j][i]; MD(j); sum-=M[j][i]; } } return 0; }

4.3、数塔最大值算法
void solve(int i,int j) //i,j 是数塔起始的坐标,a 数组是全局定义用来储存数据的数组,max 是 最大值,s 不断变化的和,也是全局变量 { k=0; s=s+a[i][j]; max=max>s?max:s; while(i<n) { solve(i+1,j); s=s-a[i+1][j]; solve(i+1,j+1); s=s-a[i+1][j+1]; break; } }

4.4、最小代价字母树
int dp(int num[],int length) //储存数组的数字和该数组的长度 { quickSort(num,0,length-1);
15

剑云雨啸

ACM 算法总结

if(num[1]==10000) return 0; sum=num[0]+num[1]; result+=sum; num[0]=num[1]+num[0]; num[1]=10000; dp(num,length); return 0; }

4.5、最长公共字串 LCS
int LCS(char A[],char B[]) //两个比较字符串,返回最长公共字串 { int length=0; int num[255][255]; int i,j; int len1=strlen(A); int len2=strlen(B); memset(num,0,sizeof(num)); for(i=0;i<len1;i++) { for(j=0;j<len2;j++) { if(A[i]==B[j]) { if(i>0&&j>0) num[i][j]=num[i-1][j-1]+1; else num[i][j]=1; } } } for(i=0;i<len1;i++) { for(j=0;j<len2;j++) { length=length>num[i][j]?length:num[i][j]; } }
16

剑云雨啸

ACM 算法总结

return length; }

4.6、可中断最长字串
char x[10000],y[10000]; int m,n; void LCSLength(int m,int n,char *x,char *y,int **c,int **b) { int i,j; for(i=0;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) { if(x[i-1]==y[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } int LCSchange(char x[],char y[]) 序满足 { int i; m=strlen(x);
17

//比较的两个字符串允许匹配中间有任意字符间断只要顺

剑云雨啸

ACM 算法总结

n=strlen(y); int **ptrc=new int*[m+1]; int **ptrb=new int*[m+1]; for(i=0;i<=m;i++) { ptrc[i]=new int[n+1]; ptrb[i]=new int[n+1]; } LCSLength(m,n,x,y,ptrc,ptrb); return ptrc[m][n];

}

4.7、从数组中取定值
#define MAX_NUM 50 int log1[MAX_NUM]; int index1 = 0; //要足够大 //记录和数 //log[]数组的当前指针

void calc1(int *nArr, //数组, int start , //数组起始元素下标, int nArrLen , //数组长度, int sum) { if (sum == 0) { for(int j = 0; j < index1; j++) printf("%d ", log1[j]); printf("\n"); } else { for(int i = start; i < nArrLen; i++) { log1[index1++] = nArr[i]; calc1(nArr, i+1, nArrLen, sum - nArr[i]); } } index1--; }
18

剑云雨啸

ACM 算法总结

4.8、最近点对
#include <cstdio> #include <string> #include <cstdlib> #include <cmath> typedef struct { double x, y; } Point; Point p[100001]; int N, q[100000]; int init (); double b_search ( int, int ); inline double dist ( int i, int j ) { double x = sqrt ( ( p[i].x - p[j].x ) * ( p[i].x - p[j].x ) + ( p[i].y - p[j].y ) * ( p[i].y - p[j].y ) ); return x; } inline double min ( double a, double b ) { return a > b ? b : a; } int cmpx ( const void *a, const void *b ) { Point *A = ( Point * ) a, *B = ( Point * ) b; return A->x > B->x; } int cmpq ( const void *a, const void *b ) { int *A = ( int * ) a, *B = ( int * ) b; return p[*A].y > p[*B].y; }

19

剑云雨啸

ACM 算法总结

int init () { scanf ( "%d", &N ); int i; for ( i = 0; i < N; i ++ ) { scanf ( "%lf%lf", &p[i].x, &p[i].y ); } qsort ( p, N, sizeof ( p[0] ), cmpx ); return N; } double b_search ( int l, int r ) { if ( l == r - 1 ) { return dist ( l, r ); } else if ( l == r - 2 ) { return min ( dist ( r, l + 1 ), min ( dist ( l, r ), dist ( l, l + 1 ) ) ); } else { int mid = ( l + r ) / 2; double cur_min = min ( b_search ( l, mid ), b_search ( mid + 1, r ) ); int size = 0; int i; for ( i = mid - 1; i >= l && p[mid + 1].x - p[i].x < cur_min; i -- ) { q[size ++] = i; } for ( i = mid + 1; i <= r && p[i].x - p[mid].x < cur_min; i ++ ) { q[size ++] = i; } qsort ( q, size, sizeof ( q[0] ), cmpq ); int j; for ( i = 0; i < size - 1; i ++ ) { for ( j = i + 1; j < size && p[q[j]].y - p[q[i]].y < cur_min; j ++ ) { cur_min = min ( cur_min, dist ( q[i], q[j] ) );
20

剑云雨啸

ACM 算法总结

} } return cur_min; } }

int main () { while ( init () ) { printf ( "%0.2f\n", b_search ( 0, N - 1 ) / 2 ); } return 0; }

4.9、24 点
#include <iostream> #include <string> #include <cmath> using namespace std; const double PRECISION = 1E-6; //误差值 const int COUNT_OF_NUMBER = 4; //进行游戏的数据个数 const int NUMBER_TO_CAL = 24; //要达到的数据 double number[COUNT_OF_NUMBER]; //存放运算数据 string expression[COUNT_OF_NUMBER]; //动态字符串,每串的首位置是对应个第几个数 据 bool Search(int n) { if (n == 1) { if ( fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) //判别部分 { cout << expression[0] << endl; //当误差没有的时候输出结果保存的字符串 return true; } else { return false;
21

剑云雨啸

ACM 算法总结

} } for (int i = 0; i < n; i++) //递归主要算法部分 { for (int j = i + 1; j < n; j++) { double a, b; string expa, expb; a = number[i]; b = number[j]; number[j] = number[n - 1]; expa = expression[i]; expb = expression[j]; expression[j] = expression[n - 1]; expression[i] = '(' + expa + '+' + expb + ')'; number[i] = a + b; if ( Search(n - 1) ) return true; expression[i] = '(' + expa + '-' + expb + ')'; number[i] = a - b; if ( Search(n - 1) ) return true; // // // expression[i] = '(' + expb + '-' + expa + ')'; number[i] = b - a; if ( Search(n - 1) ) return true;

expression[i] = '(' + expa + '*' + expb + ')'; number[i] = a * b; if ( Search(n - 1) ) return true; if (b != 0) { expression[i] = '(' + expa + '/' + expb + ')'; number[i] = a / b; if ( Search(n - 1) ) return true; } if (a != 0) { expression[i] = '(' + expb + '/' + expa + ')'; number[i] = b / a; if ( Search(n - 1) ) return true;
22

// // // //

剑云雨啸

ACM 算法总结

//

} number[i] = a; number[j] = b; expression[i] = expa; expression[j] = expb; } } return false;

} void main() { for (int i = 0; i < COUNT_OF_NUMBER; i++) { 字符串的形式存放在对应的字符串中 char buffer[20]; int x; cin >> x; number[i] = x; itoa(x, buffer, 10); expression[i] = buffer; } if ( Search(COUNT_OF_NUMBER) ) { cout << "Success." << endl; } else { cout << "Fail." << endl; } }

//存放数据到数组里面并且把数据以

//如果返回正确则输出成功,否则输出失败

4.10、01 背包 极大界定 原始算法
问题描述:N 件物品和一个容量为 V 的背包,第 i 件的物品的费用是 C[i],价值是 w[i]。求 那些物品装入背包可使总价值和最大。最基本的背包问题:每种物品仅有一件,可以选择 放或者不放。 注意恰好和极大的区别仅仅在于存放价值数组 F 的初始化, 为 i 的项是否为 0 决定了组成和 容量值差 i 的组成是否合法, 于是把 F[0]项目初始化为 0 就是在刚好组成的情况中考虑组成 的最大值问题。而且刚好这种情况可以用来代替其他组成算法。 #include<stdio.h> #include<string.h> #define MAX 20 int N,V; //物品数量和容量
23

剑云雨啸

ACM 算法总结

int C[MAX]; //费用 int W[MAX]; //价值 int f[MAX][MAX]; //存放价值 int x[MAX]; //求黑箱组成 int i,j; //变量 int kongjian; //求黑箱组成

int Bei01Budeng(int N,int V) //参数是物品数量和容量,X 数组表示组成,F[N][V]表示最大 价值 { memset(C,0,sizeof(C)); memset(W,0,sizeof(W)); memset(f,0,sizeof(f)); for(i=1;i<=N;i++) { scanf("%d%d",&C[i],&W[i]); } //存放最大价值 for(i=1;i<=N;i++) { for (j=1;j<=V;j++) { if (C[i]<=j) { if (W[i]+f[i-1][j-C[i]]>f[i-1][j]) { f[i][j]=W[i]+f[i-1][j-C[i]]; } else f[i][j]=f[i-1][j]; } else f[i][j]=f[i-1][j]; } } /* 测试 F 数组生成是否 OK for(i=0;i<=N;i++) { for(j=0;j<=V;j++) { printf("%5d",f[i][j]);
24

剑云雨啸

ACM 算法总结

} printf("\n"); }*/ //输出最大值 printf("max=%d\n",f[N][V]); //解析存放物件 kongjian=V; memset(x,0,sizeof(x)); //x[i]为 1 表示第 I 个物品的采用 for(i=N;i>0;i--) { if(f[i][kongjian]==f[i-1][kongjian]) x[i]=0; else { x[i]=1; kongjian-=C[i]; } }

//输出组成 for(i=0;i<=N;i++) { if(x[i]) printf("%d ",i); }

return 0; } int main() { while(scanf("%d%d",&N,&V)!=EOF) { Bei01Budeng(N,V); } return 0; }
25

剑云雨啸

ACM 算法总结

/* 5 10 26 23 65 54 46 */

4.11、01 背包 极大界定 空间优化
#include<stdio.h> #include<string.h> #define MAX 20 int N,V; //物品数量和容量 int C[MAX]; //费用 int W[MAX]; //价值 int f[MAX]; //存放价值 int x[MAX]; //求黑箱组成 int i,j; //变量 int kongjian; //求黑箱组成

int Bei01BudengYouHua(int N,int V) //参数是物品的数量和可容纳的空间,F 数组最后一个 数据是最大值 { memset(C,0,sizeof(C)); memset(W,0,sizeof(W)); memset(f,0,sizeof(f)); for(i=1;i<=N;i++) scanf("%d%d",&C[i],&W[i]); //存放最大价值 for(i=1;i<=N;i++) { for (j=V;j>=0;j--) { if(C[i]<=j&&W[i]+f[j-C[i]]>f[j]) f[j]=W[i]+f[j-C[i]];
26

剑云雨啸

ACM 算法总结

} } //输出最大值 printf("max=%d\n",f[V]); return 0; } int main() { while(scanf("%d%d",&N,&V)!=EOF) Bei01BudengYouHua(N,V); return 0; } /* 5 10 26 23 65 54 46 */

4.12、01 背包 恰好装满 附带组成
#include<stdio.h> #include<string.h> #define MAX 20 int N,V; //物品数量和容量 int C[MAX]; //费用 int W[MAX]; //价值 int f[MAX][MAX]; //存放价值 int x[MAX]; //求黑箱组成 int i,j; //变量 int kongjian; //求黑箱组成

int Bei01Budeng(int N,int V) //参数是 { memset(C,0,sizeof(C)); memset(W,0,sizeof(W)); memset(f,-10000,sizeof(f)); for(i=0;i<=N;i++)
27

剑云雨啸

ACM 算法总结

{ f[i][0]=0; } for(i=1;i<=N;i++) { scanf("%d%d",&C[i],&W[i]); } //存放最大价值 for(i=1;i<=N;i++) { for (j=1;j<=V;j++) { if (C[i]<=j) { if (W[i]+f[i-1][j-C[i]]>f[i-1][j]) { f[i][j]=W[i]+f[i-1][j-C[i]]; } else f[i][j]=f[i-1][j]; } else f[i][j]=f[i-1][j]; } } /* 测试 F 数组生成是否 OK for(i=0;i<=N;i++) { for(j=0;j<=V;j++) { printf("%5d",f[i][j]); } printf("\n"); }*/ //输出最大值 printf("max=%d\n",f[N][V]); //解析存放物件 kongjian=V; memset(x,0,sizeof(x)); //x[i]为 1 表示第 I 个物品的采用
28

剑云雨啸

ACM 算法总结

for(i=N;i>0;i--) { if(f[i][kongjian]==f[i-1][kongjian]) x[i]=0; else { x[i]=1; kongjian-=C[i]; } }

//输出组成 for(i=0;i<=N;i++) { if(x[i]) printf("%d ",i); } return 0; } int main() { while(scanf("%d%d",&N,&V)!=EOF) { Bei01Budeng(N,V); } return 0; } /* 5 10 26 23 65 54 46 */

29

剑云雨啸

ACM 算法总结

4.13、01 背包 恰好装满 空间优化
#include<stdio.h> #include<string.h> #define MAX 20 int N,V; //物品数量和容量 int C[MAX]; //费用 int W[MAX]; //价值 int f[MAX]; //存放价值 int x[MAX]; //求黑箱组成 int i,j; //变量 int kongjian; //求黑箱组成

int Bei01BudengYouHua(int N,int V) //参数是物品的数量和可容纳的空间,F 数组最后一个 数据是最大值 { memset(C,0,sizeof(C)); memset(W,0,sizeof(W)); memset(f,-10000,sizeof(f)); f[0]=0; for(i=1;i<=N;i++) scanf("%d%d",&C[i],&W[i]); //存放最大价值 for(i=1;i<=N;i++) { for (j=V;j>=0;j--) { if(C[i]<=j&&W[i]+f[j-C[i]]>f[j]) f[j]=W[i]+f[j-C[i]]; } } //输出最大值 printf("max=%d\n",f[V]); kongjian=V; memset(x,0,sizeof(x)); return 0; } int main() {
30

剑云雨啸

ACM 算法总结

while(scanf("%d%d",&N,&V)!=EOF) Bei01BudengYouHua(N,V); return 0; } /* 5 10 26 23 65 54 46 */

4.14、完全背包 恰好装满 买咖啡题
问题描述:有 N 中物品和一个容量为 V 的背包,每种物品都有无限件可用。第 i 件物品的 容量是 C[i], 价值是 w[i]。 求解将哪些物品装入背包可使这些物品的容量总和不超过背包容 量,且价值总和最大。 第二个循环是顺序就是完全背包,数量不定,逆序是 01 背包,数量唯一。 基本思路: 这个问题非常类似于 01 背包问题,所不同的是每种物品有无限件。也就是从每件物品的角 度考虑,与它相关的策略不是可取与不可取,而是取多少的问题。我的想法是可以将数据全 部存放进一个地方,让 10 件相同的物品分成 10 次储存,这样的话和 01 背包问题就一摸一 样了,但是这样的话导致了空间时间复杂度多的要死。于是需要优化。 #include<stdio.h> #include<string.h> #define MAX_LEN 10001 #define number 4 //物品个数,可自己输入 const int COINS[number+1] ={0,25, 10, 5, 1}; //数组下标从 1 开始,次序越前,优先级越高, 可自动生成(用性价比排序) ,也可手动定义,本质就是消费 int dp[MAX_LEN]; int dp_path[number+1][MAX_LEN]; int a[number+1]; //存放各个价值的数量 int totalsum; //要求达到的值 int i,j; void dp_procedure() {
31

剑云雨啸

ACM 算法总结

//初始化 memset(dp, -1, sizeof(dp)); memset(dp_path, 0, sizeof(dp_path)); dp[0] = 0; for(i=1;i<=number;i++) { for(j=0;j<=totalsum;j++) { if (dp[j]!=-1&&j+COINS[i]<=totalsum&&dp_path[i][j]<a[i]) { if (dp[j+COINS[i]]==-1||dp[j]+1>dp[j+COINS[i]]) { dp[j+COINS[i]] = dp[j] + 1; dp_path[i][j+COINS[i]] = dp_path[i][j] + 1; } } } } } void print_ans() { if (dp[totalsum]==-1) { printf("不能组成!\n"); return ; } int ans[number+1]; int tmpsum = totalsum; for (i=number;i>=1;i--) { ans[i] = dp_path[i][tmpsum]; tmpsum -= COINS[i]*ans[i]; } for(i=1;i<=number;i++) { printf("%d\t",ans[i]); } printf("\n"); } int main() {
32

剑云雨啸

ACM 算法总结

while (scanf("%d", &totalsum)!=EOF&&totalsum) { for(i=1;i<=4;i++) scanf("%d", a+i); dp_procedure(); print_ans(); } return 0; }

4.15、完全背包 极大界定 原始算法
#include<stdio.h> #include<string.h> #define MAX 31 int thing[MAX][2],v[MAX][MAX]={0};//thing[][0] 表示重量 thing[][1]表示价值 , 后面用来存 放前多少空间最多存放的价值 int x[MAX]; int n,m; //物品的个数以及空间的最大数值 int i,j; int kongjian; int wanquanbeibao() { memset(x,0,sizeof(x)); memset(v,0,sizeof(v)); for(i=1;i<=n;i++) scanf("%d%d",&thing[i][0],&thing[i][1]); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { v[i][j]=v[i-1][j]; if(thing[i][0] <= j) { if((v[i][j-thing[i][0]]+thing[i][1]) > v[i][j]) { v[i][j]=v[i][j-thing[i][0]]+thing[i][1]; } } } }
33

剑云雨啸

ACM 算法总结

printf("%d\n",v[n][m]); kongjian=m; for(i=n;i>0;i--) { while(v[i][kongjian]!=v[i-1][kongjian]) { x[i]++; kongjian-=thing[i][0]; } } for(i=1;i<=n;i++) { printf("%d %d\t",i,x[i]); } return 0; } int main() { while(scanf("%d%d",&n,&m)) wanquanbeibao(); return 0; }

4.16、背包扩展 等价匹配种数统计
/* 输入的第一行是麦克想要交换得到的价值和他拥有的卡片 然后没张卡片一行,分别是卡片的价值和卡片的数量。 求有多少种可能交换。 */ #include<stdio.h> struct Card{ int p, cnt; } card[20] ; int n, m, ans;

34

剑云雨啸

ACM 算法总结

void dfs( int left, int pos ) { if( left == 0 ){ ++ans ; return ; } int i ; for( i=pos; i<m; ++i ){ if( card[i].cnt ){ --card[i].cnt ; dfs( left-card[i].p, i ) ; ++card[i].cnt ; } } } int main() { int i, cases ; for( cases=0; EOF != scanf("%d%d",&n,&m); ++cases ) { for( i=0; i<m; ++i ) { scanf("%d%d", &card[i].p, &card[i].cnt ); } ans = 0 ; dfs( n, 0 ) ; if( cases ) printf("\n"); printf("%d\n", ans ); } return 0 ; }

五、串
5.1、KMP 算法
void getNext(char pat[], int next[]) //字串和匹配数据储存数组 { int j=0;
35

剑云雨啸

ACM 算法总结

for(int i=0;pat[i];i++) { if(i==0) next[i]=-1; else { if(pat[i]==pat[j]) { ++i; ++j; next[i]=j; } else j=next[j]; } } } int KMP(char *str, char*pat, int *next) // 母串 字串 匹配数组 { int i=0,j=0; while(str[i]) { if(pat[j]==0) return i-j; if(j==0 || str[i]==pat[j]){ ++i; ++j; } else j=next[j]; } if(pat[j]==0) return i-j; return -1; }

六、高精度算法
6.1 通用函数
#include<stdio.h> #include<string.h> char c[2000];//全局变量,存储大数运算的结果 char arr[1000];//高精度除以高精度的余数 36

剑云雨啸 long z=0;//高精度除以低精度的余数 int Judge(char ch[]) {//判断字符串 ch 是否全为 0,若全为 0,返回 0,否则返回 1 inti,k; k=strlen(ch); for(i=0;i<k;i++) if(ch[i]!='0') return 0; return 1; } int Compare(char a[],char b[]) {//比较字符串的大小,方法不同于 strcmp 函数,类似于整型常量的比较 intlena,lenb,i; lena=strlen(a); lenb=strlen(b); if(lena<lenb) return -1; else if(lena>lenb) return 1; else { if(strcmp(a,b)==0) return 0; else { for(i=0;i<lena;i++) { if(a[i]>b[i]) return 1; if(a[i]<b[i]) return -1; } return 0; } } }

ACM 算法总结

6.2、高精度加法
/*算法:先确定 a 和 b 中的最大位数 k,然后依照由低至高位的顺序进行加法运算。注意进位,若高位有 进位,则 c 的长度为 k+1。*/ voidBigNumberAdd(char a1[],char b1[]) { inti,j,k,lena,lenb; 37

剑云雨啸 int a[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); //将加数与被加数化为整型数组,并且该数组的其他位为 for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0';

ACM 算法总结

//当数组除了加数和被加数以外的整型数组元素均为 0 时,无需考虑 lena 和 lenb 的大小 k=lena>lenb?lena:lenb; for(i=0;i<k;i++) { d[i]=a[i]+b[i]+d[i]; d[i+1]=d[i+1]+d[i]/10; d[i]=d[i]%10; } //若高位进 while(d[k]) k++; while(!d[k-1]) k--;//001+0003=4 //将整型数组逆着转变并赋值给 c 字符型数组 for( j=0;j<k;j++) c[ j]=d[k-j-1]+'0'; if(Judge(c))//若全为 0,则只输出一个 strcpy(c,"0"); }

6.3、高精度减法
/*算法:依照由低位至高位的顺序进行减法运算。在每次位运算中,若出现不够减的情况,则向高位借位。 在进行了 la 的减法后,若最高位为 0,则 a 的长度减。若 A、B 大小未知,则需先判断大小。*/ voidBigNumberSub(char a1[],char b1[]) {//a1 为被减数,b1 为减数 intlena,lenb,i,j,k,flag; int a[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); if(Compare(a1,b1)>=0) {//若被减数大于等于减数 for(i=0;i<lena;i++) a[i]=a1[lena-1-i]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; 38

剑云雨啸 flag=0;//结果正的标志 } else {//若被减数小于减数 for(i=0;i<lenb;i++) a[i]=b1[lenb-1-i]-'0'; for(i=0;i<lena;i++) b[i]=a1[lena-1-i]-'0'; flag=1;//结果负的标志 } k=lena>lenb?lena:lenb; for(i=0;i<k;i++) {//大数减小数 if(a[i]<b[i]) {//若被减数不够减,向高位借一位 a[i+1]--; d[i]=a[i]-b[i]+10; } else d[i]=a[i]-b[i]; } //若较高位已为 0,并且不止 1 位时 while(!d[i-1]) { k--; i--; } //根据 flag,输出有无"-" if(!flag) { for(i=0;i<k;i++) {//将结果转化为字符逆着赋给数组 c if(!i&&!d[k-i-1])//若差的第一个字母为 0,则马上跳过 continue; c[i]=d[k-i-1]+'0'; } } else { c[0]='-'; for(i=1;i<=k;i++) {//将结果转化为字符逆着赋给数组 c if(i==1&&!d[k-i])//若差的第一个字母为 0,则马上跳过 continue;

ACM 算法总结

39

剑云雨啸 c[i]=d[k-i]+'0';//注意 d 的下标,不是 k-i-1 } } if(Judge(c))//若差全为 0,则只输出一个 strcpy(c,"0"); }

ACM 算法总结

6.4、高精度乘法--高精度乘以低精度
/*算法:将多位数存入数组,低位在前、高位在后,然后用一位数去乘数组的各位,考虑进位,最后按正 常顺序输出*/ voidBigNumMultiSmall(char a1[],int b1) { inti,j,t; int a[2000]={0}; //将字符串转化为整型数组,并逆置 t=strlen(a1); for(i=0;i<t;i++) a[i]=a1[t-1-i]-'0'; //整型数组的每个元素乘以 b1,然后对其进行求余,整除,使其只有一位数 a[0]=a[0]*b1; for(i=1;i<t;i++) { a[i]*=b1; a[i]+=a[i-1]/10; a[i-1]=a[i-1]%10; } while(a[i-1]>9) {//若最后一个元素大于 9 a[i]=a[i-1]/10; a[i-1]=a[i-1]%10; i++; } //将得到的整型数组逆置赋给字符串 for( j=0;j<i;j++) c[ j]=a[i-j-1]+'0'; if(Judge(c))//若积全为 0,则只输出一个 0 strcpy(c,"0"); }

40

剑云雨啸

ACM 算法总结

6.5、高精度乘法--高精度乘以高精度
voidBigNumMultiBig(char a1[],char b1[]) { inti,j,k,lena,lenb; int a[1000]={0},b[1000]={0},d[2000]={0}; //将字符串转化为整型数组,并逆置 lena=strlen(a1); lenb=strlen(b1); for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-i-1]-'0'; //计算乘数从低位到高位以此乘以被乘数的低位到高位 for(i=0;i<lena;i++) for( j=0;j<lenb;j++) { d[i+j]=d[i+j]+a[i]*b[ j]; d[i+j+1]+=d[i+j]/10; d[i+j]=d[i+j]%10; } //根据高位是否为判断整型数组的位数 k=lena+lenb; while(!d[k-1]) k--; //积转化为字符型 for(i=0;i<k;i++) c[i]=d[k-1-i]+'0'; if(Judge(c))//若积全为 0,则只输出一个 1 strcpy(c,"0"); }

6.6、整型常量的阶乘
voidBigNumFact(int x) { inti,k,m=0,a[1000]={0}; a[0]=1; for(;x;x--) {//m 为在求阶乘过程中 a 的元素个数 for(k=i=0;i<=m;i++) { 41

剑云雨啸 k=k+a[i]*x;//数组各个元素均乘以 x(x 递减),以完成阶乘的运算 a[i]=k%10; k/=10; } while(k) { a[++m]=k%10; k/=10; } } //阶乘的结果转化为字符型 for(i=0;i<=m;i++) c[i]=a[m-i]+'0'; if(Judge(c))//若结果全为,则只输出一个 strcpy(c,"0"); }

ACM 算法总结

6.7、整型常量的阶乘和
void BigNumFactAdd(int t) //可以改进,减少算法时间复杂度 { int i; char sum[2000],d[2000]; //对字符串进行初始化 memset(d,0,sizeof(d)); memset(sum,0,sizeof(sum)); //分别求出相应 i 的阶乘然后相加 for(i=t;i>0;i--) { BigNumFact(i); //调用大数乘法。可以减少时间复杂度 strcpy(d,c); memset(c,0,sizeof(c)); BigNumberAdd(d,sum); strcpy(sum,c); memset(c,0,sizeof(c)); } strcpy(c,sum);//将结果赋值给全局变量,进行输出 }

6.8、高精度的乘方,幂数为整型常量
voidBigNumInvol(char a1[],int b1) 42

剑云雨啸 { int i; char temp[1000]; strcpy(temp,a1);//注意乘方是自己乘自己,而不是结果乘结果 for(i=2;i<b1;i++) { BigNumMultiBig(a1,temp); strcpy(temp,c); memset(c,0,sizeof(c));//将 c 清空,防止出现错误 } //进行最后一次乘法 BigNumMultiBig(a1,temp); if(Judge(c))//若结果全为 0,则只输出一个 0 strcpy(c,"0"); }

ACM 算法总结

6.9、高精度除法--高精度除以低精度,只产生余数
intBigNumDividSmall(char a1[],int b1) { if(!b1) return 0; inti,j,k,flag=0,a[1000]={0}; char b[2000]; memset(b,0,sizeof(b)); k=strlen(a1); for(i=0;i<k;i++) a[i]=a1[i]-'0'; z=0; for(i=0;i<k;i++) { z=a[i]+z*10; b[i]=z/b1+'0'; z=z%b1; } i=j=0; while(b[i++]=='0'); for(i=i-1;i<k;i++) c[ j++]=b[i]; return 1; }

43

剑云雨啸

ACM 算法总结

6.10、高精度除法--高精度除以高精度,只产生余数
voidBigNumDividBig(char a1[],char b1[]) { char a[1000],b[1000],time[1000]; int lena1,lentime,i,j,k,flag=0; memset(arr,0,sizeof(arr)); //若被除数小于除数,则商为,余数为被除数 if(Compare(a1,b1)<0) strcpy(arr,a1); //若两数相等,则商为,余数为 else if(!Compare(a1,b1)) c[0]='1'; //若被除数大于除数 else { j=lentime=0; lena1=strlen(a1); memset(b,0,sizeof(b)); memset(time,0,sizeof(time)); for(i=0;i<lena1;i++) {//计算得到被除数的前几位,得到整型数组形式的商 //time 的一个元素表示一次相除的商 b[ j++]=a1[i]; flag=0; while(Compare(b,b1)>=0) { BigNumberSub(b,b1); strcpy(b,c); memset(c,0,sizeof(c)); time[lentime]++; flag=1;//控制 time 的元素的位置 } if(flag)//将商转换为字符 time[lentime]+='0'; else//当被除数前几位小于除数,商补 time[lentime]='0'; if(!strcmp(b,"0"))//若 b 为‘’ j=0; else//继续在 b 的后面加值 j=strlen(b); lentime++; }

44

剑云雨啸 k=0; for(i=0;i<lentime;i++) if(time[i]!='0') break;//找到 time 数组中第一个不为的位置 for( j=i;j<lentime;j++) c[k++]=time[ j]; strcpy(arr,b); } if(Judge(c)) strcpy(c,"0"); if(Judge(arr)) strcpy(arr,"0"); }

ACM 算法总结

七、排序搜索
7.1、插入排序
void INSERTION(int A[]) //以排序数组作为参数,首元素储存长度 { int i,j,key; for(j=2;j<=A[0];j++) //从数组的第二个元素开始作为比较遍历的主体 { key=A[j]; //将比较的主体数据保存起来 i=j-1; //每次从比较主体的前面的一位作为比较的开始端口向前移动 while(i>0&&A[i]>key) //当向前没有推到顶端或者是向前推没有找到一个比比较 主体的数据要小的数值 { A[i+1]=A[i]; //把比较后不符合的数值向后移动一位, 即比较主体的数据理应 是插在该不比比较数据小的位序之前 i--; //标记减少,i 向前移动 } A[i+1]=key; //找到了比比较主体小的数值或者是找到顶端的时候,将比较主体插 在相对应的位置 } }

45

剑云雨啸

ACM 算法总结

7.2、堆排序
#define max 20 int heapsize; int PARENT(int i) //将当前元素的下标作为参数,返回父母元素的对应数组下标 { return i/2; } int LEFT(int i) //将当前元素下标作为参数和父节点,返回左孩子对应的数组元素下标 { return 2*i; } int RIGHT(int i) //将当前元素下标作为参数和父节点,返回右孩子对应的数组元素下标 { return 2*i+1; } void MAXHEAPIFY(int A[],int i) //保持堆的最大性质,假如父节点比孩子大,则交换,而 且以子节点作为新的父节点判断,假如父节点就是最大堆,则结束循环。 { int l; int r; int largest,temp; l=LEFT(i); r=RIGHT(i); if(l<=heapsize&&A[l]>A[i]) largest=l; else largest=i; if(r<=heapsize&&A[r]>A[largest]) largest=r; if(largest!=i) { temp=A[i]; A[i]=A[largest]; A[largest]=temp; MAXHEAPIFY(A,largest); } } void BUILDMAXHEAPIFY(int A[]) //建堆 { int i;
46

剑云雨啸

ACM 算法总结

heapsize=A[0]; for(i=A[0]/2;i>=1;i--) MAXHEAPIFY(A,i); } void HEAPSORT(int A[]) //堆排序主函数,以排序数组作为参数,首元素表示长度 { int i,temp; BUILDMAXHEAPIFY(A); for(i=A[0];i>=2;i--) { temp=A[1]; A[1]=A[i]; A[i]=temp; heapsize--; MAXHEAPIFY(A,1); } }

7.3、合并排序(分治)
void MERGE(int A[],int p,int q,int r) { int i,j,k; int n1=q-p+1; //参与合并的第一个数组的长度 int n2=r-q; //参与合并的第二个数组的长度 int L[MAX]; //int L[n1+1]; //定义一个用来储存第一个数组内容的数组 int R[MAX];// int R[n2+2]; //定义一个用来储存第二个数组内容的数字 for(i=1;i<=n1;i++) L[i]=A[p+i-1]; //将数组内容分开拷贝保存 for(j=0;j<=n2;j++) R[j]=A[q+j]; L[n1+1]=MAX; //设置最后一位为正无穷 R[n2+1]=MAX; i=1; j=1; for(k=p;k<=r;k++) //通过比较插入 { if(L[i]<=R[j]) { A[k]=L[i]; i++; }
47

剑云雨啸

ACM 算法总结

else { A[k]=R[j]; j++; } } } void MERGESORT(int A[],int p,int r)//主函数,三个整形变量分别存放第一段的头部,第一段 的尾部和第二段的尾部 { int q; if(p<r) { q=(p+r)/2; MERGESORT(A,p,q); //递归的每一次都分为前半部分和后半部分 MERGESORT(A,q+1,r); MERGE(A,p,q,r); //排序函数 } }

7.4、计数排序
void COUNTSORT(int A[],int B[],int k) //A 是输入的数组元素储存地址,B 是结果输出元素 储存地址,K 是在所有的输入的元素之中最大值都不能超越的一个大数 { int i,j; int C[MAX]; //临时储存数据 for(i=0;i<=k;i++) //初始化为 0 C[i]=0; for(j=1;j<=A[0];j++) //包含等于 i 的元素的个数 C[A[j]]=C[A[j]]+1; for(i=1;i<=k;i++) //包含小于或等于 i 的个数 C[i]=C[i]+C[i-1]; for(j=A[0];j>=1;j--) //在结果数组中放入结果数据 { B[C[A[j]]]=A[j]; //在 B 中指定的位置存放 C[A[j]]所指的数据 A[j] C[A[j]]=C[A[j]]-1; //位序自减 1 } }

48

剑云雨啸

ACM 算法总结

7.5、冒泡排序
void BUBBLESORT(int A[])//在 A[0]处放数组的长度 { int i,j,temp; for(i=1;i<A[0];i++) { for(j=A[0];j>i;j--) { if(A[j]<A[j-1]) //从尾部开始往前比较,并调整顺序 { temp=A[j]; A[j]=A[j-1]; A[j-1]=temp; } } } }

7.6、快速排序
void quickSort(int* arr,int startPos, int endPos) //第一个参数为排序的字符串,第二个为开始排 序的位置,第三个为结束排序的元素位置 { int i,j; int ch; ch=arr[startPos]; i=startPos; j=endPos; while(i<j) { while(arr[j]>=ch && i<j)--j; arr[i]=arr[j]; while(arr[i]<=ch && i<j)++i; arr[j]=arr[i]; } arr[i]=ch; if(i-1>startPos) quickSort(arr,startPos,i-1); if(endPos>i+1) quickSort(arr,i+1,endPos); }
49

剑云雨啸

ACM 算法总结

7.7、二分搜索
int BinarySearch(int a[],int x,int n) //在数组中寻找等于 X 的数据, 倘若相等, 则返回该值的位 置,n 是数据个数 { int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } return -1; }

八、技巧
8.1、输入技巧
scanf("%[^'/']",a); 把不是斜杠的放到 a 中,不用再麻烦半天写一堆条件了。 本来想找关于“%[]”的知识,百度 google 都没收录这个,不想再在输入输出网页中找了。 还有%[^\n]表示把换行前的都放入字符串中。

50

剑云雨啸

ACM 算法总结

8.2、递归
递归限制大概是 1W 多层。

8.3、位运算
》除 2 的个数 《乘以 2 的个数 ^异或

8.4、字典序
最小则是从大往小排,最大则是从小往大。

8.5、省略末尾零
用 COUT 输出就可以了

51



更多相关文章:
ACM程序算法模板
ACM程序算法模板_学科竞赛_高中教育_教育专区。剑云雨啸 ACM 算法总结 ACM 程序算法模板 剑云雨啸 ACM 算法总结 目录一、组合数学...剑云雨啸 ACM 算法总结 ACM...
ACM程序设计大赛常用算法模板
ACM程序设计大赛常用算法模板_IT/计算机_专业资料。本文是对于ACM常用算法模板的整理,汇总得到。首先感谢我的队友,还有浙大搞ACM的先辈们!ACM...
ACM程序模板
图论知识和模板 匈牙利算法: 匈牙利算法 USACO 4.2.2 The Perfect Stall 完美的牛栏 stall4 页 17 ACM 知识准备 最简单的求二分图最大匹配,最朴素的匈牙利算法...
《ACM算法与程序设计》解题报告模板
ACM算法程序设计》解题报告模板ACM算法程序设计》解题报告模板隐藏>> 电子科技大学 期末解题报告 课程: 《ACM 算法程序设计》 学院: 学号: 姓名: 报告...
acm程序设计模板(全)
65页 7下载券 ACM程序设计题目 2页 1下载券 ACM模板 25页 2下载券喜欢...(hungary 邻接表) //二分图最大匹配,hungary 算法,邻接表形式,复杂度 O(m*...
ACM常用算法模板
ACM常用算法模板_计算机软件及应用_IT/计算机_专业资料。专用模板 目录: 一、...程序中用的是 sina(x)/x 需要 math.h 默认精度要求是 1e-5 源程序: ...
2010ACM程序设计模板4.0
ACM 算法模板 79页 1财富值 ACM模板7 24页 免费 ACM模板1 76页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...
上海交通大学ACM算法模板gai
上海交通大学ACM算法模板gai_计算机软件及应用_IT/计算机_专业资料。ACM 算法模板ACM 算法模板集 Contents 一. 常用函数与 STL 二. 重要公式与定理 1. Fibonac...
bobo的ACM算法模板
bobo的ACM算法模板_IT/计算机_专业资料。bobo的ACM算法模板Bobo’s ACM 模板 一些常量和函数: 一些常量和函数: 最大 Long long __int64 INF = ~(((__int64...
ACM模板4
免费模板~~~ 免费模板 2010 ACM 程序竞赛模板 浙江省第七届大学生程序设计竞赛...40 一、图论 1.1.最小生成树类 1.1.最小生成树类 prim 算法第1页 哈嘻...
更多相关标签:
acm常用算法模板    acm算法模板    acm模板    邝斌的acm模板    acm latex 模板    acm论文模板    上海交大acm模板    吉林大学acm模板    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图