Hinweise zur Verwendung von dict mit Python [Competition Pro]

Ich hatte das Gefühl der Ablehnung für die Lügnerschaft, dass der Rechenaufwand O (1) ist (ich glaube, ich verstehe den Grund), und ich habe bis jetzt kein hartnäckiges Diktat verwendet, aber beim FHC habe ich letzte Woche teilgenommen Einfaches Problem mit Diktat

Timing zu verwenden

Wenn der Wertebereich groß und dünn ist

Operationen, die ausgeführt werden können

Haben Sie Elemente in Form von Schlüssel, Wert

Elemente können mit O (1) eingefügt, gelöscht, aktualisiert und durchsucht werden. [Referenz: Wikipedia HashTable](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86% E3% 83% BC% E3% 83% 96% E3% 83% AB)

Häufig verwendete Operationen

Beispiel

dict.py

>>>dic = dict(a=1,b=2,c=3)
#Auch wenn es sich um eine Zeichenkette handelt""Schreiben Sie so wie es ist, ohne es anzuhängen
>>> dic
{'a': 1, 'b': 2, 'c': 3}
#Fügen Sie es jedoch hinzu, wenn Sie darauf verweisen
>>> dic[a]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> dic["a"]
1
>>> dic.pop("a")
1
>>> dic
{'b': 2, 'c': 3}
#Es ist auch möglich, in dieser Schreibweise zu definieren
>>> dic.clear()
>>> dic
{}
>>> dic = {1:1,2:1,3:2,4:3,5:5}
#Schlüssel kann ein numerischer Wert sein
>>> dic[1]
1
>>> dic[1]=8
>>> dic
{1: 8, 2: 1, 3: 2, 4: 3, 5: 5}
>>> dic.get(1,-1)
8
>>> list(dic.keys())
[1, 2, 3, 4, 5]
>>> list(dic.values())
[8, 1, 2, 3, 5]
>>> list(dic.items())
[(1, 8), (2, 1), (3, 2), (4, 3), (5, 5)]
#Wenn Sie Elemente schleifen möchten
>>> for k,v in dic.items():
...     print(k,v)
...
1 8
2 1
3 2
4 3
5 5

Verwendung im Wettbewerb professionelle Fragen

Da es eine große Sache ist, werde ich das zu Beginn eingeführte FHC-Problem mit dict lösen. Wenn Sie an dem Problem selbst interessiert sind, versuchen Sie es bitte mit Erklärung, die ich geschrieben habe.

Dieses Mal habe ich, abgesehen von Deklaration und Zuweisung, nur die Wertreferenz mit get und loop mit items () verwendet, aber ich konnte spärliches dp leicht schreiben. Es war ein Unterschied zu idx in der Dichotomie, daher würde ich es gerne auch in Zukunft verwenden.

timer.py

import bisect
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# step1:Setzen Sie sich (in sortierter Reihenfolge))Führen Sie die DP sowohl am linken als auch am rechten Rand durch
# dp_l[i] = max(dp_l[j] + h[i],h[i])Baum führt zu Platz i(i=j+h[j])Suche nach Diktat
# dp_r[i] = max(dp_r[j] + h[i],h[i]) 
# step2:dp_l_Für alle Schlüssel, die ich diktiere, dp_r_Finden Sie heraus, ob es in der Tonart Diktat mit Diktat liegt(p[i]+h[i]Ist p[j]-h[j]Wird j i,Entspricht der Suche nach j)
# step3:Matching in Schritt 2 i,für j, ans= max(ans,dp_l[i]+dp_r[j])
t = int(input())
for case in range(t):
    n = int(input())
    p = [0] * n
    h = [0] * n
    for i in range(n):
        p[i], h[i] = map(int, input().split())
    p, h = zip(*sorted(zip(p, h)))
    #In aufsteigender Reihenfolge mit p siehe in aufsteigender Reihenfolge für diejenigen, die nach rechts verschoben werden, und in absteigender Reihenfolge für diejenigen, die nach links verschoben werden.

    #Von links schauen Zu dem, was Sie von links sehen
    #dp hat den Schlüssel als pos,Wert setzt in Länge
    dp_r_dict = {}  #Pos endet in einer Reihe von Bäumen, die nach rechts fallen(Rechtes Ende) Die längste Länge in der Spalte
    dp_l_dict = {}
    for i in range(n):
        # dict[p[i]]Wenn dies der Fall ist, wird es zurückgegeben, andernfalls wird 0 zurückgegeben
        #Wenn P[i]Wenn es etwas gibt, mit dem es endet, können Sie es verbinden und dehnen
        tmp = dp_l_dict.get(p[i], 0) + h[i]
        if dp_l_dict.get(p[i] + h[i], 0) < tmp:  #Ähnlich
            dp_l_dict[p[i] + h[i]] = tmp
    r_max = 0
    for i in range(n - 1, -1, -1):
        tmp = dp_r_dict.get(p[i], 0) + h[i]
        if dp_r_dict.get(p[i] - h[i], 0) < tmp:
            dp_r_dict[p[i] - h[i]] = tmp
            r_max = max(r_max, dp_r_dict[p[i] - h[i]])
    # step3:dp_l_Zum Diktieren dp mit allen Tasten_r_Überprüfen Sie, ob eine Übereinstimmung mit dem Diktatschlüssel vorliegt, und nehmen Sie max
    ans = 0
    for pos, l_len in dp_l_dict.items():
        tmp = l_len + dp_r_dict.get(pos, 0)  #Alle können nach rechts zeigen
        ans = max(ans, tmp)
    #Betrachten Sie alles nach links
    ans = max(ans, r_max)
    case_str = "Case #" + str(case + 1) + ": " + str(ans)
    print(case_str)

Am Ende

Bitte kommentieren Sie, wenn Sie Fehler haben oder besser schreiben.

Referenz

python Document