[PYTHON] AtCoderBeginnerContest171 Review & Summary (zweite Hälfte)

AtCoder ABC171 Dies ist eine Zusammenfassung der Probleme des AtCoder-Anfängerwettbewerbs 171, der am 21.06.2020 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Die zweite Hälfte befasst sich mit dem DE-Problem. Klicken Sie hier für die erste Hälfte. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

D Problem Ersetzen

Problemstellung Sie haben eine Folge von $ A $, die aus $ N $ positiven ganzen Zahlen $ A_1, A_2, ⋯, A_N $ besteht. Sie werden weiterhin die folgenden $ Q $ -Zeiten ausführen. ・ In der Operation $ i $ werden alle Elemente mit dem Wert $ B_i $ durch $ C_i $ ersetzt. Ermitteln Sie für alle $ i (1 \ leq i \ leq Q) $ die Summe aller Elemente der Sequenz $ A $ nach der $ i $ -Operation $ S_i $.

Ich dachte, dass mir die Zeit ausgehen würde, wenn ich die Summe jedes Mal berechnen würde, also beschloss ich, die Differenz für jede Operation zu berechnen. Die Zahlenfolge $ A $ wird von dict verwaltet.

abc171d.py

n = int(input())
a_list = list(map(int, input().split()))
a_dict = {}
total = 0
for a in a_list:
    if a in a_dict:
        a_dict[a] += 1
    else:
        a_dict[a] = 1
    total += a

q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if b in a_dict:
        if c in a_dict:
            a_dict[c] += a_dict[b]
        else:
            a_dict[c] = a_dict[b]
        total -= a_dict[b] * b
        total += a_dict[b] * c
        a_dict[b] = 0
    print(total)

Ich konnte das D-Problem reibungslos lösen. Das nächste E-Problem konnte ich jedoch nicht lösen.

E Problem Roter Schal

Problemstellung Es gibt $ N $ (** sogar **) Katzen. Jedes Sunuke-Kun ist mit $ 1,2,…, N $ nummeriert. Jeder Sunuke-Kun hat einen roten Schal um den Hals und der Schal hat $ 1 $ der nicht negativen ganzen Zahl, die er am liebsten mag. Sunuke und seine Kollegen haben kürzlich eine Operation namens xor (exklusive logische Summe) für ganze Zahlen gelernt. Sofort beschlossen Sunuke-kun und andere, die diese Berechnung verwenden wollten, das xor der Ganzzahl zu berechnen, die auf dem Schal von Sunuke-kun außer ihm selbst geschrieben war. Es ist bekannt, dass die Ganzzahl xor, die auf den Schal eines anderen Sunuke-Kun geschrieben ist und von Sunuke-Kun mit der Zahl $ i $ berechnet wurde, $ a_i $ ist. Verwenden Sie diese Informationen, um die Ganzzahl zu identifizieren, die auf jedem Sunuke-Kun-Schal steht.

Bei 4264 Personen war das E-Problem gelöst, und als das D gelöst wurde, war es ungefähr der 2000. Platz, aber am Ende war die Rangliste nicht erkennbar. Gerade Zahlen waren die Punkte. Ich habe auch versucht, verschiedene Formeln in meinem Notizbuch zu berechnen, aber ich konnte keine Formel finden, um die Antwort zu finden. Ich denke, ich kann es das nächste Mal lösen, also möchte ich sagen, dass ich gelernt habe.

abc171e.py

n = int(input())
a_list = list(map(int, input().split()))
y = 0
for a in a_list:
    y = y ^ a
for a in a_list:
    x = y ^ a
    print(x, end=" ")

Ich bin auch diese Woche beschäftigt, also möchte ich es hinzufügen, auch wenn ich Zeit habe.

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.