Alex的算法选集：简明C++竞赛通用代码(A³C⁵)-正在进行中！_C++_TeX

共155个文件

cpp：142个

tex：7个

py：1个

版权申诉

132 浏览量 2023-04-30 10:27:26 上传评论收藏 1.66MB ZIP 举报

《Alex的算法选集：简明C++竞赛通用代码(A³C⁵)-正在进行中！》是一份专门针对编程竞赛的资源，旨在帮助参赛者掌握C++编程语言，并熟悉常用的算法和数据结构。这个压缩包名为"algorithm-anthology-master"，暗示其内容可能是一个包含各种算法实现和相关教程的项目。 1. **C++基础与进阶**： - **基础语法**：C++是一种静态类型、编译式、通用的、大小写敏感的、不仅支持过程化编程，也支持面向对象编程的程序设计语言。学习C++需要了解变量、常量、运算符、流程控制语句（如if-else，switch-case，for，while）等基本元素。 - **面向对象编程**：C++支持类、对象、封装、继承、多态等面向对象特性，这对于理解和编写复杂算法至关重要。 2. **算法概论**： - **排序算法**：包括快速排序、归并排序、堆排序、冒泡排序、插入排序等，它们在解决数据处理问题时起到关键作用。 - **搜索算法**：如二分查找、深度优先搜索（DFS）、广度优先搜索（BFS）等，这些算法在数据检索和图论问题中常见。 - **动态规划**：用于解决具有重叠子问题和最优子结构的问题，例如斐波那契数列、背包问题等。 - **贪心算法**：通常用于解决局部最优解能导致全局最优解的问题，如最小生成树、活动选择问题等。 - **回溯法**：用于在解决问题时尝试所有可能的解决方案，如八皇后问题、数独等。 3. **数据结构**： - **数组**：基础数据结构，便于直接访问任何位置的元素。 - **链表**：非连续存储的数据结构，适用于频繁插入和删除操作。 - **栈**：后进先出（LIFO）的数据结构，常用于函数调用和表达式求值。 - **队列**：先进先出（FIFO）的数据结构，用于任务调度和缓冲区管理。 - **哈希表**：提供快速的查找、插入和删除操作，通过散列函数实现。 - **树**：包括二叉树、平衡树（如AVL树、红黑树）等，用于数据索引和搜索。 - **图**：用于表示网络结构，支持邻接矩阵和邻接表等多种表示方式。 4. **编程竞赛实践**： - **ACM/ICPC训练**：这些代码可能包含历年的竞赛题目和解决方案，有助于参赛者模拟比赛环境。 - **在线判题系统**：如LeetCode、Codeforces、HackerRank等，提供自动测试和评估代码的功能。 - **时间复杂度和空间复杂度分析**：优化算法性能的关键，确保在限制时间内解决问题。 5. **TeX排版**： - TeX是一种用于数学和科技文档排版的系统，压缩包中的TeX文件可能是算法的数学描述或公式，有助于清晰地呈现复杂的算法逻辑。 6. **版本控制**： - "master"分支通常指的是Git仓库的主要分支，意味着这些代码可能是通过Git进行版本控制的，方便团队协作和代码维护。这个压缩包对于参与编程竞赛的初学者和进阶者来说都是一份宝贵的资源，涵盖了C++编程语言的基础知识，算法理论，数据结构的实现，以及如何利用TeX进行高质量文档的编写。通过深入学习和实践，可以提升编程能力，提高解决实际问题的效率。

资源推荐

资源详情

资源评论

收起资源包目录

Alex的算法选集：简明C++竞赛通用代码(A³C⁵)-正在进行中！_C++_TeX_下载.zip （155个子文件）

6.0_Geometry_Library_in_One_File.cpp 36KB

5.4.2_Big_Integers.cpp 20KB

6.4.4_Delaunay_Triangulation_(Fast).cpp 16KB

5.6.5_Polynomial_Root_Finding_(RPOLY).cpp 14KB

5.1_Math_Utilities.cpp 12KB

5.5.1_Matrix_Utilities.cpp 12KB

1.1.1_Sorting_Algorithms.cpp 11KB

2.6.6_Link-Cut_Tree.cpp 10KB

3.3.3_Shunting_Yard_Parsing.cpp 9KB

2.6.5_Heavy_Light_Decomposition.cpp 9KB

3.3.2_Recursive_Descent_Parsing_(Generic).cpp 9KB

2.2.4_Red-Black_Tree.cpp 9KB

2.4.3_2D_Segment_Tree.cpp 8KB

2.4.2_Quadtree_(Range_Update).cpp 8KB

2.3.6_Implicit_Treap.cpp 8KB

6.2.3_Line_Intersection.cpp 8KB

3.1_String_Utilities.cpp 7KB

5.3.4_Integer_Factorization.cpp 7KB

3.6.2_Radix_Tree.cpp 7KB

5.5.4_LU_Decomposition.cpp 7KB

6.2.4_Circle_Intersection.cpp 7KB

5.2.4_Enumerating_Combinations.cpp 7KB

2.2.7_Interval_Treap.cpp 7KB

6.4.2_Polygon_Intersection_and_Union.cpp 7KB

2.2.6_Size_Balanced_Tree.cpp 7KB

5.2.3_Enumerating_Permutations.cpp 6KB

2.3.5_Segment_Tree_(Compressed).cpp 6KB

2.3.4_Segment_Tree_(Range_Update).cpp 6KB

5.2.1_Combinatorial_Calculations.cpp 6KB

5.4.3_Rational_Numbers.cpp 6KB

3.5.3_Suffix_Array_and_LCP_(Linear_DC3).cpp 6KB

5.4.1_Big_Integers_(Simple).cpp 6KB

6.1.1_Point.cpp 6KB

2.2.3_AVL_Tree.cpp 6KB

6.4.3_Delaunay_Triangulation_(Simple).cpp 6KB

5.2.6_Enumerating_Generic_Combinatorial_Sequences.cpp 6KB

2.4.1_Quadtree_(Point_Update).cpp 6KB

6.3.6_Segment_Intersection_Finding.cpp 6KB

3.4.3_Sequence_Alignment.cpp 5KB

2.2.8_Hash_Map.cpp 5KB

2.2.9_Skip_List.cpp 5KB

2.2.5_Splay_Tree.cpp 5KB

3.6.1_Trie.cpp 5KB

3.2.3_String_Searching_(Aho-Corasick).cpp 5KB

6.1.5_Rectangle.cpp 5KB

1.2.2_Maximal_Subarray_Sum_(Kadane).cpp 5KB

5.3.1_GCD,_LCM,_Mod_Inverse,_Chinese_Remainder.cpp 5KB

6.2.2_Distances.cpp 5KB

6.1.3_Circle.cpp 5KB

4.3.3_Bridges,_Cut-points,_and_Biconnectivity.cpp 5KB

2.2.2_Treap.cpp 5KB

2.4.7_R-Tree_(Nearest_Segment).cpp 5KB

5.6.4_Polynomial_Root_Finding_(Laguerre).cpp 5KB

5.2.2_Enumerating_Arrangements.cpp 5KB

5.2.5_Enumerating_Partitions.cpp 4KB

2.3.3_Segment_Tree_(Point_Update).cpp 4KB

6.3.1_Polygon_Sorting_and_Area.cpp 4KB

1.3.1_Binary_Search.cpp 4KB

2.2.1_Binary_Search_Tree.cpp 4KB

3.5.2_Suffix_Array_and_LCP_(Counting_Sort).cpp 4KB

6.2.1_Angles.cpp 4KB

6.1.2_Line.cpp 4KB

6.3.3_Convex_Hull_and_Diametral_Pair.cpp 4KB

4.1.1_Graph_Class_and_Depth-First_Search.cpp 4KB

2.4.5_K-d_Tree_(2D_Range_Query).cpp 4KB

3.5.1_Suffix_Array_and_LCP_(Manber-Myers).cpp 4KB

5.5.3_Determinant_and_Inverse.cpp 4KB

5.5.5_Linear_Programming_(Simplex).cpp 4KB

2.4.4_2D_Range_Tree.cpp 4KB

1.3.5_Convex_Hull_Trick_(Fully-Dynamic).cpp 4KB

2.6.2_Disjoint_Set_Forest_(Compressed).cpp 4KB

5.3.3_Primality_Testing.cpp 4KB

6.1.4_Triangle.cpp 4KB

4.1.3_Eulerian_Cycles_(DFS).cpp 4KB

2.3.2_Square_Root_Decomposition.cpp 4KB

2.5.7_2D_Fenwick_Tree_(Compressed).cpp 4KB

3.4.2_Longest_Common_Subsequence.cpp 4KB

5.6.3_Polynomial_Root_Finding_(Differentiation).cpp 4KB

1.1.2_Array_Rotation.cpp 4KB

2.4.6_K-d_Tree_(Nearest_Neighbor).cpp 3KB

2.1.4_Pairing_Heap.cpp 3KB

4.7.1_Maximum_Clique_(Bron-Kerbosch).cpp 3KB

6.4.1_Convex_Polygon_Cut.cpp 3KB

4.6.3_Maximum_Graph_Matching_(Edmonds).cpp 3KB

5.5.2_Row_Reduction.cpp 3KB

4.2.2_Shortest_Path_(Dijkstra).cpp 3KB

4.1.4_Unweighted_Tree_Centers_(DFS).cpp 3KB

2.1.2_Randomized_Mergeable_Heap.cpp 3KB

2.1.3_Skew_Heap.cpp 3KB

1.1.3_Counting_Inversions.cpp 3KB

6.3.4_Minimum_Enclosing_Circle.cpp 3KB

2.6.4_Lowest_Common_Ancestor_(Segment_Tree).cpp 3KB

4.4.1_Minimum_Spanning_Tree_(Prim).cpp 3KB

6.3.5_Closest_Pair.cpp 3KB

2.1.1_Binary_Heap.cpp 3KB

4.7.2_Graph_Coloring.cpp 3KB

4.5.4_Maximum_Flow_(Push-Relabel).cpp 3KB

1.4.2_Cycle_Detection_(Brent).cpp 3KB

4.7.3_Shortest_Hamiltonian_Cycle_(TSP).cpp 3KB

2.5.5_Fenwick_Tree_(Compressed).cpp 3KB

共 155 条

Alex's Anthology of Algorithms: Common Code for Contests in Concise C++ (A3C5) ================== [PDF Download](https://github.com/alxli/algorithm-anthology/raw/master/Book/a3c5.pdf). Please beware of any older versions in circulation, as they are very buggy. ## Introduction Welcome to a comprehensive collection of common algorithms and data structures. The ultimate goal of this book is not to explain concepts from the ground up, but instead to explore the finer details behind their *implementations*. There are many potential ways you can use this, for instance: * as a reference to help you better understand topics that you have only studied on a high level, * as a printed codebook, which is a permitted resource for contests such as the ACM ICPC, or * to cross-check existing code you have written for contest or coding interview questions. Before diving into any section, it is strongly recommended that you have already studied the algorithms involved. Reading the code first is never an ideal approach to properly understand an algorithm. You should instead try proving (its correctness and time/space complexity) and implementing it from scratch. Every topic to be explored is easily researchable online. Thus instead of including theoretical discussions, I document just enough to establish the problem being solved, notation being used, and any special trickery involved. I have also included small, non-rigorous examples to demonstrate usage of the code. We mentioned that the implementation itself is the focus, but what makes an implementation good? The code is written with the following principles in mind: * *Clarity:* A reader already familiar with an algorithm should have no problem understanding how its implementation works. Consistency in naming conventions should be emphasized, and any tricks or language-specific hacks should be documented. * *Concision:* To minimize the amount of scrolling and searching during the frenzy of time contests, it is helpful for code to be compact. Shorter code is also generally easier to understand, as long as it is not overly cryptic. Finally, each implementation should fit in a single source file as required by nearly all online judging systems. * *Efficiency:* The code here is designed to be performant on real contests, and should maintain a low constant overhead. This is often challenging in the face of clarity and tweakability, but we can hope for contest setters to be liberal with time and memory limits. If the code here times out, you can reasonably rule out insufficient constant optimization and assume that you are choosing an algorithm from a suboptimal complexity class. * *Genericness:* Implementations should be easy to adapt to achieve slightly different goals. One may want to tweak some core logic, parameters, data types, etc. In timed contests, we would certainly prefer this process to be as painless as possible. C++ templates are often used to increase tweakability at a slight cost to simplicity. * *Portability:* Different contest environments use different compiler builds. In order to maximize compatibility, non-standard and newer features are avoided. The decision to follow C++98 standards is due to many contest systems being stuck on an older version of the language. Moreover, minimizing newer C++ features will make the code more language-agnostic. As these points and the title both suggest, there is a slight bias towards contests. Compiling a codebook for my personal reference during contests was indeed how this project got started. This work has become much more multipurpose now. Whatever your use case is, I hope you discover something enlightening. Cheers. — Alex ## Portability Note All programs were tested with GCC and compiled for a 32-bit target using the switches below:: ``` g++ -std=gnu++98 -pedantic -Wall -Wno-long-long -O2 ``` This means the following are assumed about data types: * `bool` and `char` are 8-bit. * `int` and `float` are 32-bit. * `double` and `long long` are 64-bit. * `long double` is 96-bit. Programs are highly portable (ISO C++ 1998 compliant), except in the following regards: * Usage of `long long` and dependent features, which are compliant in C99/C++0x or later. 64-bit integers are a must for many contest problems. * Usage of variable sized arrays. While easily replaced by vectors, they are generally simpler and avoid dynamic memory (which some argue is a bad idea for contests). * Usage of GCC's built-in functions like `__builtin_popcount()` and `__builtin_clz()`. These can be extremely convenient, but are straightforward to implement if unavailable. See here for a reference: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html * Usage of compound-literals, e.g. `myvector.push_back((mystruct){a, b, c})`. This adds a little more concision by not requiring a constructor definition. * Hacks that may depend on the platform (e.g. endianness), such as getting the signbit with type-punned pointers. Be weary of portability for all bitwise/lower level code.

评论收藏

内容反馈

版权申诉