Competitive Programming Repository

Wettbewerbsbekämpfungsprogrammierende Repository

Sammlung von Algorithmen und Datenstrukturen in C ++, die bei wettbewerbsfähigen Programmierwettbewerben weit verbreitet sind.

Die folgenden Themen sind abgedeckt:

Bereichsaktualisierungen und Abfragen

• Reichweite aggregierte Abfragen :
  • Binär indizierte Bäume (Bit) :
    • Punkt -Update -Bereichsabfrage
    • Bereichs -Update -Bereichsabfrage
    • Statistische Abfrage bestellen
    • 2d binäre indizierte Bäume
  • Segmentbäume (Segtree) :
    • Punkt -Update -Bereichsabfrage
    • Schneller iterativer Segtrees
    • Bereichs -Update -Punkt -Abfrage - Lazy Propogation
    • Max -Subsegmentsumme im Bereich
    • 2D -Segmentbäume
    • Dynamische Segmentbäume - Insertion/Löschung zwischen Elementen
    • Dynamische Segmentbäume - Umgekehrt ein Segment umgeben
  • Sortierbäume zusammenführen :
    • Sortierbäume zusammenführen
    • Sortierbäume zusammenführen - Statistik bestellen
  • Spärmer Tisch :
    • Bereich Mindestanfrage
  • Mo -Algorithmus :
    • Mo -Algorithmus - Arrays
• Dynamische Programmierung :
  • Dynamische Programmiervorlagen :
    • Digit DP / Bitwise DP
  • Standard -DP -Probleme :
    • Die längste zunehmende Subsequenz
    • Längste palindrome Subsequenz
    • Levenstein -Entfernung / Bearbeitungsentfernung
• Grafiken :
  • Einzelquelle Kürzeste Pfadalgorithmen :
    • Dijkstra in dichten Graphen
    • Dijkstra mit Prioritätswarteschlange
    • KTH kürzester Pfad zwischen Knoten mit Dijkstra
    • Bellman Ford Negative Zykluserkennung
  • Alle Paare am kürzesten Weg :
    • Verwenden von binärer Exponentiation
    • Floyd Warshall
  • Zykluserkennung :
    • Zykluserkennung in ungerichteten/gerichteten Graphen
  • Minimum Spanning Tree :
    • Kruskalalgorithmus
  • Topologische Sortierung / stark verbundene Komponente :
    • Topologische Sortierung
    • Stark verbundene Komponente
  • Maxflow/Matching :
    • Hopkroft Karp Max Matching
    • Dinic Max Flow
  • MISC :
    • Brücken in der Grafik
    • Konnektivität
    • Bippartiz
• Bäume :
  • Anfragen von Vorfahren :
    • Niedrigster gemeinsamer Vorfahr
    • KTH Vorfahr
  • Pfadanfragen :
    • Spärlicher Tisch *
    • Schwere leichte Zersetzung gewichtete Knoten
    • Schwere leichte Zersetzung gewichtete Kanten
  • MISC :
    • Durchmesser des Baumes
    • Vorbestellungs-/Postorder -Briefmarken, ist es in Subtree?
• Binäre Exponentiation :
  • Berechnen Sie N^m unter Verwendung einer binären Exponentiation
  • Lösung linearer Wiederholungen
• Saiten :
  • String -Algorithmen :
    • Z -Algorithmus
    • KMP -Algorithmus
    • Rolling String Hashing
    • Rolling String Hashing für dynamische Saiten
  • String -Datenstrukturen :
    • Suffix -Array *
• Sortierung :
  • Sortierung zusammenführen
  • Schnelle Auswahl
• Schnelle Eingabe/Ausgabe, String/Ganzzahlkonvertierung :
  • Schnelle Eingang/Ausgabe
  • String/Ganzzahlkonvertierung
• Miser. Datenstrukturen :
  • Disjunkt SET
  • Disjoint -set (unterstützt den Rückgängigungsbetrieb)
  • Max/min Priority Warteschlange mit Update
  • Binärer Trie für die XOR -Maximierung/Minimierung
  • Bigint *
  • Augmented Binärbaum für Bestellstatistiken und Rangabfrage
  • MONOTONE PRISEITZEUGE WANDE
  • Trie
• Anhaltende Datenstrukturen :
  • Persistente Segmentbäume (Segtree) :
    • Persistierter Segmentbaum
    • Persistenter Segmentbaum - Bestellstatistik
• Zahlentheoriealgorithmen :
  • Primalitätscheck :
    • Fermats Primalitätsprüfung
  • Sieb :
    • Sieb von Eratosthenes
    • Segmentierter Sieb für große Primzahlen
    • Primfaktoren zählen
  • Polynommultiplikation :
    • Fast Fourier Tranform
    • Karatsuba
  • MISC :
    • Kombinatorische und katalanische - faktorielle Vorverarbeitung
    • Mobeius -Funktion
    • Euler Totient -Funktion
    • Lucas Theorm - Kombinatorik
• Computergeometrie :
  • Konvexer Rumpf
• MISC :
  • Summe des Bodens (x) mit x = 1: n
  • Summe der zyklischen Funktionen *
  • Nächstes größeres Element vor/nach jedem Element
  • Multiplizieren Sie lange lange ganze Zahlen
  • Multiplizieren Sie lange lange ganze Zahlen - Überlauferkennung
  • Scanline - Überschneidende Intervalle zusammenführen