Tout ce que vous avez à faire est de définir la position de l'une des personnes associées aux informations sur 0 et de vérifier s'il y a une incohérence dans DFS. Notez qu'il ne s'agit pas toujours d'un groupe.
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')
Recherche d'union pondérée Peut être résolue avec un arbre.
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')
Quel que soit le nombre d'opérations que vous effectuez, le total ne change pas, donc la seule réponse possible est une fraction du total. Après cela, vous pouvez en faire un multiple de cette fraction avec K opérations, mais trier le reste divisé par cette fraction. Si vous le faites, celui qui doit être soustrait vient à l'avant, et celui qui doit être ajouté vient à l'arrière, donc si vous comptez dans l'ordre de l'avant et de l'arrière, vous pouvez calculer le nombre minimum d'opérations requises.
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
Au moins ceil (max (h) / b) ou moins, mais il est trop tard pour calculer la différence entre A et B dans l'ordre de celui avec la force physique la plus élevée (confirmé à l'aide de heapq). Quand on m'a dit cela, c'était une merveille que je puisse le résoudre en un instant, mais je ne pouvais pas du tout y penser.
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)
Je pensais que sac à dos = DP et je pensais dans cette direction, mais je n'y pense pas du tout. En premier lieu, N ≤ 100 et w1 ≤ wi ≤ w1 + 3, donc même si je recherche tout (100/4 + 1) 4 </ strong> Il devait être sup> ≒ 4,6 × 10 5 </ sup>, et il était normal de faire une recherche complète.
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)
Bref, AGC, ACG, GAC, A? GC, AG? C sont inutiles, il vous suffit donc de ne garder que les 3 derniers caractères au maximum.4 3 </ sup> -3 Vous n'avez qu'à tenir 3 types, à peu près à partir de là Puisqu'il est dérivé quatre fois, le montant du calcul était d'environ 250 × 100 = 2,5 × 10 4 </ sup>, ce qui était dans la plage de marge. C'est pourquoi il a été résolu par DP.
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)
Je pensais que ce serait facile s'il n'y avait pas de valeur absolue. Ensuite, je me suis demandé si je devais trouver les valeurs maximales de plus et moins respectivement. Si tel est le cas, 2 fois 3 </ sup>, s'il n'y a pas de valeur absolue Il n'y a pas de problème en termes de quantité de calcul car c'est la même chose que faire, je n'étais pas sûr que ce serait la valeur maximale, mais il semble que c'était une façon de penser parce que c'était AC.
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