Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.
Die Lösung, die ich hier schreibe, wird geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansehe. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.
Die Zeichenkette T ist eine Frage, um zu beantworten, ob die Zeichenkette S am Ende ein Zeichen hat.
Wir verglichen, indem wir T mit T [: -1] schnitten.
S = input()
T = input()
if S == T[:-1]:
print('Yes')
else:
print('No')
Es gibt $ A $ für Karten mit der Bezeichnung 1, $ B $ für Karten mit der Bezeichnung 0 und $ C $ für Karten mit der Bezeichnung -1. Der Maximalwert bei der Auswahl von $ K $ ist eine zu beantwortende Frage.
Der Zählung in der Größenordnung von 1, 0, -1 sollte Vorrang eingeräumt werden. Da es sich jedoch um $ A, B, C \ leq2 \ times10 ^ 9 $ handelt, tut es weh, wenn Sie versuchen, es in ein Array zu legen oder mit for zu drehen. (Ein Verlust)
A, B, C, K = map(int, input().split())
out = min(A, K) - max(0, K-A-B)
print(out)
Das Problem besteht darin, den niedrigsten Preis in einer Kombination zu finden, bei der alle für jede Zahl summierten Elemente $ X $ überschreiten.
Das Limit von $ N, M \ leq 12 $ ermöglicht eine vollständige Abdeckung. Parallele Berechnungen wurden durchgeführt, indem "itertools.product ()" und dann "numpy" für die vollständige Suche verwendet wurden.
import itertools
import numpy as np
N, M, X = map(int, input().split())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)
out = 10**18
for c in itertools.product([False, True], repeat=N):
tmp = np.sum(items[np.where(c)], axis=0)
if M == np.count_nonzero(tmp[1:] >= X):
out = min(out, tmp[0])
if out == 10**18:
print(-1)
else:
print(out)
Jede Stadt hat ein Warp-Ziel. Die Frage ist, K-mal aus der ersten Stadt zu teleportieren und die ankommende Stadt zu beantworten.
Wenn Sie ab dem Limit von $ K \ leq10 ^ {18} $ richtig suchen, ist dies TLE. Ich gab auf. Sehen Sie die Antworten anderer Leute.
Es sollte beachtet werden, dass der Bereich von K $ K \ leq 10 ^ {18} $ ist, aber der Bereich von N $ N \ leq 2 \ mal 10 ^ {5} $ ist. Mit anderen Worten, diese Suche wird immer wiederholt.
Suchen Sie zunächst normal. Speichern Sie die Zeit t_zero, die zuerst in jeder Stadt angekommen ist, als Array und berechnen Sie die Zeit für eine Runde, wenn Sie dieselbe Stadt ein zweites Mal erreichen. Nehmen Sie die verbleibende Laufzeit einer Runde von K. Verwenden Sie die zuvor durchgeführten Berechnungen erneut, ohne erneut nach der verbleibenden Zeit k suchen zu müssen. Ich habe den folgenden Code übergeben.
N, K = map(int, input().split())
A = list(map(int, input().split()))
t_zero = [-1] * N
t = 0
a = 1
while t_zero[a-1] == -1:
if t == K:
break
t_zero[a-1] = t
t += 1
a = A[a-1]
else:
k = (K - t_zero[a-1]) % (t - t_zero[a-1])
a = t_zero.index(t_zero[a-1] + k) + 1
print(a)
Es ist ein Problem, die in einer horizontalen Reihe angeordneten Blöcke farblich zu kennzeichnen. Es kann jedoch erlaubt sein, dass dieselbe Farbe bis zu K nebeneinander liegt, und wie viele Kombinationen gibt es?
Es gibt $ M \ times (M-1) ^ {N-1} $ Kombinationen, in denen N Stücke von M Farbe so angeordnet sind, dass sie nicht nebeneinander liegen.
Wenn K-Gruppenblöcke nebeneinander liegen können, kann gesagt werden, dass $ N-K $ -Blöcke so angeordnet sind, dass die Farben nicht ausgerichtet sind. Außerdem können Sie die Kombination benachbarter Blöcke mit $ _ {N-1} C _ {K} $ auswählen.
Mit anderen Worten, Sie können die folgende Formel berechnen.
Folgendes ist implementiert. Während der Produktion konnte ich die Berechnung jedoch nicht gut beschleunigen und nicht rechtzeitig lösen.
N, M, K = map(int, input().split())
out = 0
mod = 998244353
c = 1
for k in range(K+1):
out += M * pow(M-1, N-k-1, mod) * c
out %= mod
c *= (N-k-1) * pow(k+1, mod-2, mod)
c %= mod
print(out)
Hier
Das ist alles für diesen Artikel.
Recommended Posts