ACM/ICPC常用算法的代码库（吉林大学版，强烈推荐）_打icpc和ccpc单词

icpc

5星 · 超过95%的资源需积分: 50 173 浏览量更新于2023-03-03 评论 4 收藏 645KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

ACM/ICPC 代码库

吉林大学计算机科学与技术学院 2005 级

2007-2008

目录 .............................................. 1

Graph 图论 ........................................ 3

| DAG 的深度优先搜索标记 ............................................. 3

| 无向图找桥 ..................................................................... 3

| 无向图连通度(割) ........................................................ 3

| 最大团问题 DP + DFS ................................................. 3

| 欧拉路径 O(E) ............................................................... 3

| DIJKSTRA 数组实现 O（N^2） ..................................... 3

| DIJKSTRA O(E * LOG E) ............................................. 4

| BELLMANFORD 单源最短路 O(VE) ................................. 4

| SPFA(SHORTEST PATH FASTER ALGORITHM) .............. 4

| 第 K 短路（DIJKSTRA） ................................................. 5

| 第 K 短路（A*） ............................................................ 5

| PRIM 求 MST .................................................................... 6

| 次小生成树 O(V^2) ...................................................... 6

| 最小生成森林问题(K 颗树)O(MLOGM). ...................... 6

| 有向图最小树形图 ......................................................... 6

| MINIMAL STEINER TREE ................................................ 6

| TARJAN 强连通分量 ........................................................ 7

| 弦图判断 ......................................................................... 7

| 弦图的 PERFECT ELIMINATION 点排列 .......................... 7

| 稳定婚姻问题 O(N^2) .................................................. 7

| 拓扑排序 ......................................................................... 8

| 无向图连通分支(DFS/BFS 邻接阵) ............................. 8

| 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) ............ 8

| 有向图最小点基(邻接阵)O(N^2)............................... 9

| FLOYD 求最小环 .............................................................. 9

| 2-SAT 问题 ..................................................................... 9

Network 网络流 ................................... 11

| 二分图匹配（匈牙利算法 DFS 实现） ...................... 11

| 二分图匹配（匈牙利算法 BFS 实现） ...................... 11

| 二分图匹配（HOPCROFT－CARP 的算法） .................. 11

| 二分图最佳匹配（KUHN MUNKRAS 算法 O(M*M*N)） 11

| 无向图最小割 O(N^3) ............................................... 12

| 有上下界的最小(最大)流 .......................................... 12

| DINIC 最大流 O(V^2 * E) ....................................... 12

| HLPP 最大流 O(V^3) ................................................ 13

| 最小费用流 O(V * E * F) ....................................... 13

| 最小费用流 O(V^2 * F) ........................................... 14

| 最佳边割集 ................................................................... 15

| 最佳点割集 ................................................................... 15

| 最小边割集 ................................................................... 15

| 最小点割集（点连通度） ........................................... 16

| 最小路径覆盖 O(N^3) ................................................ 16

| 最小点集覆盖 ............................................................... 16

Structure 数据结构 ............................... 17

| 求某天是星期几 ........................................................... 17

| 左偏树合并复杂度 O(LOG N) ................................... 17

| 树状数组 ....................................................................... 17

| 二维树状数组 ............................................................... 17

| TRIE 树(K 叉) .............................................................. 17

| TRIE 树(左儿子又兄弟) ............................................. 18

| 后缀数组 O(N * LOG N) ............................................ 18

| 后缀数组 O(N) ............................................................ 18

| RMQ 离线算法 O(N*LOGN)+O(1) ............................. 19

| RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法

(O(

NLOGN + Q)) ............................................................. 19

| RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA ............. 19

| LCA 离线算法 O(E)+O(1) ........................................ 20

| 带权值的并查集 ........................................................... 20

| 快速排序 ....................................................................... 20

| 2 台机器工作调度 ........................................................ 20

| 比较高效的大数 ........................................................... 20

| 普通的大数运算 ........................................................... 21

| 最长公共递增子序列 O(N^2) .................................... 22

| 0-1 分数规划 ............................................................... 22

| 最长有序子序列（递增/递减/非递增/非递减） .... 22

| 最长公共子序列 ........................................................... 23

| 最少找硬币问题（贪心策略-深搜实现） ................. 23

| 棋盘分割 ....................................................................... 23

| 汉诺塔 ........................................................................... 23

| STL 中的 PRIORITY_QUEUE .......................................... 24

| 堆栈 ............................................................................... 24

| 区间最大频率 ............................................................... 24

| 取第 K 个元素................................................................ 25

| 归并排序求逆序数 ....................................................... 25

| 逆序数推排列数 ........................................................... 25

| 二分查找 ....................................................................... 25

| 二分查找（大于等于 V 的第一个值）........................ 25

| 所有数位相加 ............................................................... 25

Number 数论 ...................................... 26

|递推求欧拉函数 PHI(I) ............................................... 26

|单独求欧拉函数 PHI(X) ............................................... 26

| GCD 最大公约数 .......................................................... 26

| 快速 GCD ...................................................................... 26

| 扩展 GCD ...................................................................... 26

| 模线性方程 A * X = B (% N) .................................. 26

| 模线性方程组 ............................................................... 26

| 筛素数 [1..N] ............................................................ 26

| 高效求小范围素数 [1..N] ........................................ 26

| 随机素数测试(伪素数原理) ...................................... 26

| 组合数学相关 ............................................................... 26

| POLYA 计数 .................................................................... 27

| 组合数 C(N, R) ........................................................... 27

| 最大 1 矩阵 ................................................................... 27

| 约瑟夫环问题（数学方法） ....................................... 27

| 约瑟夫环问题（数组模拟） ....................................... 27

| 取石子游戏 1 ................................................................ 27

| 集合划分问题 ............................................................... 27

| 大数平方根（字符串数组表示） ............................... 28

| 大数取模的二进制方法 ............................................... 28

| 线性方程组 A[][]X[]=B[] ....................................... 28

| 追赶法解周期性方程 ................................................... 28

| 阶乘最后非零位,复杂度 O(NLOGN) ........................... 29

递归方法求解排列组合问题 ......................... 30

| 类循环排列 ................................................................... 30

| 全排列 ........................................................................... 30

| 不重复排列 ................................................................... 30

| 全组合 ........................................................................... 31

| 不重复组合 ................................................................... 31

| 应用 ............................................................................... 31

模式串匹配问题总结 ............................... 32

| 字符串 HASH .................................................................. 32

| KMP 匹配算法 O(M+N) ............................................... 32

| KARP-RABIN 字符串匹配 ............................................. 32

| 基于 KARP-RABIN 的字符块匹配................................. 32

| 函数名: STRSTR ........................................................... 32

| BM 算法的改进的算法 SUNDAY ALGORITHM ................ 32

| 最短公共祖先（两个长字符串） ............................... 33

| 最短公共祖先（多个短字符串） ............................... 33

Geometry 计算几何 ................................ 34

| GRAHAM 求凸包 O(N * LOGN) .................................... 34

| 判断线段相交 ............................................................... 34

| 求多边形重心 ............................................................... 34

| 三角形几个重要的点 ................................................... 34

| 平面最近点对 O(N * LOGN) ...................................... 34

| LIUCTIC 的计算几何库 ................................................ 35

| 求平面上两点之间的距离 ........................................... 35

| (P1-P0)*(P2-P0)的叉积 ....................................... 35

| 确定两条线段是否相交 ............................................... 35

| 判断点 P 是否在线段 L 上 ............................................ 35

| 判断两个点是否相等 ................................................... 35

| 线段相交判断函数 ....................................................... 35

| 判断点 Q 是否在多边形内 .......................................... 35

| 计算多边形的面积 ....................................................... 35

| 解二次方程 AX^2+BX+C=0 ........................................ 36

| 计算直线的一般式 AX+BY+C=0 ................................. 36

| 点到直线距离 ............................................................... 36

| 直线与圆的交点，已知直线与圆相交 ....................... 36

| 点是否在射线的正向 ................................................... 36

| 射线与圆的第一个交点 ............................................... 36

| 求点 P1 关于直线 LN 的对称点 P2 .............................. 36

| 两直线夹角（弧度） ................................................... 36

ACM/ICPC 竞赛之 STL ............................... 37

ACM/ICPC 竞赛之 STL 简介 .......................................... 37

ACM/ICPC 竞赛之 STL--PAIR ...................................... 37

ACM/ICPC 竞赛之 STL--VECTOR .................................. 37

ACM/ICPC 竞赛之 STL--ITERATOR 简介 ...................... 38

ACM/ICPC 竞赛之 STL--STRING .................................. 38

ACM/ICPC 竞赛之 STL--STACK/QUEUE ........................ 38

ACM/ICPC 竞赛之 STL--MAP ........................................ 40

ACM/ICPC 竞赛之 STL--ALGORITHM ............................. 40

STL IN ACM ..................................................................... 41

头文件 ............................................................................... 42

线段树 ........................................... 43

求矩形并的面积（线段树+离散化+扫描线） ............... 43

求矩形并的周长（线段树+离散化+扫描线） ............... 44

Graph 图论

/*==================================================*\

| DAG 的深度优先搜索标记

| INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;

| CALL: dfstag(i, n); pre/post:开始/结束时间

\*==================================================*/

int edge[V][V], pre[V], post[V], tag;

void dfstag(int cur, int n)

{ // vertex: 0 ~ n-1

pre[cur] = ++tag;

for (int i=0; i<n; ++i) if (edge[cur][i]) {

if (0 == pre[i]) {

printf("Tree Edge!\n");

dfstag(i, n);

} else {

if (0 == post[i]) printf("Back Edge!\n");

else if (pre[i] > pre[cur])

printf("Down Edge!\n");

else printf("Cross Edge!\n");

}

post[cur] = ++tag;

}

/*==================================================*\

| 无向图找桥

| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;

| CALL: dfs(0, -1, 1, n);

\*==================================================*/

int bridge, edge[V][V], anc[V], pre[V], vis[V];

void dfs(int cur, int father, int dep, int n)

{ // vertex: 0 ~ n-1

if (bridge) return;

vis[cur] = 1; pre[cur] = anc[cur] = dep;

for (

int i=0; i<n; ++i) if (edge[cur][i]) {

if (i != father && 1 == vis[i]) {

if (pre[i] < anc[cur])

anc[cur] = pre[i];//back edge

}

if (0 == vis[i]) { //tree edge

dfs(i, cur, dep+1, n);

if (bridge) return;

if (anc[i] < anc[cur]) anc[cur] = anc[i];

if (anc[i] > pre[cur]) { bridge = 1; return; }

}

vis[cur] = 2;

}

/*==================================================*\

| 无向图连通度(割)

| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0;

| CALL: dfs(0, -1, 1, n);

| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数

| 注意:0作为根比较特殊!

\*==================================================*/

int edge[V][V], anc[V], pre[V], vis[V], deg[V];

void dfs(int cur, int father, int dep, int n)

{// vertex: 0 ~ n-1

int cnt = 0;

vis[cur] = 1; pre[cur] = anc[cur] = dep;

for (int i=0; i<n; ++i) if (edge[cur][i]) {

if (i != father && 1 == vis[i]) {

if (pre[i] < anc[cur])

anc[cur] = pre[i];//back edge

}

if (0 == vis[i]) { //tree edge

dfs(i, cur, dep+1, n);

++cnt; // 分支个数

if (anc[i] < anc[cur]) anc[cur] = anc[i];

if ((cur==0 && cnt>1) ||

(cnt!=0 && anc[i]>=pre[cur]))

++deg[cur]; // link degree of a vertex

}

vis[cur] = 2;

}

/*==================================================*\

| 最大团问题 DP + DFS

| INIT: g[][]邻接矩阵;

| CALL: res = clique(n);

\*==================================================*/

int g[V][V], dp[V], stk[V][V], mx;

int dfs(int n, int ns, int dep){

if (0 == ns) {

if (dep > mx) mx = dep;

return 1;

}

int i, j, k, p, cnt;

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

k = stk[dep][i]; cnt = 0;

if (dep + n - k <= mx) return 0;

if (dep + dp[k] <= mx) return 0;

for (j = i + 1; j < ns; j++) {

p = stk[dep][j];

if (g[k][p]) stk[dep + 1][cnt++] = p;

}

dfs(n, cnt, dep + 1);

}

return 1;

}

int clique(int n){

int i, j, ns;

for (mx = 0, i = n - 1; i >= 0; i--) {

// vertex: 0 ~ n-1

for (ns = 0, j = i + 1; j < n; j++)

if (g[i][j]) stk[1][ ns++ ] = j;

dfs(n, ns, 1); dp[i] = mx;

}

return mx;

}

/*==================================================*\

| 欧拉路径 O(E)

| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;

| CALL: elpath(0); 注意:

不要有自向边

\*==================================================*/

int adj[V][V], idx[V][V], cnt[V], stk[V], top;

int path(int v){

for (int w ; cnt[v] > 0; v = w) {

stk[ top++ ] = v;

w = adj[v][ --cnt[v] ];

adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];

// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v

}

return v;

}

void elpath (int b, int n){ // begin from b

int i, j;

for (i = 0; i < n; ++i) // vertex: 0 ~ n-1

for (j = 0; j < cnt[i]; ++j)

idx[i][ adj[i][j] ] = j;

printf("%d", b);

for (top = 0; path(b) == b && top != 0; ) {

b = stk[ --top ];

printf("-%d", b);

}

printf("\n");

}

/*==================================================*\

| Dijkstra 数组实现 O（N^2）

| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)

| lowcost[] --- beg到其他点的最近距离

| path[] -- beg为根展开的树，记录父亲结点

\*==================================================*/

#define INF 0x03F3F3F3F

const int N;

int path[N], vis[N];

void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){

int i, j, min;

memset(vis, 0, sizeof(vis));

vis[beg] = 1;

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

lowcost[i] = cost[beg][i]; path[i] = beg;

}

lowcost[beg] = 0;

path[beg] = -1; // 树根的标记

int pre = beg;

for (i=1; i<n; i++){

min = INF;

剩余45页未读，继续阅读

zdp000111

2012-07-17

中文版的，讲解清晰，代码很全，不错

yingxiangtju

粉丝: 0
资源: 3

会员权益专享

ACM/ICPC常用算法的代码库（吉林大学版，强烈推荐）

评论4

会员权益专享

最新资源

ACM/ICPC常用算法的代码库（吉林大学版，强烈推荐）

评论4

Algorithm:ACMICPC、TopCoder等算法代码

ACM/ICPC 代码库

常用算法代码

ACM/ICPC词汇

描述 将字母的大小写转换一下，非字母字符原样输出。 格式 输入格式 输出格式 样例1 样例输入1 I like ACM/ICPC. Hello World! +-*/ are operators. 样例输出1 i LIKE acm/icpc. hELLO wORLD! +-*/ ARE OPERATORS. 代码写一下

ACM-ICPC模板整理

https://ac.nowcoder.com/acm/contest/67743/L

acm-icpc国际大学生程序设计竞赛 知识与入门

c语言 参加ACM/ICPC比赛时，每支队伍有题目AC就会得到一只气球，题号与对应的气球颜色如下表所示。 编写程序，输入一支队伍所得到的所有气球颜色，请输出他们AC的题号。

LM78L05ACM/TR

acm经典c语言算法代码

https://ac.nowcoder.com/acm/contest/61657/L

acm常用java算法,

acm竞赛常用算法与数据结构

关于Python的竞赛

bjfouj数据结构

2023山东省赛icpc

怎么刷算法备战蓝桥杯

数据结构及基础算法试题

https://ac.nowcoder.com/acm/contest/70759/A

会员权益专享

最新资源

描述将字母的大小写转换一下，非字母字符原样输出。格式输入格式输出格式样例1 样例输入1 I like ACM/ICPC. Hello World! +-/ are operators. 样例输出1 i LIKE acm/icpc. hELLO wORLD! +-/ ARE OPERATORS. 代码写一下

acm-icpc国际大学生程序设计竞赛知识与入门

c语言参加ACM/ICPC比赛时，每支队伍有题目AC就会得到一只气球，题号与对应的气球颜色如下表所示。编写程序，输入一支队伍所得到的所有气球颜色，请输出他们AC的题号。