[PYTHON] Yukicoder-Wettbewerb 248 Teilnehmerrekord

Yukicoder-Wettbewerb 248 Teilnehmerrekord

A 1052 Electronic Device X

Durchbruch in 29 Minuten. Ich habe es endlich herausgefunden, als ich K = 1 bis 8 für N = 10,11 manuell berechnet habe (lacht). Wenn N gerade ist, ist es gerade, wenn K ungerade ist und wenn K gerade ist. Da nur ungerade Zahlen verfügbar sind, ist das Maximum N / 2. Wenn N ungerade ist, sind sowohl gerade als auch ungerade Zahlen verfügbar, sodass das Maximum N ist.

N, K = map(int, input().split())

if N % 2 == 0:
    print(min(K + 1, N // 2))
else:
    print(min(K + 1, N))

B 1053 Gaming Stick

Ich konnte nicht durchbrechen. Nachdem ich bis zu 2 WAs aktiviert hatte, fragte ich mich, ob es ein anderes Muster gab, das die Bedingungen erfüllen konnte, während ich es nicht konnte, wenn es überhaupt eines der drei gab. (Lacht) Es gibt zwei Muster, die die Bedingungen erfüllen können.

1. Die Farben werden nicht vom Anfang getrennt (0 mal)
2. Es gibt nur einen, der in zwei Teile geteilt ist, nämlich den Anfang und das Ende (einmal).

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)

C 1054 Union add query

Ich konnte nicht durchbrechen. Ich dachte, es wäre möglich, sie alle wie ABC138D --Ki zusammenzufügen, aber es ist unmöglich, sie in der verbleibenden Zeit zu implementieren. damit…….

Nachtrag: Der Union Find-Baum wurde wie beschrieben geändert und implementiert. Bei der Vereinigung wurde angegeben, dass der Wert des übergeordneten Elements vom Wert des übergeordneten Elements abgezogen wurde, das dem Unternehmen beitritt. Ich war besorgt darüber, wie ich die Anzahl der Personen erhöhen könnte, aber ich war zu dumm. Die Erklärung besagte, dass es in Ordnung ist, die Routenkomprimierung zu entfernen, aber Python ist langsam und ich dachte nicht, dass es zu schwierig ist, die Routenkomprimierung zu verlassen Ich habe es verlassen und implementiert. Ich habe AC gemacht, aber es war eine kurze Zeit, also denke ich, dass es die richtige Antwort war.

Obwohl es sich um eine Änderung handelt, wird es jetzt übergeben, um nicht nur die übergeordneten Informationen, sondern auch die Gesamtwertinformationen zu finden. Und find gibt nicht nur die übergeordnete Nummer, sondern auch den Gesamtwert des übergeordneten Elements auf dem Weg zum übergeordneten Element zurück. Wenn Sie die Route komprimieren, müssen Sie die Summe in der Mitte zu Ihrer eigenen Summe addieren. Zum Zeitpunkt der Vereinigung, wie oben erwähnt, subtrahieren Sie die Summe der übergeordneten Werte von der Summe der übergeordneten Werte unter dem Dach, um sie jeweils zu versetzen. Der Wert eines Knotens ist die Summe der Werte dieses Knotens und des Werts seines übergeordneten Knotens (aufgrund des Effekts der Pfadkomprimierung).

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))