Alex's Anthology of Algorithms: Common Code for Contests in Concise C++ (A<sup>3</sup>C<sup>5</sup>)
==================
[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.<br>
— 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.
没有合适的资源?快使用搜索试试~ 我知道了~
Alex的算法选集:简明C++竞赛通用代码(A³C⁵)-正在进行中!_C++_TeX_下载.zip
共155个文件
cpp:142个
tex:7个
py:1个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 136 浏览量
2023-04-30
10:27:26
上传
评论
收藏 1.66MB ZIP 举报
温馨提示
Alex的算法选集:简明C++竞赛通用代码(A³C⁵)-正在进行中!_C++_TeX_下载.zip
资源推荐
资源详情
资源评论
收起资源包目录
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 条
- 1
- 2
资源评论
快撑死的鱼
- 粉丝: 1w+
- 资源: 9154
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功