Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.
Die Lösung, die ich hier schreibe, wurde geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansah. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.
A - Duplex Printing
Die Frage ist, wie viele Blätter Papier für den doppelseitigen Druck von N Seiten benötigt werden.
Durch 2 teilen und aufrunden.
n = int(input())
print((n+1)//2)
B - Bingo Die Frage ist zu beantworten, ob die angegebenen Zahlen und Bingokarten ausgerichtet sind.
Es war umständlich, das zweidimensionale Array zu durchsuchen, um das Element zu finden, daher habe ich die Operation des Ersetzens durch "np.where" mit "numpy" verwendet. Ich habe auch das Vorhandensein von Bingo überprüft, indem ich "np.sum ()" entlang der vertikalen und horizontalen Achse verwendet habe.
Beachten Sie, dass pypy3 numpy nicht lesen kann.
import numpy as np
S = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
S = np.where(S==int(input()), 0, S)
HBingo = min(np.sum(S, axis=0)) == 0
WBingo = min(np.sum(S, axis=1)) == 0
SBingo = S[2][0] == 0 and S[1][1] == 0 and S[0][2] == 0
BSBingo = S[0][0] == 0 and S[1][1] == 0 and S[2][2] == 0
if HBingo or WBingo or SBingo or BSBingo:
print('Yes')
exit()
print('No')
Es scheint jedoch viel schneller zu sein, das Array gehorsam zu durchsuchen, ohne numpy zu verwenden.
C - Guess The Number
Es ist ein Problem, die Mindestanzahl zurückzugeben, die die Bedingungen für die Anzahl der empfangenen Ziffern und die Anzahl erfüllt.
Erstellen Sie zunächst jede Ziffer mit "-1" als Ausgangszustand. Jedes Mal, wenn eine Eingabe von ihr empfangen wird, wird sie neu geschrieben, wenn entweder "der neu zu schreibende Wert ist -1" oder "die neu zu schreibende Zahl steht nicht in Konflikt" erfüllt ist. Wenn ein Konflikt auftritt, geben Sie -1 aus und beenden Sie das Programm.
Konvertieren Sie abschließend die Ziffer (-1), die nicht neu geschrieben wurde, in den Mindestwert, und Sie sind fertig. Konvertieren Sie in 1, wenn es die erste Ziffer von links ist (beachten Sie, dass 0 zulässig ist, wenn N = 1 ist), und in 0, wenn es danach ist.
Beachten Sie, dass die erste Ziffer nicht auf 0 geändert werden kann, wenn $ N \ geq2 $ (ein Verlust).
N, M = map(int, input().split())
ans = [-1] * N
for _ in range(M):
i, n = map(int, input().split())
if (ans[i-1] == -1 or ans[i-1] == n) and not(N > 1 and i == 1 and n == 0):
ans[i-1] = n
else:
print(-1)
exit()
ans = [n if n != -1 else 0 for n in ans]
if ans[0] == 0 and N > 1:
ans[0] = 1
print(*ans, sep='')
D - Friend Suggestions
Angesichts des Status von SNS ist es eine Frage, wie viele Beziehungen "Freunde von Freunden" und "weder Freunde noch Feinde" sind.
Ich wusste nicht, wie ich herausfinden sollte, ob sie verbunden waren, also gab ich auf.
Ich habe den Kommentar gesehen. Die Anzahl der Freundeskandidaten ist die Anzahl, die durch Subtrahieren von "Anzahl Ihrer Freunde", "Anzahl Ihrer Freunde (1)" und "Anzahl der Personen, die im Cluster blockieren" von "Anzahl der Personen im Cluster, zu denen Sie gehören" erhalten wird. Wird sein.
Daher wird als Array das Array "ClusterI", in dem "der Cluster, zu dem jedes Element gehört", das Array "ClusterN", in dem "die Anzahl der Personen in jedem Cluster" gespeichert ist, und die "Anzahl der Personen, die mit Freunden blockieren" gespeichert, die später gezeichnet werden sollen. Erstellen Sie drei Arrays von out.
clusterI speichert den niedrigsten Index im Cluster. Das ist das Problem. Der folgende Code ändert den Vorgang des Umschreibens des Index mit for.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def unite(x, y):
CX = clusterI[x]
CY = clusterI[y]
if CX != CY:
if CX < CY:
CX, CY = CY, CX
clusterN[CX] += clusterN[CY]
for i in range(n):
if clusterI[i] == CY:
clusterI[i] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if clusterI[a-1] == clusterI[b-1]:
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)
Das ist TLE.
Ich habe es mit einer rekursiven Funktion umgeschrieben und dabei auf den Code anderer Leute verwiesen. Ich ging daran vorbei. Die große Herausforderung besteht darin, dass Sie nicht über das Wissen über Exploration verfügen.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def find(x):
if clusterI[x] != x:
minI = find(clusterI[x])
clusterI[x] = minI
return minI
else:
return x
def unite(x, y):
CX = find(x)
CY = find(y)
if CX != CY:
if CX > CY:
CX, CY = CY, CX
x, y = y, x
clusterN[CX] += clusterN[CY]
clusterI[CY] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if find(a-1) == find(b-1):
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[find(i)] - 1 for i in range(n)]
print(*out)
E - Simple String Queries
Es ist ein Problem, die Anzahl der Zeichentypen zu überprüfen, indem der Vorgang des Konvertierens der Zeichenfolge gemäß der Eingabe wiederholt wird.
Der folgende Code ist der, den ich wie gewohnt gemacht habe.
import collections
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
Q1, Q2, Q3 = input().split()
if Q1 == '1':
S[int(Q2)-1] = ord(Q3)
else:
print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))
TLE kam heraus.
Ich habe mir den Kommentar angesehen.
Erstellen Sie ein Array mit 26 Elementen mit Informationen zu A bis Z. Die Position, an der das Zeichen angezeigt wird, wird im Element gespeichert. Überprüfen Sie beim Zählen, ob 26 Zeichen vorhanden sind, um festzustellen, ob sie innerhalb des angegebenen Bereichs liegen.
Das Folgende ist die Implementierung davon, wie es ist.
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
li[ordN(Q3)].append(Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
if [True for n in li[j] if Q2 <= n and n <= Q3]:
count += 1
print(count)
Bei dieser Rate wird TLE weiterhin angezeigt. Schreiben Sie unter Bezugnahme auf den Code anderer Personen neu. Hält die Erscheinungsposition von Zeichen in einem sortierten Zustand. Zusätzlich werden Ersatz und Positionsprüfung durch Dichotomie durchgeführt. Die Bibliothek "Halbierung" wird für die Dichotomie verwendet.
Die folgenden zwei Funktionen werden verwendet.
bisect.bisect_left(list, x)
a = [1, 2, 4, 6, 10]
print(bisect.bisect_left(a, 4)) # 3
Gibt die Position zurück, an der das zweite Argument in die Liste des ersten Arguments eingegeben werden kann, ohne die Sortierreihenfolge zu unterbrechen.
bisect.insort(list, x)
a = [1, 2, 4, 6, 10]
bisect.insort(a, 4)
print(a)# [1, 2, 4, 4, 6, 10]
Fügt sich in die Liste des ersten Arguments ein, ohne die Sortierreihenfolge zu unterbrechen.
Der folgende Code wurde damit umgeschrieben.
import bisect
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
li[ordN(S[Q2])].pop(I)
bisect.insort(li[ordN(Q3)], Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
I = bisect.bisect_left(li[j], Q2)
if I < len(li[j]) and li[j][I] <= Q3:
count += 1
print(count)
Ich ging daran vorbei.
Das ist alles für diesen Artikel.
Recommended Posts