ACM.rar_王道资源-CSDN文库

共1个文件

doc：1个

版权申诉

99 浏览量 2022-09-23 10:35:31 上传评论收藏 66KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

ACM.rar （1个子文件）

ACM经典代码.doc 459KB

一．数论..........................................................4

1.阶乘最后非零位 ...............................................4

2. 模线性方程(组) ..............................................4

3. 素数表 .....................................................6

4. 素数随机判定(miller_rabin) ..................................6

5. 质因数分解 ..................................................7

6. 最大公约数欧拉函数 ...........................................8

二．图论_匹配 .....................................................9

1. 二分图最大匹配(hungary 邻接表形式) .............................9

2. 二分图最大匹配(hungary 邻接表形式,邻接阵接口) ..................10

3. 二分图最大匹配(hungary 邻接阵形式) ............................10

4. 二分图最大匹配(hungary 正向表形式) ............................11

5. 二分图最佳匹配(kuhn_munkras 邻接阵形式) .......................11

6. 一般图匹配(邻接表形式).......................................12

7. 一般图匹配(邻接表形式,邻接阵接口) .............................13

8. 一般图匹配(邻接阵形式).......................................14

9. 一般图匹配(正向表形式).......................................15

三．图论_生成树...................................................16

1. 最小生成树(kruskal 邻接表形式) ...............................16

2. 最小生成树(kruskal 正向表形式) ...............................17

3. 最小生成树(prim+binary_heap 邻接表形式) ......................19

4. 最小生成树(prim+binary_heap 正向表形式) ......................20

5. 最小生成树(prim+mapped_heap 邻接表形式) ......................21

6. 最小生成树(prim+mapped_heap 正向表形式) ......................22

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

8. 最小树形图(邻接阵形式).......................................24

四．图论_网络流...................................................25

1. 上下界最大流(邻接表形式) .....................................25

2. 上下界最大流(邻接阵形式) .....................................26

3. 上下界最小流(邻接表形式) .....................................27

4. 上下界最小流(邻接阵形式) .....................................29

5. 最大流(邻接表形式) ..........................................30

6. 最大流(邻接表形式,邻接阵接口).................................31

7. 最大流(邻接阵形式) ..........................................32

8. 最大流无流量(邻接阵形式) .....................................32

9. 最小费用最大流(邻接阵形式) ...................................33

五. 图论_最短路径 .................................................34

1. 最短路径(单源 bellman_ford 邻接阵形式) ........................34

2. 最短路径(单源 dijkstra_bfs 邻接表形式) ........................35

3. 最短路径(单源 dijkstra_bfs 正向表形式) ........................35

4. 最短路径(单源 dijkstra+binary_heap 邻接表形式) ................36

5. 最短路径(单源 dijkstra+binary_heap 正向表形式) ................37

6. 最短路径(单源 dijkstra+mapped_heap 邻接表形式) ................38

7. 最短路径(单源 dijkstra+mapped_heap 正向表形式) ................39

8. 最短路径(单源 dijkstra 邻接阵形式) ............................40

9. 最短路径(多源 floyd_warshall 邻接阵形式) ......................40

六. 图论_连通性 ..................................................41

1. 无向图关键边(dfs 邻接阵形式) .................................41

2. 无向图关键点(dfs 邻接阵形式) .................................42

3. 无向图块(bfs 邻接阵形式) .....................................43

4. 无向图连通分支(bfs 邻接阵形式) ................................43

5. 无向图连通分支(dfs 邻接阵形式) ................................44

6. 有向图强连通分支(bfs 邻接阵形式) ..............................44

7. 有向图强连通分支(dfs 邻接阵形式) ..............................45

8. 有向图最小点基(邻接阵形式) ...................................46

七. 图论_应用 ....................................................46

1.欧拉回路(邻接阵形式) .........................................46

2. 前序表转化 .................................................47

3. 树的优化算法 ...............................................48

4. 拓扑排序(邻接阵形式). .......................................49

5. 最佳边割集 .................................................50

6. 最佳顶点割集 ...............................................51

7. 最小边割集 .................................................52

8. 最小顶点割集 ...............................................53

9. 最小路径覆盖 ...............................................55

八. 图论_NP 搜索 ..................................................55

1. 最大团(n 小于 64)(faster) ...................................55

2. 最大团 ....................................................58

九. 组合 ........................................................59

1. 排列组合生成 ...............................................59

2. 生成 gray 码 ...............................................60

3. 置换(polya) ...............................................61

4. 字典序全排列 ...............................................61

5. 字典序组合 .................................................62

6. 组合公式 ..................................................62

十. 数值计算 .....................................................63

1. 定积分计算(Romberg) ........................................63

2. 多项式求根(牛顿法) ..........................................64

3. 周期性方程(追赶法) ..........................................66

十一. 几何 .......................................................67

1. 多边形 ....................................................67

2. 多边形切割 .................................................70

3. 浮点函数 ..................................................71

4. 几何公式 ..................................................76

5. 面积 ......................................................78

6. 球面 ......................................................79

7. 三角形 ....................................................79

8. 三维几何 ..................................................81

9. 凸包(graham) ..............................................89

10. 网格(pick) ...............................................91

11. 圆 ......................................................92

12. 整数函数 .................................................94

13. 注意 .....................................................96

十二. 结构 .......................................................97

1. 并查集 ....................................................97

2. 并查集扩展(friend_enemy) ...................................98

3. 堆(binary) ...............................................98

4. 堆(mapped) ...............................................99

5. 矩形切割 ..................................................99

6. 线段树 ...................................................100

7. 线段树扩展 ................................................102

8. 线段树应用 ................................................105

9. 子段和 ...................................................105

10. 子阵和 ..................................................105

十三. 其他 ......................................................106

1. 分数 .....................................................106

2. 矩阵 .....................................................108

3. 日期 .....................................................110

4. 线性方程组(gauss) .........................................111

5. 线性相关 .................................................113

十四. 应用 ......................................................114

1. joseph ..................................................114

2. N 皇后构造解 ..............................................115

3. 布尔母函数 ................................................115

4. 第 k 元素 .................................................116

5. 幻方构造 .................................................116

6. 模式匹配(kmp) ............................................118

7. 逆序对数 .................................................118

8. 字符串最小表示.............................................119

9. 最长公共单调子序列 .........................................119

10. 最长子序列 ...............................................120

11. 最大子串匹配 .............................................121

12. 最大子段和 ...............................................122

13. 最大子阵和 ...............................................123

一．数论

1.阶乘最后非零位

//求阶乘最后非零位,复杂度 O(nlogn)

//返回该位,n 以字符串方式传入

#include <string.h>

#define MAXN 10000

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;

}

return ret+ret%2*5;

}

2. 模线性方程(组)

#ifdef WIN32

typedef __int64 i64;

#else

typedef long long i64;

#endif

//扩展 Euclid 求解 gcd(a,b)=ax+by

int ext_gcd(int a,int b,int& x,int& y){

int t,ret;

if (!b){

x=1,y=0;

return a;

}

ret=ext_gcd(b,a%b,x,y);

t=x,x=y,y=t-a/b*y;

return ret;

}

//计算 m^a, O(loga), 本身没什么用, 注意这个按位处理的方法 :-P

int exponent(int m,int a){

int ret=1;

for (;a;a>>=1,m*=m)

if (a&1)

ret*=m;

return ret;

}

//计算幂取模 a^b mod n, O(logb)

int modular_exponent(int a,int b,int n){ //a^b mod n

int ret=1;

for (;b;b>>=1,a=(int)((i64)a)*a%n)

if (b&1)

ret=(int)((i64)ret)*a%n;

return ret;

}

//求解模线性方程 ax=b (mod n)

//返回解的个数,解保存在 sol[]中

//要求 n>0,解的范围 0..n-1

int modular_linear(int a,int b,int n,int* sol){

int d,e,x,y,i;

d=ext_gcd(a,n,x,y);

if (b%d)

return 0;

e=(x*(b/d)%n+n)%n;

for (i=0;i<d;i++)

sol[i]=(e+i*(n/d))%n;

return d;

}

//求解模线性方程组(中国余数定理)

// x = b[0] (mod w[0])

// x = b[1] (mod w[1])

// ...

// x = b[k-1] (mod w[k-1])

//要求 w[i]>0,w[i]与 w[j]互质,解的范围 1..n,n=w[0]*w[1]*...*w[k-1]

int modular_linear_system(int b[],int w[],int k){

int d,x,y,a=0,m,n=1,i;

for (i=0;i<k;i++)

n*=w[i];

for (i=0;i<k;i++){

m=n/w[i];

d=ext_gcd(w[i],m,x,y);

a=(a+y*m*b[i])%n;

}

return (a+n)%n;

}

评论收藏

内容反馈

版权申诉

邓凌佳

粉丝: 65
资源: 1万+

ACM.rar_王道

acm.rar_ACM

ACM.rar_ACM

acm.rar_ACM java_java package acm

zju1048.rar_acm.zju.edu._pid_show_zju acm

ACM.rar_acm zju 2830_acm 网站源码_acm.zju.edu.cn_浙大acm_浙大oj网站

acm.zip_acm72.com网_contour c_www.:acm72.com

ACM.rar_ACM_ACM Hwang .p_ACM java_pku 1689 rubbery_ppt

zju1025.rar_ZJU_acm zju 10_pid_sticks_zju 1025

acm.rar_ACM 语音_ACM控件_acm delphi_delphi6_录音 播放

acm.rar_Fan Problem ACM

ACM.rar_ACM_ACM PDF_ACM pdf

Operation System_ACM.rar

ACM.rar_ACM_acm icpc

hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

ACM-SJTU.rar_ACM_SJTU ACM模板_acm.sjtu_sjtu_sjtu hao yuan acm

最新资源

acm.rar_ACM 语音_ACM控件_acm delphi_delphi6_录音播放