-
Nie ma jednej implementacji algorytmu zaspokojającej wszystkie przypadki użycia, więc algorytmy powinny być proste do skopiowania, wklejenia do własnego kodu i zmodyfikowania w ważnych punktach ich działania.
-
Wszystkie algorytmy w tej bibliotece powinny być możliwie niezależnymi od siebie kawałkami kodu, wymagać jak najmniej kodu do samodzielnego funkcjonowania i mieć jak najprostszy interfejs.
-
Kod ma być czytelny, krótki, bez mikrooptymalizacji.
-
Asserty powinny sprawdzać warunki dotyczące wejścia, które nie mogą być wykryte na inne sposoby (np. przez sygnał naruszenia ochrony pamięci lub tryb debugowania w glibc++).
- matematyka
- NWD, NWW
- mnożenie i potęgowanie modularne
- rozszerzony algorytm Euklidesa
- odwrotność modularna
- liniowe równania diofantyczne
- chińskie twierdzenie o resztach
- logarytm dyskretny
- sito liczb pierwszych - Eratostenes, Euler
- test pierwszości - z sita, Miller-Rabin
- rozkład na czynniki pierwsze - z sita, rho Pollarda
- funkcja φ Eulera
- liczba, suma i iloczyn dzielników
- silnia - spamiętywana, zwyklejsza
- symbol Newtona
- liczba podziałów elementów do kilku zbiorów
- FFT
- modularny int
- NTT
- pierwiastek pierwotny
- podsilnia
- lemat Burnside'a
- liczby Catalana
- FWHT o podstawie 3
- rozszerzony binarny algorytm Euklidesa
- eliminacja Gaussa - rzeczywista, modularna, bitowa
- grafy
- skojarzenie w grafie dwudzielnym - Hopcroft-Karp
- przeszukiwanie grafu - BFS, DFS (w tym funkcja low)
- sortowanie topologiczne - Kahn, z DFS
- silnie spójne składowe - Kosaraju
- dwukolorowanie grafu
- mosty, punkty artykulacji i dwuspójne składowe
- generator grafów losowych
- minimalne drzewo rozpinające - Kruskal, Prim
- najkrótsze ścieżki
- dla DAGów, Dijkstra, Dial, Bellman-Ford, SPFA, Floyd-Warshall
- A*, Johnson
- binary lifting
- najniższy wspólny przodek - z binary liftingu, z RMQ
- heavy-light decomposition
- centroid decomposition
- 2-SAT
- graf funkcyjny
- problem skoczka szachowego - Warnsdorff i Pohl
- maksymalny przepływ - Edmonds-Karp
- ścieżka Eulera (lub cykl)
- liczba ścieżek i najdłuższa ścieżka w DAGu
- znajdywanie cykli
- najbardziej oddalony wierzchołek i średnica w drzewie
- offline dynamic connectivity
- przepływ minimalnego kosztu - Ford-Fulkerson i SPFA
- chain decomposition
- skojarzenie w ogólnym grafie
- problem komiwojażera - z DP, z branch-and-bound
- algorytm Rémy'ego
- struktury danych
- drzewo przedziałowe
- przedział-przedział, przedział-przedział bez propagacji, przedział-przedział 2D, punkt-przedział, punkt-przedział 2D, przedział-punkt, przedział-punkt 2D
- leniwe przedział-przedział
- struktura zbiorów rozłącznych - las zbiorów rozłącznych, z trzymaniem elementów, z cofaniem
- sparse table
- stos i kolejka minimum/monotoniczna
- sumy prefiksowe - 1D, 2D
- drzewo Fenwicka - punkt-przedział, punkt-przedział 2D, przedział-punkt, przedział-punkt 2D, przedział-przedział, przedział-przedział 2D
- skompresowane drzewo trie
- GNU C++ PBDS
- implicit treap
- drzewo Li Chao
- sumy pierwiastkowe
- big int
- ułamek
- treap
- wielomian
- dynamiczne drzewo AABB
- fibonacci heap
- disjoint sparse table
- sparse table 2D
- macierz i wektor
- drzewo przedziałowe
- tekstówki
- najdłuższy wspólny podciąg - z DP, z dziel i zwyciężaj
- haszowanie w okienku
- hasze prefiksowe
- wyszukiwanie wzorca w tekście - Rabin-Karp, KMP
- tablica sufiksowa - w O(n log n), z haszy
- funkcja prefiksowa
- najmniejsze przesunięcie cykliczne - Booth
- algorytm Manachera
- algorytm Aho-Corasick
- tablica LCP - Kasai
- funkcja Z
- KMR
- geometria
- convex hull trick
- figury geometryczne - punkt, odcinek, wielokąt, koło
- twierdzenie Picka
- najbliższa para punktów - z zamiatania, z dziel i zwyciężaj
- otoczka wypukła - Graham
- triangulacja wielokątów
- przecięcie i różnica prostokątów
- euklidesowe minimalne drzewo spinające
- inne
- najdłuższy rosnący podciąg
- algorytm Mo
- meet in the middle
- Quickselect
- algorytm magicznych piątek
- Lazyselect
- or/subset convolution
- algorytm sympleksowy
- reszta algorytmów
- templatka do rozwiązań
- pragmy
- testerka w kodzie
- szybkie I/O
- rozmiar stosu
- "Kajaki" z IV OI
- "Małpki" z Solve