Percer en 29 minutes. J'ai finalement découvert quand j'ai calculé manuellement K = 1 à 8 pour N = 10,11 (rires). Quand N est pair, c'est pair quand K est impair, et quand K est pair. Puisque seuls les nombres impairs sont disponibles, le maximum est N / 2. Lorsque N est impair, les nombres pairs et impairs sont disponibles, donc le maximum est N.
N, K = map(int, input().split())
if N % 2 == 0:
print(min(K + 1, N // 2))
else:
print(min(K + 1, N))
Je n'ai pas pu percer. Après avoir contrôlé jusqu'à 2 WA, je me demandais s'il y avait un autre modèle qui pourrait remplir les conditions, alors que je ne pouvais pas le faire s'il y avait même une des 3 divisions ( (Rires) Il y a deux modèles qui peuvent remplir les conditions.
N = int(input())
A = list(map(int, input().split()))
d = {}
prev = -1
for a in A:
if prev != a:
d.setdefault(a, 0)
d[a] += 1
prev = a
if all(v == 1 for v in d.values()):
print(0)
exit()
if any(v >= 3 for v in d.values()):
print(-1)
exit()
if len([v for v in d.values() if v == 2]) == 1 and A[0] == A[-1]:
print(1)
else:
print(-1)
Je n'ai pas pu percer. Je pensais qu'il serait possible de les ajouter tous ensemble comme ABC138D --Ki, mais il est impossible de les implémenter dans le temps restant. alors…….
Addendum: L'arbre Union Find a été modifié et implémenté comme décrit. Lors de l'union, il a été dit que la valeur du parent était soustraite de la valeur du parent rejoignant le parapluie. Je m'inquiétais de savoir comment augmenter le nombre de personnes, mais j'étais trop stupide. L'explication disait qu'il était correct de supprimer la compression de route, mais Python est lent et je ne pensais pas qu'il était trop difficile de quitter la compression de route, donc Je l'ai laissé et mis en œuvre, j'ai fait AC, mais c'était peu de temps, donc je pense que c'était la bonne réponse.
Bien qu'il s'agisse d'une modification, elle est maintenant transmise pour rechercher non seulement les informations sur le parent, mais également les informations sur la valeur totale. Et find renvoie non seulement le numéro du parent, mais également la valeur totale du parent sur le chemin du parent. Lors de la compression de l'itinéraire, il est nécessaire d'ajouter le total du milieu à votre propre total. Au moment de l'union, comme mentionné ci-dessus, soustrayez le total des valeurs parent du total des valeurs parent sous le parapluie pour compenser chacune. La valeur d'un nœud est la somme des valeurs de ce nœud et de la valeur de son parent (en raison de l'effet de la compression de chemin).
from sys import setrecursionlimit
from sys import stdin
def find(parent, amount, i):
t = parent[i]
if t < 0:
return i, 0
t, a = find(parent, amount, t)
parent[i] = t
amount[i] += a
return t, amount[i]
def unite(parent, amount, i, j):
i, _ = find(parent, amount, i)
j, _ = find(parent, amount, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
amount[i] -= amount[j]
setrecursionlimit(10 ** 6)
readline = stdin.readline
N, Q = map(int, readline().split())
parent = [-1] * (N + 1)
amount = [0] * (N + 1)
result = []
for _ in range(Q):
T, A, B = map(int, readline().split())
if T == 1:
unite(parent, amount, A, B)
elif T == 2:
j, _ = find(parent, amount, A)
amount[j] += B
elif T == 3:
j, a = find(parent, amount, A)
result.append(amount[j] + a)
print('\n'.join(str(v) for v in result))
Recommended Posts