Es wird gesagt, dass die Verwendung von "in" (Verwendung von "in" in einer Schleife) jedes Mal, wenn wiederholt beurteilt wird, ob ein Element in der Liste vorhanden ist, langsam sein kann. Aus der Schlussfolgerung geht hervor, dass "es langsam ist, in der Liste mit" in "zu suchen, anstatt" an "selbst langsam ist". Ich hatte es leicht bemerkt, aber es war wahrscheinlich das erste Mal, dass ich einen solchen Geschwindigkeitsunterschied bemerkte.
Das Folgende ist ein ähnliches Programm, das in ABC167D eingereicht wurde, aber das erste besteht darin, die Liste mit "in" in einer Schleife zu durchsuchen, und es wird eine On-Parade von "TLE". Auf der anderen Seite erstellt die zweite eine separate Liste für Flags und verarbeitet sie, und sie ist leicht "AC" (139 ms). Darüber hinaus ist das dritte Experiment ein Experiment, das auf dem Rat einer freundlichen Person basiert: "Sie sollten das Suchziel so einstellen, dass es anstelle der Liste festgelegt wird." Dies wurde auch leicht zu "AC" (188 ms).
AtCoder Beginner Contest 167 D - Teleporter
ABC167D/TLE
n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #Liste der Städte (einschließlich der ersten), die ich bisher besucht habe
twn = 1 #Teleporter-Transferziel
for _ in range(k):
if a[twn - 1] not in dst: #Wenn das Teleporter-Transferziel nicht in der Liste der von Ihnen besuchten Städte aufgeführt ist
dst.append(a[twn - 1]) #Wenn nicht, fügen Sie es der Liste der Städte hinzu, die Sie besucht haben
twn = a[twn - 1] #Teleporter-Übertragungsziel aktualisieren
else: #Wenn sich das Teleporter-Transferziel in der Liste der Städte befindet, die Sie bisher besucht haben (das Transferziel von dort wird wiederholt).
index = dst.index(a[twn - 1]) #Holen Sie sich den Index des Teleporter-Transferziels in die Stadtliste, die Sie bisher erstellt haben
ld = len(dst[:index]) #Finden Sie die Länge vor dem Looping und die Periode des Loop-Teils
cyc = len(dst[index:])
print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
exit()
print(dst[-1])
ABC167D/AC139ms
n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n #Flaggenliste, ob Sie in jede Stadt gegangen sind(Stimmt, wenn nicht weg)
dst = [1]
twn = 0 #Teleporter-Transferziel(Flag Listenindex)
for _ in range(k):
if flg[twn]:
dst.append(a[twn])
flg[twn] = False
twn = a[twn] - 1
else:
index = dst.index(a[twn])
ld = len(dst[:index])
cyc = len(dst[index:])
print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
exit()
print(dst[-1])
ABC167D/AC188ms
n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #Liste der Städte (einschließlich der ersten), die ich bisher besucht habe
dsts = set(dst) #Eine Reihe von Städten (einschließlich der ersten), die ich bisher besucht habe
twn = 1 #Teleporter-Transferziel
for _ in range(k):
if a[twn - 1] in dsts: #Wenn sich das Teleporter-Transferziel in der Stadt befindet, in der Sie sich befunden haben (Transfers von dort werden wiederholt)
index = dst.index(a[twn - 1]) #Holen Sie sich den Index des Teleporter-Transferziels in die Stadtliste, die Sie bisher erstellt haben
ld = len(dst[:index]) #Finden Sie die Länge vor dem Looping und die Periode des Loop-Teils
cyc = len(dst[index:])
print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
exit()
else: #Wenn sich das Teleporter-Transferziel nicht in der Stadt befindet, in der Sie sich befunden haben
dst.append(a[twn - 1]) #Wenn nicht, fügen Sie es der Liste der Städte hinzu, die Sie besucht haben
dsts.add(a[twn - 1])
twn = a[twn - 1] #Teleporter-Übertragungsziel aktualisieren
print(dst[-1])
Fazit Wenn Sie das Vorhandensein oder Nichtvorhandensein in einer Schleife mehrmals bestimmen möchten, anstatt die Zielliste direkt mit "in" zu durchsuchen, überprüfen Sie einen separat erstellten Suchsatz mit "in" oder verwenden Sie "in" für Flags. Es ist überwältigend schneller, eine Liste zu erstellen und nachzuschlagen.
Recommended Posts