competitive_programming

Wettbewerbsprogrammierung und Übungen

Dies sind meine C ++ - Lösungen einiger Wettbewerbsprogramme und verschiedene Übungen. Ähnliche Probleme werden unter Verwendung verschiedener Algorithmen und Datenstrukturen gelöst - manchmal unter Verwendung derjenigen, die in der Standardbibliothek bereitgestellt werden, manchmal mit meinen eigenen.

Die meisten Lösungen sind in C+11 aufgrund der Ex-UVA-Online-Richterbeschränkung. Einige von ihnen nach erfolgreicher Einreichung wurden so geändert, dass sie C ++ 14/17 -Funktionen verwenden.

Ex-Uva OJ-Probleme

Probleme Quelle

AUSWEIS	Titel	Kategorien
001 08	Maximale Summe	Lineare Suche, maximale Summe Subarray, Kadanes Algorithmus
001 09	Scud Busters	Konvexer Rumpf
001 12	Baumsummierung	Binärbaum
001 20	Stapel von Flapjacks	Stapel, Pfannkuchensortierung
001 22	Bäume auf der Ebene	Binärbaum, Durchlauf der Ebene der Ebene, Breite, die erste Suche
001 40	Bandbreite	Permutationen, Backtracking
001 47	Dollar	Dynamische Programmierung, Münzänderung
001 64	Saitencomputer	Dynamische Programmierung, Entfernung bearbeiten
002 00	Seltene Ordnung	Topologische Sortierung, Tiefe-First-Suche
002 16	In die Schlange stehen	Dynamische Programmierung, Hamiltonianische Pfad, Bitmasken
002 18	MOTH -Ausrottung	Konvexer Rumpf
002 22	Budgetreisen
002 40	Variable Radix Huffman Codierung	Huffman Tree, Tiefe-First-Suche
002 59	Softwarezuweisung
002 64	Zählen auf Cantor
002 70	Sich anstellen
002 94	Divisors
003 34	Identifizierung gleichzeitiger Ereignisse
003 48	Optimal Array mult. Sequenz	Dynamische Programmierung, Matrixkettenmultiplikation
003 50	Pseudo -Zufallszahlen
003 53	Lästige Palindrome	Polynom -Roll -Hash, String -Verarbeitung
003 57	Zählen Sie die Wege
003 61	Polizisten und Räuber
003 72	Whatfix Notation	Binärbaum, Pre-/In-/Post-Order-Traverals-Umwandlung
003 74	Big Mod	Binäre Exponentiation, modulare Exponentiation
004 29	Worttransformation
004 37	Turm von Babylon
004 39	Ritter bewegt sich	Breite-First-Suche
004 54	Anagramme
004 55	Periodische Saiten	Saiten, Knuth -Morris -Pratt -Algorithmus
004 59	Grafikkonnektivität	Disjoint-Set/Union-Find, Graph Connected-Komponenten
004 69	Feuchtgebiete von Florida
004 81	Was geht auf	Die längste zunehmende Subquenz, binäre Suche
004 82	Permutationen Arrays
005 01	Schwarze Box	AVL -Baum, Binärbaum -Iterator
005 07	Jill reitet wieder	Lineare Suche, maximale Summe Subarray, Kadanes Algorithmus
005 16	Erstklassiges Land
005 26	Stringentfernung	Dynamische Programmierung, Entfernung bearbeiten
005 36	Baumwiederherstellung	Binärbaum, Pre-/In-/Post-Order-Traverals-Umwandlung
005 40	Team -Warteschlange
005 43	Goldbach -Vermutung	Primzahlen
005 48	Baum
005 51	Haufen von Klammern nisten
005 58	Wurmlöcher
005 62	Münzen teilen
005 68	Nur die Fakten	Faktororial, Rezidivbeziehung
005 74	Fassen Sie es zusammen
005 82	Zufällig verdrahtete neuronale Netze	Tiefe-First-Suche, bikonische Grafikkomponente
005 83	Hauptfaktoren
006 12	DNA -Sortierung	Sortierung zusammenführen, Inversionszählen
006 23	500!	Faktor, große Ganzzahl
006 30	Anagramme
006 39	Lass dich nicht abfließen lassen
006 74	Münzwechsel
006 79	Bälle fallen lassen
006 84	Integrale Determinante	Gaußsche Eliminierung, euklidischer Algorithmus
006 86	Goldbach -Vermutung II	Primzahlen
007 01	Das Archäologen -Dilemma	Logarithmus
007 14	Bücher kopieren	Lineare Partitionierung, implizite binäre Suche
007 19	Glasperlen	Lexikographisch minimaler Rotation, Duvans Algorithmus
007 27	Gleichung	Ausdrucksanalyse, Rangierhartenalgorithmus
007 29	Das Problem der Hamming -Entfernung	Backtracking
007 50	Acht Queens Schachproblem	Backtracking
007 87	Maximales Absquenzprodukt	Maximale Produktsubrat, große Ganzzahl
007 93	Netzwerkverbindungen
007 96	Kritische Links	Tiefe-First-Suche, Graph Bridge
008 20	Internetbandbreite
008 33	Wasser fällt
008 68	Numerisches Labyrinth	Backtracking
008 72	Bestellung
009 08	Computerstellen wieder anschließen
009 29	Zahlenlabyrinth
009 42	Zyklische Zahlen	Rationale Zahl, Dezimalbruchung, Hash -Tabelle
009 90	Tauchen für Gold
009 91	Sichere Grüße	Kombinatorik, Rezidivbeziehung, katalanische Zahlen
011 21	Subsequenz	Schiebefenster
011 75	Damenwahl	Stabiles Matching-Problem, Sturm-Form-Algorithmus
012 10	Summe der aufeinanderfolgenden Primzahlen	Primzahlen
012 52	Zwanzig Fragen
012 60	Verkäufe
012 93	Symbolische Ableitung	Ausdrucksanalyse, Mied Yard -Algorithmus, symbolische Bewertung.
013 72	Protokollsprung
016 50	Zahlenzeichenfolge	Kombinatorik, Rezidivbeziehung
100 03	Stöcke schneiden
100 04	Bicoloring
100 18	Umkehren und hinzufügen	Ganzzahlen, 196-Algorithmus
100 61	Wie viele Nullen und Ziffern?	Faktorial, Primzahlen, Faktorisierung, Logarithmus
100 79	Pizza schneiden	Kombinatorik, zentrale polygonale Zahlen
101 07	Was ist der Median?	Prioritätswarteschlange, Online -Algorithmen
101 71	Treffen prof. Miguel
101 93	Alles was du brauchst ist Liebe	Größter gemeinsamer Divisor
102 20	Ich liebe große Zahlen!	Faktor, große Ganzzahl
102 23	Wie viele Knoten	Kombinatorik, Rezidivbeziehung, katalanische Zahlen
102 29	Modular Fibonacci	Fibonacci -Zahlen, modulare Exponentiation
102 45	Das engste Paarproblem	2d nächstes Punktpaar
102 68	498-Bis	Horners Regel
102 82	Babelfisch	Hash -Tisch
102 98	Power Saiten
103 05	Aufgaben bestellen
103 11	Goldbach und Euler	Primzahlen
103 19	Manhattan
103 27	Flip -Sortierung	Avlbaum
103 41	Löse es	Numerics, Newtons Methode
103 64	Quadrat	Backtracking, Bitmasken
103 82	Gras gießen	Gierig, Intervallabdeckung
104 28	Die Wurzeln	Root -Erkenntnis, Bisektionsmethode
104 54	Trexpression	Ausdrucksanalyse, Rangierhartenalgorithmus, katalanische Zahlen
104 96	Piepers sammeln
105 33	Ziffernprimzahlen
105 67	Helfen Sie, Bates zu füllen
105 70	Treffen mit Aliens	Permutation, Swapszählungen, Zyklenzählen
105 76	Y2K -Buchhaltungsfehler
105 86	Polynomreste
106 00	ACM -Wettbewerb und Stromausfall
106 04	Chemische Reaktion
106 51	Kieselsoritaire
106 55	Betrachtung! Algebra	Rezidivbeziehung, modulare Exponentiation
106 64	Gepäck
106 84	Jackpot
106 99	Zählen Sie die Faktoren	Primzahlen, Prime -Zerlegung
107 23	Cyborg -Gene
107 38	Riemann gegen Mertens	Primzahlen, Möbius -Funktion, Mertens -Funktion
108 01	Heben Sie Hopfen
108 10	Ultra Quicksort	Sortierung verschmelzen/einfügen, Inversionszählen
108 55	Gedrehte Quadrate	Matrixrotation, Matrixtransposition
108 70	Rezidive
109 20	Spiralhahn	Analytischer Ausdruck
109 31	Parität
109 34	Wasserballons fallen lassen
109 35	Karten wegwerfen	Warteschlange, einzig gebundene Liste
109 38	Flohzirkus
109 54	Fügen Sie alle hinzu	Haufen
109 57	Su doku Checker	Backtracking, Bit Maske
109 94	Einfache Addition	Analytischer Ausdruck
110 57	Genaue Summe
110 60	Getränke
110 77	Finden Sie die Permutationen	Kombinatorik, Rezidivbeziehung, Stirling -Zahlen
111 37	Genialer Kämpfer
111 51	Längste Palindrome	Dynamische Programmierung, String -Verarbeitung
111 71	SMS	Dynamische Programmierung, Stringverarbeitung, Trie
111 95	Ein weiteres N -Queen -Problem	Backtracking, Bit Maske
112 27	Die silberne Kugel
112 35	Häufige Werte
112 36	Lebensmittelgeschäft
112 57	Neuer Marketingplan	Polygon, eingeschriebener Kreisradius, Prioritätswarteschlange
112 58	String -Partition	Dynamische Programmierung
112 60	Ungerade Wurzelsumme	Analytischer Ausdruck, impl. binäre Suche, modulare Arithmetik
112 71	Widerstandsgitter	Rezidivbeziehung, asymptotische Expansion
112 83	Boggle spielen	Backtracking
112 97	Volkszählung	2d SQRT -Zersetzung
113 62	Telefonliste	Trie, Präfix -Matching
114 13	Füllen Sie die Behälter
114 20	Kommode	Kombinatorik, Rezidivbeziehung
114 56	Trainierende
114 61	Quadratnummern	Implizite binäre Suche
114 62	Altersart	Zählen
114 63	Kommandos
114 75	Sich bis palindrome erstrecken
115 17	Genaue Änderung
115 36	Kleinstes Unterarray	Schiebefenster
115 72	Einzigartige Schneeflocken	Lineare Suche, Hash -Tabelle
115 84	Aufteilung durch Palindrome
116 21	Kleine Faktoren	Logarithmus
116 34	Zufällige Zahlen generieren
116 36	Hallo Welt!	Analytischer Ausdruck, Logarithmus
116 58	Beste Koalitionen
116 86	Stöcke aufnehmen
116 91	Allergietest
117 03	Sqrt, log, sin	Rezidivbeziehung
117 14	Blindsortierung	Bestellstatistik (2. ND größte)
117 33	Flughäfen
119 02	Dominator
119 91	Einfaches Problem von Rujia Liu?	Sortierung, binäre Suche
119 97	K kleinste Summen
120 86	Potentiometer	Fenwick Tree
121 05	Größer ist besser (1)
121 05	Größer ist besser (2)
121 92	Weinrebe	Binäre Suche
122 38	Ameisenkolonie
123 47	Binärer Suchbaum	Binärer Suchbaum, Vor-/Nachbestellung durchweg
124 55	Barren	Vollständige Suche, Backtracking
124 58	Oh, meine Bäume!
124 62	Rechteck	Lineare Suche, Stapel, Bitmaske
124 94	Eindeutiges Substring	Lex. Minimale Rotation, Duvans Algorithmus, Hash -Tabelle
125 04	Aktualisieren eines Wörterbuchs	Schnelle Sortierung
126 40	Größtes Summenspiel	Lineare Suche, maximale Summe Subarray, Kadanes Algorithmus
126 97	Minimale Subtarraylänge	Lineare Suche, maximale Summe Subarray, Kadanes Algorithmus
127 02	Erweiterung	Binäre Morphologie, binäre Bilddilatation
129 11	Teilmenge Summe	Subset Summe, vollständige Suche, Meet-in-the-Middle
130 50	Wege entdecken	Kombinatorik, Rezidivbeziehung
132 82	Cakey McCakeface (1)	Sortierung, lineare Suche
132 82	Cakey McCakeface (2)	Bitmaske, Eimer

Internationaler Hochleistungs -Computing -Wettbewerb

Probleme Quelle

AUSWEIS	Titel	Kategorien
C2	Holen Sie sich das Bild	Fractal, Mandelbrot Set, MPI, std::thread

Andere Probleme und Übungen

Verschiedene Probleme aus verschiedenen Online -Quellen.

Titel	Kategorien
Array zum binären Suchbaum	Binärer Suchbaum
Array mit Einheit adj. Differenzsuche	Lineare Suche
Binär sortierte Array -Übergangspunkt	Binäre Suche
Binärbaumdurchmesser	Binärbaum, Tiefe-First-Traversal
Binärbaum -Top -Ansicht	Binärbaum, Breite-First-Traversal
Bitonic Array -Suche	Binäre Suche
Gemeinsame Elemente in drei Array	Lineare Suche
Verbindungspunkt in Y-förmigen verknüpften Listen	Einzelliste
Zählen Sie Anagram Substrings	Hash -Tisch, Schiebfenster
Zählen Sie kleinere Elemente rechts	Avlbaum
Zählen Sie Quadrate in Postcodes	Analytischer Ausdruck
Zählen Sie die Drillinge	Lineare Suche, Paar Summe Suche
Spaltbarkeit in einem binären Strom	Modulare Arithmetik, Spaltbarkeit
Gleichgewichtspunkt	Lineare Suche
Klammern erzeugen (1)	Kombinatorik, Backtracking
Hat eine Untergruppe mit einer Summe	Dynamische Programmierung
Ist eine verknüpfte Liste ein Palindrom	Einzelliste
Ist ein Unterbaum (1)	Binärbaum, Tiefe-First-Traversal
K-Th-Element in der Zeilensäule sortierte Matrix	Haufen
Größte Zahl mit K Swaps	Backtracking
Größtes Rechteck in einem Histogramm	Lineare Suche, Stapel
Größtes Quadrat Eine Boolesche Matrix	Dynamische Programmierung, größte quadratische Submatrix
Die letzten zwei Ziffern von Fibonacci	Fibonacci -Zahlen, modulare arithmetische, binäre Exponentiation
LISTE MERGE	Einzelliste
LISTE MERGE SORT	Einzig verbundene Liste, Zusammenführungsart
Längste Unterscheidungs-Charakter-Substring	Lineare Suche
Längste palindromische Summensubstring	Lineare Suche
Mehrheitselement	Boyer -Moore -Mehrheitsstimmenalgorithmus
Array strikt zunehmen	Die längste zunehmende Subquenz, binäre Suche
Matrixrotation	Matrixrotation, Matrixtransposition
Maximaler Abstand zwischen sortierten Elementen	Lineare Suche
Maximaler numerischer Wert in einer Zeichenfolge	Lineare Suche, lexikografischer Vergleich
Maximum von jedem Subtarray (1)	Schiebefenster, ausgeglichener binärer Baum
Maximum von jedem Subtarray (1)	Schiebefenster, Deque
Maximales Produkt von 3 Elementen	Lineare Suche
Min-Stack	Stapel
Minimales Element in sortiertem gedrehtem Array	Binäre Suche
Mindestanzahl von Sprüngen (1)	Dynamische Programmierung
Mindestanzahl von Sprüngen (2)	Lineare Suche
Fast sortiert	Haufensart, Insertion -Sortierung
Nächstes größeres Element	Lineare Suche, Stapel
Knoten in der Entfernung k im binären Baum	Binärbaum, Tiefe-First-Traversal
Anzahl der Pfade in einem Netz	Kombinatorik
Gleiche und seltsame Knoten	Einzelliste
Schlange als zwei Stapel	Warteschlange, Stapel
Entfernen Sie doppelte Knoten	Einzelliste
Mittelknoten entfernen	Einzelliste
Stellen Sie ein Alphabet aus einem Wörterbuch wieder her	Topologische Sortierung, Kahns Algorithmus
Eine einzeln verknüpfte Liste umkehren	Einzelliste
Reverse Wörter in einer Zeichenfolge umgekehrt	Lineare Suche
Drehen Sie eine einzeln verknüpfte Liste	Einzelliste
Drehete Array -Suche	Binäre Suche, lineare Suche
Zweitgrößte	Bestellstatistik, zweitgrößtes Element, binärer Zähler
Zeilen und Spalte einstellen, wenn	Lineare Suche
Kleinste Zahl in einer Permutation	Lineare Suche
Sortierte die Absatz von Größe 3	Lineare Suche
Sortierte die Absatz von Größe 4	Lineare Suche
Quadratwurzel	Implizite binäre Suche
Subarray mit gegebener Summe	Lineare Suche
Drei -Wege -Partition	Array -Partitionierung
Zwei Elemente mit der angegebenen Summe	Lineare Suche, Hash -Tabelle
Ungeordnete gleiche Arrays	Sequenz, Hash -Tabelle
Xor verlinkte Liste	Doppelt verknüpfte Liste
Subarray mit Nullsummen	Lineare Suche, Hash -Tabelle