Ich habe endlich etwas Zeit, also habe ich versucht, virtuell an PAST teilzunehmen. Das Ergebnis war 64 Punkte, also mittelschwer (60-79 Punkte). Im Gegensatz zum üblichen mathematischen und inspirierenden Spiel von AtCoder ist die Implementierung etwas Es gab viele Probleme, die auf subtile Weise problematisch zu sein schienen, und ich hatte das Gefühl, dass die Haarfarbe etwas anders war.
Brechen Sie in dreieinhalb Minuten durch. Überprüfen Sie, ob es sich nur um eine Zahl handelt. Wenn dies in Ordnung ist, konvertieren Sie sie in int und geben Sie sie doppelt aus.
S = input()
for i in range(3):
if S[i] not in '0123456789':
print('error')
exit()
print(int(S) * 2)
Durchbruch in 7 Minuten. Vergleichen Sie einfach mit dem vorherigen Wert und der Ausgabe.
N = int(input())
A = [int(input()) for _ in range(N)]
prev = A[0]
for i in range(1, N):
if A[i] == prev:
print('stay')
elif A[i] < prev:
print('down %d' % (prev - A[i]))
elif A[i] > prev:
print('up %d' % (A[i] - prev))
prev = A[i]
Brechen Sie in 2 Minuten durch. Sortieren Sie einfach in absteigender Reihenfolge und geben Sie den dritten Wert von vorne aus.
ABCDEF = list(map(int, input().split()))
ABCDEF.sort(reverse=True)
print(ABCDEF[2])
Brechen Sie in 11 Minuten durch. Zählen Sie einfach die Anzahl der Auftritte im Wörterbuch, identifizieren Sie 0 und 2 Dinge und geben Sie sie aus.
N = int(input())
A = [int(input()) for _ in range(N)]
t = set(A)
if len(t) == N:
print('Correct')
exit()
d = {}
for i in range(N):
if A[i] in d:
d[A[i]] += 1
else:
d[A[i]] = 1
for i in range(1, N + 1):
if i not in d:
x = i
elif d[i] == 2:
y = i
print(y, x)
Durchbruch in 24 Minuten. Die Implementierung von Follow Follow hat auch die Benutzer hinzugefügt, die dem Follow folgen, das während der Verarbeitung zugenommen hat, und es hat einige Zeit gedauert, bis Eingabebeispiel 1 nicht bestanden wurde. Eingabebeispiel 1 hat es abgefangen. Ich denke, es hätte mehr Zeit gedauert, wenn Sie es nicht getan hätten.
N, Q = map(int, input().split())
t = [['N'] * N for _ in range(N)]
for _ in range(Q):
S = input()
if S[0] == '1':
_, a, b = map(int, S.split())
t[a - 1][b - 1] = 'Y'
elif S[0] == '2':
_, a = map(int, S.split())
for i in range(N):
if t[i][a - 1] == 'Y':
t[a - 1][i] = 'Y'
elif S[0] == '3':
_, a = map(int, S.split())
for i in [i for i in range(N) if t[a - 1][i] == 'Y']:
for j in range(N):
if t[i][j] == 'Y' and j != a - 1:
t[a - 1][j] = 'Y'
for i in range(N):
print(''.join(t[i]))
past201912F - DoubleCamelCase Sort
Brechen Sie in 7 Minuten durch. Es gibt nichts besonders Schwieriges. Schneiden Sie es einfach in Worte, sortieren Sie sie, ignorieren Sie die Groß- und Kleinschreibung und kombinieren Sie sie.
S = input()
t = []
start = -1
for i in range(len(S)):
if S[i].isupper():
if start == -1:
start = i
else:
t.append(S[start:i+1])
start = -1
t.sort(key=str.lower)
print(''.join(t))
Es brach in 20 Minuten durch. Ich dachte, ich wüsste es zuerst nicht, aber wenn ich genau hinschaute, konnte ich Round-Robin machen, weil N ≤ 10. Es war nicht besonders schwierig.
N = int(input())
a = [list(map(int, input().split())) for _ in range(N - 1)]
result = -float('inf')
t = [0] * N
for _ in range(3 ** N):
s = 0
for i in range(N):
for j in range(i + 1, N):
if t[i] == t[j]:
s += a[i][j - i - 1]
result = max(result, s)
for i in range(N):
if t[i] < 2:
t[i] += 1
break
t[i] = 0
print(result)
Es bricht in 44 Minuten und einer halben durch. Es ist unvermeidlich, dass TLE aufgrund der Einschränkungen sowohl festgelegte Verkäufe als auch alle Arten von Verkäufen im Array widerspiegelt. Daher habe ich für jede Variable eine kumulative Variable erstellt und diese mit einer Richtlinie zum Abgleichen von Tsuji übergeben. Es hat lange gedauert, bis ich bemerkte, dass das odd_min- = a durchgesickert war.
N = int(input())
C = list(map(int, input().split()))
Q = int(input())
all_min = min(C)
odd_min = min(C[::2])
all_sale = 0
odd_sale = 0
ind_sale = 0
for _ in range(Q):
S = input()
if S[0] == '1':
_, x, a = map(int, S.split())
t = C[x - 1] - all_sale - a
if x % 2 == 1:
t -= odd_sale
if t >= 0:
ind_sale += a
C[x - 1] -= a
all_min = min(all_min, t)
if x % 2 == 1:
odd_min = min(odd_min, t)
elif S[0] == '2':
_, a = map(int, S.split())
if odd_min >= a:
odd_sale += a
odd_min -= a
all_min = min(odd_min, all_min)
elif S[0] == '3':
_, a = map(int, S.split())
if all_min >= a:
all_sale += a
all_min -= a
odd_min -= a
print(all_sale * N + odd_sale * ((N + 1) // 2) + ind_sale)
Es bricht in 14 Minuten durch. Es ist DP, also nicht besonders schwierig. Konvertieren Sie einfach Y in 1 und N in 0, was als Bit jeder Ziffer angesehen wird, und dann DP.
N, M = map(int, input().split())
def conv(S):
result = 0
for c in S:
result *= 2
if c == 'Y':
result += 1
return result
dp = [-1] * 2001
dp[0] = 0
for _ in range(M):
S, C = input().split()
S = conv(S)
C = int(C)
for i in range(2000, -1, -1):
if dp[i] == -1:
continue
if dp[i | S] == -1 or dp[i | S] > dp[i] + C:
dp[i | S] = dp[i] + C
print(dp[(1 << N) - 1])
Ich konnte nicht durchbrechen. Finden Sie mit DP die billigste Route von links unten nach rechts unten, schreiben Sie die zurückverfolgte Stelle neu, um 0 zu kosten, finden Sie mit DP die billigste Route von rechts unten nach rechts oben und die Kosten für jede Ich habe versucht, eine Implementierung zu erstellen, die zusammenfasst, aber ungefähr die Hälfte von WA.
Nachtrag: Nach der Erklärung gelöst.
from heapq import heappop, heappush
INF = float('inf')
def cost_from(H, W, A, y0, x0):
dp = [[INF] * W for _ in range(H)]
dp[y0][x0] = 0
q = [(0, y0, x0)]
while q:
c, y, x = heappop(q)
t = dp[y][x]
if t != c:
continue
if y - 1 >= 0:
u = t + A[y - 1][x]
if dp[y - 1][x] > u:
dp[y - 1][x] = u
heappush(q, (u, y - 1, x))
if y + 1 < H:
u = t + A[y + 1][x]
if dp[y + 1][x] > u:
dp[y + 1][x] = t + A[y + 1][x]
heappush(q, (u, y + 1, x))
if x - 1 >= 0:
u = t + A[y][x - 1]
if dp[y][x - 1] > u:
dp[y][x - 1] = u
heappush(q, (u, y, x - 1))
if x + 1 < W:
u = t + A[y][x + 1]
if dp[y][x + 1] > u:
dp[y][x + 1] = u
heappush(q, (u, y, x + 1))
return dp
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
result = INF
cost1 = cost_from(H, W, A, H - 1, 0)
cost2 = cost_from(H, W, A, H - 1, W - 1)
cost3 = cost_from(H, W, A, 0, W - 1)
for i in range(H):
for j in range(W):
t = cost1[i][j] + cost2[i][j] + cost3[i][j] - 2 * A[i][j]
if t < result:
result = t
print(result)
Ich konnte nicht durchbrechen. Natürlich konnte ich eine naive Implementierung schreiben, aber ich konnte mir keine Möglichkeit vorstellen, den Rechenaufwand zu reduzieren.
Nachtrag: Ich habe die Oiler Tour und AC gelernt.
N = int(input())
root = -1
children = [[] for _ in range(N + 1)]
left = [0] * (N + 1)
right = [0] * (N + 1)
for i in range(1, N + 1):
p = int(input())
if p == -1:
root = i
else:
children[p].append(i)
i = 0
s = [root]
while s:
n = s.pop()
if n > 0:
left[n] = i
i += 1
s.append(-n)
for c in children[n]:
s.append(c)
else:
right[-n] = i
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, input().split())
if left[b] < left[a] < right[b]:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
Ich habe auch versucht, es durch Verdoppeln zu lösen.
from math import log
from collections import deque
from sys import stdin
readline = stdin.readline
N = int(readline())
root = -1
children = [[] for _ in range(N + 1)]
parent = [[-1] * (N + 1) for _ in range(18)]
for i in range(1, N + 1):
p = int(readline())
parent[0][i] = p
if p == -1:
root = i
else:
children[p].append(i)
for i in range(1, 18):
parenti1 = parent[i - 1]
parenti = parent[i]
for j in range(1, N + 1):
t = parenti1[j]
if t == -1:
parenti[j] = -1
else:
parenti[j] = parenti1[t]
depth = [-1] * (N + 1)
q = deque([(root, 0)])
while q:
n, d = q.pop()
depth[n] = d
for c in children[n]:
q.append((c, d + 1))
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, readline().split())
if depth[a] <= depth[b]:
result.append('No')
continue
while depth[a] != depth[b]:
t = int(log(depth[a] - depth[b], 2))
a = parent[t][a]
if a == b:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
Recommended Posts