上海交大ACM模板（文件有问题请注意下载似乎foxitreader1.3可以打开，版本高的阅读器反而打不开）资源-CSDN文库

4星 · 超过85%的资源需积分: 9 158 浏览量 2007-11-19 10:43:25 上传评论 2 收藏 389KB PDF 举报

### 上海交通大学ACM模板概览 #### 一、引言上海交通大学（简称“上海交大”）作为中国顶尖的高等学府之一，在计算机科学与技术领域有着深厚的学术积累和丰富的教学资源。ACM（Association for Computing Machinery，计算机协会）是世界上历史最悠久、规模最大的计算机教育和科研组织，其竞赛（ACM Programming Contest）是全球最具影响力的大学生程序设计竞赛之一。本文将基于上海交通大学提供的ACM模板进行深入解析，旨在帮助读者更好地理解和掌握ACM竞赛中的核心算法和技术。 #### 二、模板结构与主要内容 ##### 1. Algorithms and Data Structures (算法与数据结构) 该部分涵盖了大量基础和高级的算法与数据结构，是ACM竞赛中最为核心的部分。 - **1.1 High Precision in C** (C语言中的高精度计算): 介绍了如何在C语言中实现高精度的整数运算，这对于解决涉及大数的问题非常重要。 - **1.2 High Precision in C++** (C++中的高精度计算): 相较于C语言，C++提供了更多的库支持和便捷性，这里讲解了如何利用C++来处理高精度问题。 - **1.3 High Precision Floating-point Number** (高精度浮点数): 针对更复杂的数学问题，如高精度的小数运算等进行了详细介绍。 - **1.4 Fraction Class** (分数类): 提供了一个分数类的实现，用于精确表示分数和进行分数运算。 - **1.5 Binary Heap** (二叉堆): 一种常用的数据结构，用于实现优先队列等功能。 - **1.6 Winner Tree** (胜利树): 一种特殊的二叉树，常用于解决区间查询问题。 - **1.7 Digital Tree** (数字树): 又称Trie树，是一种高效的字符串存储结构。 - **1.8 Segment Tree** (线段树): 用于解决区间查询和更新问题的有效工具。 - **1.9 Segment Tree in IOI’2001** (IOI’2001中的线段树): 特别提及了一个实际案例中的线段树应用。 - **1.10 Union-Find Set** (并查集): 一种处理不相交集合合并操作的数据结构。 - **1.11 QuickSort** (快速排序): 一种高效的排序算法。 - **1.12 MergeSort** (归并排序): 另一种稳定的排序方法。 - **1.13 Radix Sort** (基数排序): 适用于整数排序的非比较型算法。 - **1.14 Select Kth Smallest Element** (选择第K小的元素): 实现了寻找数组中第K小元素的高效算法。 - **1.15 KMP** (Knuth-Morris-Pratt算法): 一种高效的字符串匹配算法。 - **1.16 Suffix Sort** (后缀排序): 对字符串的所有后缀进行排序的方法，常用于构建后缀数组。 ##### 2. Graph Theory and Network Algorithms (图论与网络算法) 这部分聚焦于图论及其在网络中的应用。 - **2.1 SSSP—Dijkstra + Binary Heap** (单源最短路径—Dijkstra算法+二叉堆): 结合了Dijkstra算法和二叉堆优化的单源最短路径算法。 - **2.2 SSSP—Bellman Ford + Queue** (单源最短路径—Bellman-Ford算法+队列): 解决负权边情况下的单源最短路径问题。 - **2.3 MST—Kruskal** (最小生成树—Kruskal算法): 构建图的最小生成树的一种方法。 - **2.4 Minimum Directed Spanning Tree** (有向图的最小生成树): 在有向图中构建最小生成树。 - **2.5 Maximum Matching on Bipartite Graph** (二分图的最大匹配): 在二分图中寻找最大匹配。 - **2.6 Maximum Cost Perfect Matching on Bipartite Graph** (二分图的最大费用完美匹配): 找到具有最大成本的完美匹配。 - **2.7 Maximum Matching on General Graph** (一般图的最大匹配): 处理一般图的最大匹配问题。 - **2.8 Maximum Flow—Ford Fulkson in Matrix** (最大流—矩阵形式的Ford-Fulkson算法): 解决最大流问题的一种经典方法。 - **2.9 Maximum Flow—Ford Fulkson in Link** (最大流—链式形式的Ford-Fulkson算法): 另一种实现最大流的算法。 - **2.10 Minimum Cost Maximum Flow in Matrix** (最小费用最大流—矩阵形式): 最小费用最大流问题的解决方案。 - **2.11 Minimum Cost Maximum Flow in Link** (最小费用最大流—链式形式): 最小费用最大流的另一种实现方式。 - **2.12 Recognizing Chordal Graph** (识别圈图): 圈图的识别方法。 - **2.13 DFS—Bridge** (深度优先搜索—桥): 利用深度优先搜索寻找图中的桥。 - **2.14 DFS—Cutvertex** (深度优先搜索—割点): 寻找图中的割点。 - **2.15 DFS—Block** (深度优先搜索—块): 块的定义以及寻找方法。 - **2.16 DFS—Topological Sort** (深度优先搜索—拓扑排序): 拓扑排序的实现。 - **2.17 Strongly Connected Component** (强连通分量): 图的强连通分量分析。以上仅是上海交通大学ACM模板的一部分内容介绍，该模板还包括了数论、代数算法、计算几何等多个方面的知识，是学习和准备ACM竞赛不可或缺的宝贵资源。通过这些详细的讲解和示例代码，参赛者不仅能够加深对各种算法的理解，还能够在实战中灵活运用，提高解题能力。

资源推荐

资源详情

资源评论

Standard Code Library

Hao Yuan

Department of Computer Science and Engineering

Shanghai Jiaotong University

October 23, 2003

Contents

1 Algorithms and Datastructures 3

1.1 High Precision in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 High Precision in C Plus Plus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 High Precision Floating-p oint Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Fraction Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Binary Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.6 Winner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.7 Digital Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.8 Segment Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.9 Segment Tree in IOI’2001 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.10 Union-Find Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.11 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.12 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.13 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.14 Select K

Smallest Element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.15 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.16 Suﬃx Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Graph Theory and Network Algorithms 14

2.1 SSSP — Dijkstra + Binary Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2 SSSP — Bellman Ford + Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 MST — Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Minimum Directed Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Maximum Matching on Bipartite Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.6 Maximum Cost Perfect Matching on Bipartite Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7 Maximum Matching on General Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.8 Maximum Flow — Ford Fulkson in Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.9 Maximum Flow — Ford Fulkson in Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.10 Minimum Cost Maximum Flow in Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.11 Minimum Cost Maximum Flow in Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.12 Recognizing Chordal Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.13 DFS — Bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.14 DFS — Cutvertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.15 DFS — Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.16 DFS — Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.17 Strongly Connected Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Number Theory 25

3.1 Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Prime Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4 φ Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 Discrete Logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.6 Square Roots in Z

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Algebraic Algorithms 29

4.1 Linear Equations in Z

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Linear Equations in Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3 Linear Equations in Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 Linear Equations in R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.5 Roots of Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.6 Roots of Cubic and Quartic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.7 Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.8 FFT - Polynomial Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.9 FFT - Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.10 FFT - Reverse Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.11 Linear Programming - Primal Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Computational Geometry 38

5.1 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.2 Extended Op erations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.3 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.4 Point Set Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.5 Closest Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.6 Circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.7 Largest Empty Convex Polygon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.8 Triangle Centers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.9 Polyhedron Volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.10 Planar Graph Contour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.11 Rectangles Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.12 Rectangles Perimeter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.13 Smallest Enclosing Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.14 Smallest Enclosing Ball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 Classic Problems 57

6.1 Bernoulli Number Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2 Baltic OI’99 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3 Bead Coloring — P´olya Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.4 Binary Stirling Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.5 Box Surface Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.6 Calculate Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.7 Cartesian Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.8 Catalan Number Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.9 Coloring Regular Polygon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.10 Counting Inverse Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.11 Counting Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.12 Eight Puzzle Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.13 Extended Honai Tower . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.14 High Precision Square Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.15 Largest Empty Rectangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.16 Last Non-Zero Digit of N! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.17 Least Common Ancestor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.18 Longest Common Substring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.19 Longest Non Descending Sub Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.20 Join and Disjoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.21 Magic Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.22 Optimal Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.23 Pack Rectangles — Cut Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.24 Pack Rectangles — O(N

) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.25 Parliament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.26 π Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.27 Plant Trees — Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.28 Plant Trees — Segment Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.29 Range Maximum Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.30 Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.31 Tree Heights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.32 Minimum Cyclic Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.33 Maximum Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.34 Maximal Non-Forbidden Submatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.35 Maximum Two Chain Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.36 N Queens Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.37 de Bruijn Sequence Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.38 ZOJ 1482 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

剩余86页未读，继续阅读

评论收藏

内容反馈

quant67

2013-06-07

真的打不开呀。foxit1.3
唐门问心

2012-04-15

的确只能用foxit 1.3才能打开
缥渺孤鸿

2012-03-18

的确只能用foxit 1.3才能打开内容不错
helloid123

2011-11-02

谢谢提醒，的确只能用foxit 1.3才能打开
ddegg1992

2012-07-16

打不开呢。。

wjbzyy

粉丝: 0
资源: 3

上海交大ACM模板（文件有问题请注意下载似乎foxit reader1.3可以打开，版本高的阅读器反而打不开）

最新资源

上海交大ACM模板 （文件有问题 请注意下载 似乎foxit reader1.3可以打开，版本高的阅读器反而打不开）

foxit reader pdf阅读工具

上海交大ACM模板_上海交大ACM模板_ACM模板_

上海交大ACM模板

上海交大ACM模板.zip

上海交大ACM模板.zip_上海交大ACM模板_上海大学

上海交通大学ACM算法模板

ACM模板（上海交大、浙大、吉林大学、邝斌）

上海交大的acm试题

上海交通大学ACM模板

算法参考资料上海交大ACM模板英文

acm模板_acm模板

上海交大ACM final选手模板

ACM 会议模板LETEX

上海交大ACM资料

上海交大ACM-ICPC模板

ACM常用模板 ACM常用模板

ACM模板(浙大)_算法竞赛_ACM模板_ACM_源码

ACM模板大全【必备】

上海交通大学acm模板(已修复的)

ACM程序设计大赛算法模板 ACM模板 一般编程问题

浙江大学ACM模板

完整版kuangbin的ACM模板（新）.pdf

中山大学ACM模板

吉林大学ACM模板

最好最全的ACM模板

浙大上交吉大上大acm模板.zip

邝斌ACM模板2015最新版下载

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

最新资源

上海交大ACM模板（文件有问题请注意下载似乎foxit reader1.3可以打开，版本高的阅读器反而打不开）

ACM程序设计大赛算法模板 ACM模板一般编程问题

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar