acm常用算法模板

经典ACM算法合集经典ACM算法合集

经典ACM算法合集经典ACM算法合集.txt“我羡慕内些老人羡慕他们手牵手一直走到最后。━交话费的时候，才发现自己的话那么值钱。实验一 统计数字问题
实验二 最大间隙问题
实验三 众数问题
实验四 半数集问题
实验五 集合划分问题
实验六 最少硬币问题
实验七 编辑距离问题
实验八 程序存储问题
实验九 最优服务次序问题
实验十 汽车加油问题
实验十一 工作分配问题
实验十二 0-1背包问题
实验十三 最小重量机器设计问题
实验十四 最小权顶点覆盖问题
实验十五 集合相等问题
实验十六 战车问题
实验一 统计数字问题
1、问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。
2、题目分析：
考虑由0,1,2,…,9组成的所有n位数。从n个0到n个9共有个n位数，在这些n位数中，0,

经典ACM算法合集经典ACM算法合集

经典ACM算法合集经典ACM算法合集.txt“我羡慕内些老人羡慕他们手牵手一直走到最后。━交话费的时候，才发现自己的话那么值钱。实验一 统计数字问题
实验二 最大间隙问题
实验三 众数问题
实验四 半数集问题
实验五 集合划分问题
实验六 最少硬币问题
实验七 编辑距离问题
实验八 程序存储问题
实验九 最优服务次序问题
实验十 汽车加油问题
实验十一 工作分配问题
实验十二 0-1背包问题
实验十三 最小重量机器设计问题
实验十四 最小权顶点覆盖问题
实验十五 集合相等问题
实验十六 战车问题
实验一 统计数字问题
1、问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。
2、题目分析：
考虑由0,1,2,…,9组成的所有n位数。从n个0到n个9共有个n位数，在这些n位数中，0,

ACM Word Template for SIG Site

1st Author

2nd Author

3rd Author

1st author's affiliation 2nd author's affiliation 3rd author's affiliation 1st line of address 1st line of address 1st line of address 2nd line of address 2nd line of address 2nd line of address

Telephone number, incl. country code Telephone number, incl. country code Telephone number, incl. country code

1st author's E-mail address 2nd E-mail

3rd E-mail

ABSTRACT

In this paper, we describe the formatting guidelines for ACM SIG Proceedings.

CCS Concepts

? Infor

ACM Word Template for SIG Site

1st Author

2nd Author

3rd Author

1st author's affiliation 2nd author's affiliation 3rd author's affiliation 1st line of address 1st line of address 1st line of address 2nd line of address 2nd line of address 2nd line of address

Telephone number, incl. country code Telephone number, incl. country code Telephone number, incl. country code

1st author's E-mail address 2nd E-mail

3rd E-mail

ABSTRACT

In this paper, we describe the formatting guidelines for ACM SIG Proceedings.

CCS Concepts

? Infor

1、Dijkstra算法

#include \#include \#define max 20

int mincost(int v[],int d[],int n) { int temp=1000000,i,w=2; for(i=2;i<=n;i++) if(v[i]==0&&d[i]

int main() { int c[max][max]; int d[max],v[max]={0}; int n,i,j,k,w,sum; scanf(\ for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(\ v[1]=1;//原点是1 也可以改 for(i=1;i<=n;i++) d[i]=c[1][i]; for(i=1;i<=n;i++) w=mincost(v,d,n); v[w]=1; for(k=2;k<=n;k++) if(v[k]==0) { sum=d[w]+c[w][k]; if(sum

}

for(i=2;i<=n;i++) printf(\ memset(v,0,max*sizeof(int)); return 0; }

/*从原点出发到其他各个点的最短距离 4

0 2 1 5

2 0 3 100000 1 3 0 4

5 100000 4 0 /*

2、求最小生成树prim算法

#include \#include \#define mvnum 12 #define mvalue 1000 #define menum 20

typedef int vexlist[mvnum];

typedef int adjmaxt[mvnum][mvnum]; int visited[mvnum]={0}; struct edge { int fvex; int evex; int weight; };

type

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

1 / 95

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.0

字符串处理 ........................................... 3

1、KMP 算法 ..................................... 3 2、扩展KMP ..................................... 4 3、Manacher 最长回文子串 ........................ 5 4、AC 自动机 .................................... 5 5、后缀数组 ..................................... 7 6、后缀自动机 ................................... 9 7、字符串HASH ................................. 10 数学 ................................................ 10

1、素

一、数论算法

1．求两数的最大公约数

function gcd(a,b:integer):integer; begin

if b=0 then gcd:=a

else gcd:=gcd (b,a mod b); end ;

2．求两数的最小公倍数

function lcm(a,b:integer):integer; begin

if a

while lcm mod b>0 do inc(lcm,a); end;

3．素数的求法

A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean; var I: integer; begin

for I:=2 to trunc(sqrt(n)) do if n mod I=0 then begin prime:=false; exit; end;

prime:=true; end;

B.判断longint范围内的数是否为素数（包含求50000以内的素数表）： procedure getprime; var

i,j:longint;

p:array[1..50000] of