Suchen Sie den Abstand von Scheitelpunkt 1 für alle Scheitelpunkte in der Suche und geben Sie 0 für gerade Entfernungen und 1 für ungerade Entfernungen aus.
N = int(input())
link = [[] for _ in range(N)]
for _ in range(N - 1):
u, v, w = map(int, input().split())
link[u - 1].append((v - 1, w))
link[v - 1].append((u - 1, w))
d = [-1] * N
d[0] = 0
q = [0]
while q:
p = q.pop()
for n, w in link[p]:
if d[n] == -1:
d[n] = d[p] + w
q.append(n)
for i in d:
print(i % 2)
"A X i </ sub> </ sub> + A Y i </ sub> </ sub> + Z i </ sub> ist gerade "." Bedeutet, dass wenn Sie ein A kennen, Sie das andere kennen. Wenn "A X </ sub> + A Y </ sub> + Z i </ "sub> ist eine gerade Zahl." Und "A X </ sub> + A Z </ sub> + Z j </ sub> ist eine gerade Zahl." Wenn Sie eines der A kennen, kennen Sie die beiden anderen.
Dann stellt sich die Frage, wie viele Gruppen von A keine Beziehung zueinander haben, und sie kann auf das Problem reduziert werden, die Anzahl der Gruppen mit Union Find zu zählen.
from sys import setrecursionlimit
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
setrecursionlimit(10 ** 5)
N, M = map(int, input().split())
parent = [-1] * N
for _ in range(M):
X, Y, Z = map(int, input().split())
unite(parent, X - 1, Y - 1)
print(len([x for x in parent if x < 0]))
Gehen Sie einfach und teleportieren Sie sich in der richtigen Reihenfolge und besuchen Sie diejenige mit der geringsten Zunahme an Müdigkeit. Einfach.
N, A, B = map(int, input().split())
X = list(map(int, input().split()))
result = 0
for i in range(N - 1):
result += min(A * (X[i + 1] - X[i]), B)
print(result)
Für alle Zahlen außer -1 und 1 addieren wir nur die magische Kraft, die erforderlich ist, um sie auf 1 zu ändern. In einigen Fällen ist jedoch weniger magische Kraft erforderlich, um eine andere Zahl zu durchlaufen, als um sie direkt auf 1 zu ändern. , Finden Sie die minimale magische Kraft, um jede Zahl nach der Worshall Floyd-Methode auf 1 zu ändern.
def warshall_floyd(n, d):
for i in range(n):
for j in range(n):
for k in range(n):
d[j][k] = min(d[j][k], d[j][i] + d[i][k])
H, W = map(int, input().split())
N = 10
d = [None] * N
for i in range(N):
d[i] = list(map(int, input().split()))
warshall_floyd(N, d)
m = [d[i][1] for i in range(N)]
result = 0
for _ in range(H):
for i in map(int, input().split()):
if i == -1:
continue
result += m[i]
print(result)
Es kann nur das Schwert mit dem maximalen Schaden geschwungen werden. Es ist kein Schwert mit weniger Schaden als diesem schwingenden Schaden erforderlich. Wenn der Schaden in der Reihenfolge desjenigen mit dem höchsten Schaden geworfen wird und der Schaden H überschreitet, bevor der maximal zu schwingende Schaden erreicht wird. Es muss nicht geschüttelt werden. Wenn nicht genug geschüttelt wird, schütteln Sie so viel. Wenn sich das Schüttelschwert im Wurfschwert befindet und Sie es nach dem Schütteln werfen, ist die Häufigkeit gleich, sodass es kein Problem gibt.
N, H = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(N)))
a_max = max(a) #Maximaler Schaden durch Schütteln
b = [x for x in b if x > a_max] #Entfernen Sie ein Schwert, dessen Wurfschaden geringer ist als der maximale Schaden beim Schwingen, da es keinen Sinn macht, es zu werfen
b.sort(reverse=True)
result = 0
#Wirf Schwerter in absteigender Reihenfolge des Schadens. Wenn du sie besiegen kannst, bevor das Schwert ausgeht, ist es das.
for x in b:
result += 1
H -= x
if H <= 0:
break
#Wenn Sie es nicht einfach durch Werfen besiegen können, schwingen Sie das Schwert mit dem maximalen Schaden
#Befindet sich das Schwert mit dem maximalen Schwungschaden im zu werfenden Schwert, bedeutet dies, dass das Schwert nach dem Schwingen so weit wie nötig geworfen wurde.
if H > 0:
result += (H + (a_max - 1)) // a_max
print(result)
Recommended Posts