Das Ergebnis war 76 Punkte, was mittelschwer war (60-79 Punkte). Beim letzten Mal war ich mit 64 Punkten kaum mittelschwer, aber diesmal war ich fortgeschritten, wenn ich eine weitere Frage löste.
Durchbruch in 3 Minuten. Wenn Sie Bx auf -x und xF auf x setzen, müssen Sie nur vorsichtig sein, wenn der Unterschied zwischen B1 und 1F nicht 1 ist.
S, T = input().split()
def f(s):
if s[0] == 'B':
return -int(s[1])
else:
return int(s[0]) - 1
print(abs(f(S) - f(T)))
Brechen Sie in dreieinhalb Minuten durch. Aggregieren Sie einfach und geben Sie am meisten aus.
S = input()
d ={}
for c in S:
d.setdefault(c, 0)
d[c] += 1
print(sorted(((d[k], k) for k in d), reverse=True)[0][1])
Brechen Sie in 12 Minuten durch. Schreiben Sie einfach gemäß der Problemstellung.
N = int(input())
S = [input() for _ in range(N)]
T = [list(l) for l in S]
for i in range(N - 2, -1, -1):
for j in range(2 * N - 1):
if T[i][j] == '.':
continue
if j - 1 >= 0:
if T[i + 1][j - 1] == 'X':
T[i][j] = 'X'
if T[i + 1][j] == 'X':
T[i][j] = 'X'
if j + 1 < 2 * N - 1:
if T[i + 1][j + 1] == 'X':
T[i][j] = 'X'
for l in T:
print(''.join(l))
Durchbruch in 11 Minuten. Da "." Ein beliebiges Zeichen ist, ist es ein regulärer Ausdruck, der übereinstimmt. Danach werden alle Muster generiert, aber Python ist itertools.product.
from itertools import product
from re import search
S = input()
cs = set(S)
cs.add('.')
result = 0
for i in range(1, 4):
for p in product(cs, repeat=i):
if search(''.join(p), S):
result += 1
print(result)
Brechen Sie in 8,5 Minuten durch. Ich denke, es gibt nichts Schwieriges, weil ich es einfach genau so schreibe, wie es in der Problemstellung steht.
N = int(input())
A = list(map(int, input().split()))
result = []
for i in range(N):
x = i
j = 1
x = A[x] - 1
while x != i:
x = A[x] - 1
j += 1
result.append(j)
print(*result)
In 7,5 Minuten durchbrechen. Erinnerte mich an ABC137D - Sommerurlaub. Nehmen Sie einfach die Aufgabe mit den höchsten Punkten aus der Rezeptwarteschlange und verdauen Sie sie wiederholt.
from heapq import heappush, heappop
N = int(input())
d = {}
for _ in range(N):
A, B = map(int, input().split())
d.setdefault(A, [])
d[A].append(B)
t = []
result = 0
for i in range(1, N + 1):
if i in d:
for b in d[i]:
heappush(t, -b)
result += -heappop(t)
print(result)
Durchbruch in 32 Minuten. Gelöst mit DP, das die minimalen Kosten von allen vorherigen Standorten zu allen nächsten Standorten sucht.
N, M = map(int, input().split())
A = [input() for _ in range(N)]
d = {}
for i in range(N):
for j in range(M):
d.setdefault(A[i][j], [])
d[A[i][j]].append((i, j))
for i in list(range(1, 10)) + ['S', 'G']:
if str(i) not in d:
print(-1)
exit()
dp = [[float('inf')] * M for _ in range(N)]
i, j = d['S'][0]
dp[i][j] = 0
current = 'S'
while current != 'G':
if current == 'S':
next = '1'
elif current == '9':
next = 'G'
else:
next = str(int(current) + 1)
for i, j in d[current]:
for ni, nj in d[next]:
dp[ni][nj] = min(dp[ni][nj], dp[i][j] + abs(ni - i) + abs(nj - j))
current = next
i, j = d['G'][0]
print(dp[i][j])
Brechen Sie in 23,5 Minuten durch. TLE ist unvermeidlich, wenn Sie gehorsam eine Zeichenfolge gemäß der Problemstellung erstellen. Deshalb habe ich die Liste der Zeichen- und Längenpaare verwaltet und gelöst.
from collections import deque
Q = int(input())
S = deque()
for _ in range(Q):
Query = input().split()
if Query[0] == '1':
C = Query[1]
X = int(Query[2])
S.append((C, X))
elif Query[0] == '2':
D = int(Query[1])
d = {}
while D != 0 and len(S) != 0:
C, X = S.popleft()
d.setdefault(C, 0)
if X >= D:
d[C] += D
if X != D:
S.appendleft((C, X - D))
D = 0
else:
d[C] += X
D -= X
print(sum(v * v for v in d.values()))
Durchbruch in 12 Minuten. Die Anzahl der Personen beträgt 2 N und N beträgt nur 16 oder weniger. Es ist also einfach, es gehorsam zu simulieren.
N = int(input())
A = list(map(int, input().split()))
result = [1] * (2 ** N)
t = [(i, A[i]) for i in range(2 ** N)]
while len(t) != 1:
nt = []
for i in range(0, len(t), 2):
ai, aj = t[i]
bi, bj = t[i + 1]
if aj > bj:
result[ai] += 1
nt.append(t[i])
else:
result[bi] += 1
nt.append(t[i + 1])
t = nt
result[t[0][0]] -= 1
for i in result:
print(i)
Durchbruch in 20 Minuten. Die Länge der letzten Zeichenkette S beträgt 1000 oder weniger, daher ist es in Ordnung, sie gehorsam zu simulieren. Wenn Sie die linke Klammer finden, suchen Sie nach der gepaarten rechten Klammer, und wenn sich eine Klammer darin befindet, fahren Sie fort Da wir es verarbeiten müssen, schreiben Sie den Prozess mit einer rekursiven Funktion und beenden Sie.
S = input()
def f(s):
i = s.find('(')
if i == -1:
return s
result = s[:i]
s = s[i:]
i = 1
n = 1
while n != 0:
if s[i] == '(':
n += 1
elif s[i] == ')':
n -= 1
i += 1
t = f(s[1:i - 1])
result += t + t[::-1]
result += f(s[i:])
return result
print(f(S))
Wenn Sie es gehorsam schreiben, ist es * O * (* N * 2 </ sup>) und es ist TLE. Reduzieren Sie daher den Rechenaufwand. Da es sich um eine gierige Methode handelt, die das linke Ende des Minimalwerts aus dem auswählbaren Bereich, dem Intervall-Minimalwert, nimmt Wird vom Segmentbaum berechnet und wird zu * O * ( N </ i> log N </ i>).
class SegmentTree():
_data = []
_offset = 0
_size = 0
def __init__(self, size):
_size = size
t = 1
while t < size:
t *= 2
self._offset = t - 1
self._data = [0] * (t * 2 - 1)
def update_all(self, iterable):
self._data[self._offset:self._offset+self._size] = iterable
for i in range(self._offset - 1, -1, -1):
self._data[i] = min(self._data[i * 2 + 1], self._data[i * 2 + 2])
def update(self, index, value):
i = self._offset + index
self._data[i] = value
while i >= 1:
i = (i - 1) // 2
self._data[i] = min(self._data[i * 2 + 1], self._data[i * 2 + 2])
def query(self, start, stop):
result = float('inf')
l = start + self._offset
r = stop + self._offset
while l < r:
if l & 1 == 0:
result = min(result, self._data[l])
if r & 1 == 0:
result = min(result, self._data[r - 1])
l = l // 2
r = (r - 1) // 2
return result
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
st = SegmentTree(N)
st.update_all(A)
result = []
i = 0
for k in range(K - 1, -1, -1):
m = st.query(i, N - k * D)
result.append(m)
while A[i] != m:
i += 1
i += D
print(*result)
Nachtrag: Ich habe versucht, es wie erläutert mit einer Prioritätswarteschlange zu lösen. Ich habe mich gefragt, was ich tun soll, wenn der bereits übergebene Wert in der Warteschlange verbleibt, aber ich frage mich, ob er verworfen werden sollte. Ist es …….
from heapq import heappush, heappop
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
result = []
q = []
i = 0
l = 0
for k in range(K - 1, -1, -1):
for j in range(l, N - k * D):
heappush(q, (A[j], j))
l = N - k * D
while True:
a, j = heappop(q)
if j >= i:
break
result.append(a)
i = j + D
print(*result)
Ich habe es auch mit Sparse Table gelöst. In diesem Problem ist SegmentTree * O * (* N * + (* N * / * D *) log N </ i>), während * O * ( > N </ i> log N </ i> + * N * / * D *), also ist es etwas langsam.
class SparseTable():
_data = None
_lookup = None
_f = None
def __init__(self, a):
data = []
lookup = []
f = min
b = 0
while (1 << b) <= len(a):
b += 1
for _ in range(b):
data.append([0] * (1 << b))
data[0][:len(a)] = a
for i in range(1, b):
j = 0
di = data[i]
di1 = data[i - 1]
while j + (1 << i) <= (1 << b):
di[j] = f(di1[j], di1[j + (1 << (i - 1))])
j += 1
lookup = [0] * (len(a) + 1)
for i in range(2, len(lookup)):
lookup[i] = lookup[i >> 1] + 1
self._data = data
self._lookup = lookup
self._f = f
def query(self, start, stop):
b = self._lookup[stop - start]
db = self._data[b]
return self._f(db[start], db[stop - (1 << b)])
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
st = SparseTable(A)
result = []
i = 0
for k in range(K - 1, -1, -1):
m = st.query(i, N - k * D)
result.append(m)
while A[i] != m:
i += 1
i += D
print(*result)
Ich kann nicht durchbrechen. Ich mache TLE, aber ich kann nicht einmal eine naive Implementierung schreiben, die die richtige Antwort gibt.
Recommended Posts