ACM常用模板及北大ACM-题型分类代码

求欧拉回路或欧拉路,邻接阵形式,复杂度 .......................................................................... 2

大数(整数类封装) ............................................................................................................. 3

二分堆(binary) ................................................................................................................ 11

多边形 ........................................................................................................................... 11

多边形切割--可用于半平面交 ......................................................................................... 15

多项式求根(牛顿法) ....................................................................................................... 16

拓扑排序,邻接阵形式,复杂度 O(n^2) ............................................................................... 30

网格(pick) ....................................................................................................................... 31

线性方程组(gauss) .......................................................................................................... 31

圆 .................................................................................................................................. 33

质因数分解 .................................................................................................................... 35

求置换的循环节,polya 原理............................................................................................. 37

周期性方程(追赶法) ....................................................................................................... 37

子段和--求 sum{[0..n-1]} .................................................................................................. 38

子阵和--求 sum{a[0..m-1][0..n-1]} ..................................................................................... 38

字典序全排列与序号的转换............................................................................................ 39

最大子阵和--求最大子阵和,复杂度 O(n^3) ....................................................................... 45

最小顶点割集................................................................................................................. 46

最小生成树(prim 邻接阵形式) ......................................................................................... 47

北大 ACM-题型分类的代码 ............................................................................................. 48

1、排序 ............................................................................................. 48

2、搜索、回溯、遍历 ........................................................................ 49

3、历法 ............................................................................................. 49

4、枚举 ............................................................................................. 49

5、数据结构的典型算法 ..................................................................... 49

6、 动态规划..................................................................................... 50

13、任意精度运算、数字游戏、高精度计算 ....................................... 52

14、概率统计..................................................................................... 52

15、小费用最大流、最大流................................................................ 52

16、压缩存储的 DP ............................................................................ 52

17、最长公共子串（LCS）.................................................................. 52

18、图论及组合数学 .......................................................................... 53

难题............................................................................................ 60

多解题 ........................................................................................ 61

求欧拉回路或欧拉路,邻接阵形式,复杂度

//求欧拉回路或欧拉路,邻接阵形式,复杂度 O(n^2)

//返回路径长度,path 返回路径(有向图时得到的是反向路径)

//传入图的大小 n 和邻接阵 mat,不相邻点边权 0

//可以有自环与重边,分为无向图和有向图

#define MAXN 100

void find_path_u(int n,int mat[][MAXN],int now,int& step,int* path){

int i;

}

void find_path_d(int n,int mat[][MAXN],int now,int& step,int* path){

int i;

for (i=n-1;i>=0;i--)

while (mat[now][i]){

mat[now][i]--;

find_path_d(n,mat,i,step,path);

}

path[step++]=now;

int euclid_path(int n,int mat[][MAXN],int start,int* path){

int ret=0;

find_path_u(n,mat,start,ret,path);

// find_path_d(n,mat,start,ret,path);

return ret;

#define DEPTH 10000

#define MAX 100

typedef int bignum_t[MAX+1];

int read(bignum_t a,istream& is=cin){

char buf[MAX*DIGIT+1],ch;

int i,j;

memset((void*)a,0,sizeof(bignum_t));

if (!(is>>buf)) return 0;

for (a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)

ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;

for (a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');

void write(const bignum_t a,ostream& os=cout){

int i,j;

for (os<<a[i=a[0]],i--;i;i--)

for (j=DEPTH/10;j;j/=10)

os<<a[i]/j%10;

}

int comp(const bignum_t a,const bignum_t b){

int i;

return a[0]-b[0];

for (i=a[0];i;i--)

if (a[i]!=b[i])

return a[i]-b[i];

return 0;

}

int comp(const bignum_t a,const int c,const int d,const bignum_t b){

int i,t=0,O=-DEPTH*2;

if (b[0]-a[0]<d&&c)

return 1;

for (i=b[0];i>d;i--){

t=t*DEPTH+a[i-d]*c-b[i];

if (t>0) return 1;

if (t<O) return 0;

}

}

void add(bignum_t a,const bignum_t b){

int i;

for (i=1;i<=b[0];i++)

if ((a[i]+=b[i])>=DEPTH)

a[i]-=DEPTH,a[i+1]++;

if (b[0]>=a[0])

a[0]=b[0];

else

for (a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);

for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);

}

void sub(bignum_t a,const bignum_t b){

int i;

void sub(bignum_t a,const int b){

int i=1;

for (a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);

for (;!a[a[0]]&&a[0]>1;a[0]--);

}

void sub(bignum_t a,const bignum_t b,const int c,const int d){

int i,O=b[0]+d;

for (i=1+d;i<=O;i++)

void mul(bignum_t c,const bignum_t a,const bignum_t b){

int i,j;

memset((void*)c,0,sizeof(bignum_t));

for (c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)

for (j=1;j<=b[0];j++)

if ((c[i+j-1]+=a[i]*b[j])>=DEPTH)

c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH;

for (c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);

}