Der Teil über die Bibliothek von Tipps, die Sie beim Programmieren von Wettbewerben mit Python2 kennen sollten wurde geteilt.
Die Python-Version ist ** 2.7.5 ** (In Python3 unterscheiden sich Spezifikationen wie Eingabe und Ausgabe erheblich, daher wird empfohlen, auf andere Artikel zu verweisen).
Hier sind einige Bibliotheken, die ich nützlich finde, obwohl sie etwas geringfügig sind.
Ich werde es eines Tages schreiben.
9.7. Itertools - Iterator-Generierungsfunktion für eine effiziente Schleifenausführung
Verwenden Sie itertools, um Kombinationen und Sequenzen in Python | CUBE SUGAR STORAGE abzurufen
Eine Bibliothek voller Methoden zum Generieren von Iteratoren.
In der Konkurrenzprogrammierung ist es nützlich, wenn Sequenzen und Kombinationen generiert werden (entsprechend next_permutation in C ++). Es arbeitet viel schneller als das Drehen mehrerer Schleifen selbst, daher sollten Sie es aktiv verwenden.
permutations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Wählen Sie zwei Elemente aus l und ordnen Sie sie an
#Betrachten Sie keine Vervielfältigung
#Bestellung wird berücksichtigt(Permutation)
for elem in itertools.permutations(l, 2):
print elem #Das Taple der angeordneten Elemente ist elem zugeordnet
output
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
combinations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Wählen Sie 3 Elemente aus l und ordnen Sie sie an
#Betrachten Sie keine Vervielfältigung
#Berücksichtigt die Bestellung nicht(Kombination)
for elem in itertools.combinations(l, 3):
print elem
output
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)
Übrigens ist es auch möglich, Kombinationen zu erhalten, die die Vervielfältigung berücksichtigen, und kartesische Produkte (direkte Produkte).
combinations_with_replacement.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Ordnen Sie die beiden Sätze der extrahierten Elemente von l an
#Betrachten Sie die Vervielfältigung
#Berücksichtigt die Bestellung nicht
for elem in itertools.product(l, repeat=2):
print elem
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 3)
(3, 4)
(3, 5)
(4, 4)
(4, 5)
(5, 5)
cartesian_product.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Ordnen Sie die beiden Sätze der extrahierten Elemente von l an
#Betrachten Sie die Vervielfältigung
#Bestellung wird berücksichtigt
for elem in itertools.product(l, repeat=2):
print elem
#Der obige Code entspricht dem folgenden Code
for a in l:
for b in l:
print (a, b)
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
(5, 5)
collections
8.3. Sammlungen - Hochleistungscontainer-Datentyp - Python 2.7ja1-Dokumentation
Das Python-Sammlungsmodul ist nüchtern und praktisch - Yuimono Seishin @Scaled_Wurm
defaultdict
Wie der Name schon sagt, ist collection.defaultdict ein Diktat mit Standardwerten.
In der Wettbewerbsprogrammierung gibt es viele Möglichkeiten, Zähler zu erstellen (insbesondere bei Implementierungsproblemen).
Wenn beispielsweise eine Frage zur Häufigkeit der in der Eingabe vorhandenen englischen Wörter gestellt wird, muss mit dict ein Zähler erstellt werden, der jedem Wort entspricht, aber dict initialisiert den Schlüssel. Andernfalls tritt ein Fehler auf, der problematisch ist.
Mit defaultdict können Sie die Initialisierung reduzieren und das Lesen des Codes erleichtern.
from collections import defaultdict
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
#Für dikt
d = {}
for e in l:
#Überprüfen Sie jedes Mal, ob ein Schlüsselwert vorhanden ist. Andernfalls müssen Sie eine Initialisierung durchführen
if e in d.keys():
d[e] += 1
else:
d[e] = 1
print d # {'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2}
dd = defaultdict(int) #Alle Schlüssel werden mit 0 initialisiert
for e in l:
dd[e] += 1 #Keine Notwendigkeit zu initialisieren
print dd # defaultdict(<type 'int'>, {'be': 2, 'that': 1, 'is': 1, 'question': 1, 'to': 2, 'not': 1, 'the': 1, 'or': 1})
print dd['be'] # 2
dd2 = defaultdict(list) #Alle Schlüssel[]Initialisiert mit
dd2['a'].append(1)
print dd2 # defaultdict(<type 'list'>, {'a': [1]})
collection.Counter ist ein Objekt, das auf die Erstellung von Zählern spezialisiert ist, und 0 wird automatisch als Anfangswert festgelegt. Dies entspricht "defautdict (int)", es gibt jedoch einige andere nützliche Funktionen, z. B. kann der Maximalwert sofort ermittelt werden.
from collections import Counter
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
c = Counter()
for e in l:
c[e] += 1
print c # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
print c['be'] # 2
#Wenn Sie eine Liste usw. als Argument übergeben, wird diese automatisch gezählt
c2 = Counter(l)
print c2 # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
#Nach absteigendem Zählerwert sortieren
print c.most_common() # [('be', 2), ('to', 2), ('that', 1), ('is', 1), ('question', 1), ('not', 1), ('the', 1), ('or', 1)]
#Gibt 3 in der Reihenfolge von dem mit dem größten Zählerwert aus
print c.most_common(3) # [('be', 2), ('to', 2), ('that', 1)]
Recommended Posts