Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.
Die Lösung, die ich hier schreibe, wurde geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansah. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.
S Schaf und W Wolf, Gewinnen ist eine Frage, die gestellt werden muss.
Wenn S größer als W ist, werden die Schafe nicht angegriffen.
S, W = map(int, input().split())
if S > W:
print('safe')
else:
print('unsafe')
Es ist eine Frage zu beantworten, welche gewinnt, wenn sich die Angriffskraft B mit physischer Stärke A und die Angriffskraft D mit physischer Stärke C treffen.
Takahashi-kun und Aoki-kun benötigen jeweils die Anzahl der Angriffe, aufgerundet auf $ C / B $ und $ A / D $. Der mit der kleineren Anzahl gewinnt. Auch wenn die Zahlen gleich sind, ist Takahashi, der zuerst geschlagen werden kann, vorteilhaft.
Ich habe es mit der obigen Idee umgesetzt. Ich habe math.ceil () für den Aufrundungsprozess verwendet. Wenn Sie etwas wie (C + (B-1)) // B schreiben, benötigen Sie keine Bibliothek.
import math
A, B, C, D = map(int, input().split())
if math.ceil(C/B) <= math.ceil(A/D):
print('Yes')
else:
print('No')
Es ist ein Problem zu zählen, wie viele Arten von Zeichenketten $ S_i $ N-mal eingegeben werden.
Ich legte es in ein Objekt vom Typ Set und zählte die Länge.
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
Es ist eine Frage, wie viele Zahlen bis 2019 teilbar gemacht werden können, wenn die Eingangsnummer S in einem beliebigen Abschnitt herausgeschnitten wird.
Ich dachte, es sei ein ähnliches Thema wie this und schrieb den folgenden Code. (Eigentlich konnte ich es während des Wettbewerbs nicht machen, weil ich einen Fehler gemacht oder die Zeit nicht verkürzt habe.)
import collections
S = input()
N = len(S)
M = [0]
mod = 0
ten = 1
for s in S[::-1]:
mod += (int(s) * ten) % 2019
mod %= 2019
M.append(mod)
ten *= 10
ten %= 2019
count = collections.Counter(M)
print(sum([c*(c-1)//2 for c in count.values()]))
Wenn beispielsweise eine Zahl "1234567" vorhanden ist, berechnet dieser Prozess den Überschuss von "7", "67", "567", "4567", "34567", "234567" und "1234567", und der Überschuss stimmt überein. Wenn mehrere Ziffern vorhanden sind, ist der Abschnitt teilbar.
Bei der eigentlichen Verarbeitung wird die Berechnungszeit gespart, indem sie häufig geteilt und die Überschussberechnung durchgeführt wird.
Eine ausführliche mathematische Erklärung finden Sie in Frage E in Artikel, den ich zuvor geschrieben habe.
Das Problem besteht darin, den kürzesten Weg von Station 1 zu allen Stationen zu finden. Sie benötigen jedoch Silbermünzen, um den Zug zu benutzen, und Sie müssen an jedem Bahnhof unterschiedliche Zeit damit verbringen, Geld auszutauschen.
Bisher hat ABC nur Frage E beantwortet, aber dies ist fast das erste Mal für ein solides Diagrammproblem. Ich habe es überhaupt nicht verstanden und aufgegeben.
Ich habe viele Erklärungen und andere Antworten gesehen.
Erstens beträgt aufgrund des Limits von $ 2 \ leq N \ leq 50 $, $ 1 \ leq A_i \ leq 50 $ die Gesamtzahl der Silbermünzen, die von diesem System getragen werden können, $ 49 \ times50 = 2450 $. (Diese Zahl kann in Abhängigkeit von den tatsächlichen Werten von "N" und "A" weiter verringert werden. Der Einfachheit halber wird diese Zahl jedoch erläutert.)
"Mindestzeit $ T $ beim Halten von Münzen an Station n" wird im folgenden Array gespeichert.
T[n][coins]
Sie können es wie folgt erstellen. Geben Sie als Anfangswert einen ausreichend großen Wert ein.
T = [[10**18 for _ in range(2451)] for _ in range(N)]
Mögliche Verhaltensmuster für jede Station sind "Kosten" -Kostenblätter, Zeit $ t $, um zur benachbarten Station $ m $ zu gelangen "" Zeit $ t $, um Goldmünzen an derselben Station zu verwenden -Es bleibt keine andere Wahl, als gegen "Kosten" zu tauschen (gehen Sie zu $ m = n $ und denken Sie, dass Sie negative "Kosten" verbraucht haben). Behandle dieses Verhalten als Taple.
(m, cost, t)
Speichern Sie diesen Taple als Array für jede Station $ n $.
act[n] = [(Aktion 1), (Aktion 2), (Aktion 3), ....]
Der folgende Code speichert die eingegebenen Werte in diesen.
N, M, S = map(int, input().split())
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
Da die Suche von hier aus durchgeführt wird, wird der Status der Suchquelle in der Prioritätswarteschlange gespeichert. Behandle einen Zustand als Taple. Die aktuelle Zeit $ currentT $, die aktuelle Station $ n $ und die Anzahl der im Besitz befindlichen Silbermünzen $ coin $ werden wie folgt ausgedrückt.
(currentT, n, coins)
Der Anfangszustand der Prioritätswarteschlange ist wie folgt.
que = [(0, 0, S)]
Das zweidimensionale Array "T" wird gefüllt, indem aus dieser Warteschlange in aufsteigender Reihenfolge von t extrahiert und eine Suche durchgeführt wird. Wenn Sie schließlich den kleinsten Wert in T [n] herausnehmen, stellt dies die minimale Zeit dar, um Station n zu erreichen.
Dann ist der durchgeschriebene Code wie folgt.
from heapq import *
N, M, S = map(int, input().split())
T = [[10**18 for _ in range(2451)] for _ in range(N)]
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
que = [(0, 0, S)]
while que:
(currentT, n, coins) = heappop(que)
for m, cost, t in act[n]:
#Wenn "zu dem Betrag, den Sie bezahlen können" "Mindestzeit T"[Ziel][Besitzgeld]Aktualisieren Sie den Wert, wenn Sie ihn aktualisieren können, und fügen Sie den Status der Warteschlange hinzu.
#Wenn das Ergebnis des Austauschs 2450 überschreitet, behandeln Sie es als 2450 und es gibt kein Problem.
if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
T[m][min(2450, coins - cost)] = currentT + t
heappush(que, (currentT + t, m, min(2450, coins - cost)))
for i in range(1, N):
print(min(T[i]))
Es scheint, dass es sich um einen Algorithmus handelt, der als Dyxtra-Methode bezeichnet wird. Ich hatte das Gefühl, dass es ein schwieriges Problem für Frage E war, aber ich war überrascht, dass der Algorithmus für den letzten Suchteil extrem einfach zu schreiben war.
Das ist alles für diesen Artikel.
Recommended Posts