Sie müssen lediglich die Position einer der mit den Informationen verknüpften Personen auf 0 setzen und prüfen, ob die DFS inkonsistent ist. Beachten Sie, dass es sich nicht immer um eine Gruppe handelt.
from sys import stdin
N, M = map(int, stdin.readline().split())
links = [[] for _ in range(N + 1)]
for _ in range(M):
L, R, D = map(int, stdin.readline().split())
links[L].append((R, D))
links[R].append((L, -D))
t = [None] * (N + 1)
for i in range(1, N + 1):
if t[i] is not None:
continue
t[i] = 0
s = [i]
while s:
j = s.pop()
for k, l in links[j]:
if t[k] is None:
t[k] = t[j] + l
s.append(k)
else:
if t[k] != t[j] + l:
print('No')
exit()
print('Yes')
Weighted Union Find Kann mit einem Baum gelöst werden.
from sys import setrecursionlimit, stdin
def find(parent, diff_weight, i):
t = parent[i]
if t < 0:
return i
t = find(parent, diff_weight, t)
diff_weight[i] += diff_weight[parent[i]]
parent[i] = t
return t
def weight(parent, diff_weight, i):
find(parent, diff_weight, i)
return diff_weight[i]
def unite(parent, diff_weight, i, j, d):
d -= weight(parent, diff_weight, j)
d += weight(parent, diff_weight, i)
i = find(parent, diff_weight, i)
j = find(parent, diff_weight, j)
if i == j:
return
diff_weight[j] = d
parent[i] += parent[j]
parent[j] = i
setrecursionlimit(10 ** 6)
N, M = map(int, stdin.readline().split())
LRD = [tuple(map(int, stdin.readline().split())) for _ in range(M)]
parent = [-1] * (N + 1)
diff_weight = [0] * (N + 1)
for L, R, D in LRD:
i = find(parent, diff_weight, L)
j = find(parent, diff_weight, R)
if i != j:
unite(parent, diff_weight, L, R, D)
else:
if weight(parent, diff_weight, L) + D != weight(parent, diff_weight, R):
print('No')
exit()
print('Yes')
Unabhängig davon, wie viele Operationen Sie ausführen, ändert sich die Summe nicht. Die einzige mögliche Antwort ist ein Bruchteil der Summe. Danach können Sie mit K-Operationen ein Vielfaches dieser Fraktion erstellen, aber den Rest durch diesen Bruch dividieren. Wenn Sie dies tun, wird derjenige, der subtrahiert werden soll, nach vorne und derjenige, der hinzugefügt werden soll, nach hinten kommen. Wenn Sie also in der Reihenfolge von vorne und hinten zählen, können Sie die erforderliche Mindestanzahl von Operationen berechnen.
def make_divisor_list(n):
result = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
result.append(i)
result.append(n // i)
return result
def calc_min_ops(r, d):
i, j = 0, len(r)
while i < j and r[i] == 0:
i += 1
i -= 1
a, b = 0, 0
while j - i != 1:
if a <= b:
i += 1
a += r[i]
else:
j -= 1
b += d - r[j]
return a
N, K, *A = map(int, open(0).read().split())
c = sum(A)
divisors = make_divisor_list(c)
divisors.sort(reverse=True)
r = [None] * N
for d in divisors:
for i in range(N):
r[i] = A[i] % d
r.sort()
if calc_min_ops(r, d) <= K:
print(d)
break
Es kann mindestens Ceil (max (h) / b) oder weniger sein, aber es ist zu spät, um die Differenz zwischen A und B in der Reihenfolge derjenigen mit der höchsten physischen Stärke zu berechnen (bestätigt mit heapq). Als mir das gesagt wurde, war es ein Wunder, dass ich es sofort lösen konnte, aber ich konnte überhaupt nicht daran denken.
from bisect import bisect_right
N, A, B, *h = map(int, open(0).read().split())
h.sort()
d = A - B
ng = (h[-1] + (A - 1)) // A - 1
ok = (h[-1] + (B - 1)) // B
while ok - ng > 1:
m = (ok + ng) // 2
b = B * m
if m >= sum((h[i] - b + (d - 1)) // d for i in range(bisect_right(h, b), N)):
ok = m
else:
ng = m
print(ok)
Ich dachte, dass Rucksack = DP und dachte in diese Richtung, aber ich kann überhaupt nicht daran denken. Erstens sind N ≤ 100 und w1 ≤ wi ≤ w1 + 3, also selbst wenn ich alle (100/4 + 1) 4 </ strong> suche sup> ≒ 4,6 × 10 5 </ sup>, und es war in Ordnung, eine vollständige Suche durchzuführen.
from sys import stdin
from itertools import accumulate
readline = stdin.readline
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
w, v = map(int, input().split())
vs[w - w1].append(v)
for i in range(4):
vs[i].sort(reverse=True)
vs[i] = [0] + list(accumulate(vs[i]))
result = 0
for i in range(len(vs[0])):
a = W - w1 * i
if a < 0:
break
for j in range(len(vs[1])):
b = a - (w1 + 1) * j
if b < 0:
break
for k in range(len(vs[2])):
c = b - (w1 + 2) * k
if c < 0:
break
t = vs[0][i] + vs[1][j] + vs[2][k]
for l in range(len(vs[3])):
d = c - (w1 + 3) * l
if d < 0:
break
result = max(result, t + vs[3][l])
print(result)
Kurz gesagt, AGC, ACG, GAC, A? GC, AG? C sind nutzlos, so dass Sie höchstens die letzten 3 Zeichen behalten müssen. 4 3 </ sup> -3 Typen, ungefähr von dort Da es viermal abgeleitet wurde, betrug der Berechnungsbetrag ungefähr 250 × 100 = 2,5 × 10 4 </ sup>, was innerhalb des Randbereichs lag. Deshalb wurde es von DP gelöst.
def is_ok(s):
if s[1:] in ['AGC', 'ACG', 'GAC']:
return False
if s[0] == 'A' and s[2:] == 'GC':
return False
if s[:2] == 'AG' and s[3] == 'C':
return False
return True
m = 1000000007
N = int(input())
d = {}
for i in 'ACGT':
for j in 'ACGT':
for k in 'ACGT':
d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
del d[k]
for i in range(N - 3):
t = {}
for k in d:
for i in 'ACGT':
s = k + i
if is_ok(s):
t.setdefault(s[1:], 0)
t[s[1:]] += d[k]
t[s[1:]] %= m
d = t
print(sum(d.values()) % m)
Ich dachte, es wäre einfach, wenn es keinen absoluten Wert gäbe. Dann fragte ich mich, ob ich die Maximalwerte von Plus und Minus finden sollte. Wenn dies der Fall ist, 2 </ sup> 3 </ sup> Mal, wenn es keinen absoluten Wert gibt Es gibt kein Problem in Bezug auf den Umfang der Berechnung, da es das gleiche ist wie das Tun. Ich war mir nicht sicher, ob es der Maximalwert sein würde, aber es scheint, dass es eine Denkweise war, weil es AC war.
from itertools import product
from sys import stdin
readline = stdin.readline
N, M = map(int, readline().split())
xyz = [tuple(map(int, readline().split())) for _ in range(N)]
result = 0
for s in product([1, -1], repeat=3):
xyz.sort(reverse=True, key=lambda e: s[0] * e[0] + s[1] * e[1] + s[2] * e[2])
cx, cy, cz = 0, 0, 0
for x, y, z in xyz[:M]:
cx += x
cy += y
cz += z
result = max(result, abs(cx) + abs(cy) + abs(cz))
print(result)
Recommended Posts