Le résultat était de 76 points, ce qui était intermédiaire (60-79 points). La dernière fois, j'étais à peine intermédiaire avec 64 points, mais cette fois j'étais avancé si je résolvais encore une question.
Si vous définissez Bx sur -x et xF sur x, vous devez seulement faire attention lorsque la différence entre B1 et 1F n'est pas 1.
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)))
Percer en 3 minutes et demie. Il suffit de regrouper et de produire le plus.
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])
Pénétrez en 12 minutes. Écrivez simplement en fonction de l'énoncé du problème.
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))
Percer en 11 minutes. Puisque "." Est un caractère arbitraire, c'est une expression régulière à faire correspondre. Après cela, tous les modèles sont générés, mais Python est 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)
Percer en 8 minutes et demie Je pense qu'il n'y a rien de difficile parce que je l'écris exactement comme il est écrit dans l'énoncé du problème.
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)
Pause en 7 minutes et demie. M'a rappelé ABC137D - Vacances d'été. Prenez simplement la tâche avec les points les plus élevés de la file d'attente de prescription et digérez-la à plusieurs reprises.
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)
Percer en 32 minutes. Résolu avec DP qui cherche le coût minimum de tous les endroits précédents à tous les endroits suivants.
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])
Percer en 23 minutes et demie. TLE est inévitable si vous créez une chaîne de caractères obéissant conformément à l'énoncé du problème, j'ai donc géré et résolu la liste des paires de caractères et de longueur.
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()))
Percer en 12 minutes. Le nombre de personnes est de 2 N </ sup> et N est aussi petit que 16 ou moins, il est donc facile de le simuler docilement.
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)
Percer dans 20 minutes. La longueur de la chaîne de caractères finale S est inférieure ou égale à 1 000, vous pouvez donc la simuler docilement. Si vous trouvez la parenthèse gauche, recherchez la parenthèse droite appariée, et s'il y a une parenthèse à l'intérieur, continuez Puisque nous devons le traiter, écrivez le processus avec une fonction récursive et terminez.
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))
Si vous l'écrivez docilement, ce sera * O * (* N * 2 </ sup>) et ce sera TLE, pensez donc à réduire la quantité de calcul. Comme il s'agit d'une méthode gourmande qui prend l'extrémité gauche de la valeur minimale de la plage sélectionnable, la valeur minimale de l'intervalle Est calculé par Segment Tree et devient * 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)
Addendum: j'ai essayé de le résoudre avec une file d'attente prioritaire comme expliqué. Je me demandais quoi faire lorsque la valeur déjà passée était laissée dans la file d'attente, alors je me demandais quoi faire quand elle devenait le minimum, mais oui, je devrais la jeter Est-ce …….
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)
Je l'ai également résolu avec Sparse Table. Dans ce problème, SegmentTree est * O * (* N * + (* N * / * D *) log N </ i>), alors que * O * ( > N </ i> log N </ i> + * N * / * D *) donc c'est un peu lent.
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)
Je ne peux pas percer. Je fais TLE, mais je ne peux même pas écrire une implémentation naïve qui donne la bonne réponse.
Recommended Posts