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.
A - Beginner Auf einer bestimmten Website für Wettbewerbsprofis scheint die Bewertung von Personen mit einer geringen Anzahl von Malen höher als die interne Bewertung angezeigt zu werden. Die tatsächliche interne Bewertung ist eine Frage, die einige beantwortet.
Wenn die Häufigkeit, mit der N 10 oder mehr beträgt, so ausgegeben wird, wie sie ist. Wenn es kleiner als 10 ist, ist der Wert, der durch Addieren des Korrekturwerts $ 100 \ times (10-N) $ erhalten wird, die interne Bewertung.
N, R = map(int, input().split())
if N < 10:
print(R + 100 * (10-N))
else:
print(R)
B - Digits Es ist eine Frage zu beantworten, wie viele Stellen sein werden, wenn der numerische Wert N in K-Notation ausgedrückt wird.
Überlegen Sie, wo die größte Ziffer sein wird. Wenn beispielsweise $ N = 9, K = 2 $, $ 1000 $, dh $ 2 ^ 3 $, die größte Ziffer ist und $ r = 4 $ erhalten wird. Wenn wir dies in einer mathematischen Formel ausdrücken, können wir einen Multiplikator r finden, der die folgenden Anforderungen erfüllt.
Ich habe das einfach umgesetzt.
N, K = map(int, input().split())
r = 1
while not(K**(r-1) <= N and N < K ** r):
r += 1
print(r)
Dies verlief ohne Probleme, aber als ich mir die Erklärung ansah, war die Methode anders.
Die Anzahl der zu berechnenden Ziffern beträgt $ D $, und der Wert jeder Ziffer beträgt $ a_ {D-1}, \ cdots, a_1, a_0 $
Dann
Es wird durch die Formel ausgedrückt.
Wenn Sie den Vorgang des Teilens von $ N $ durch $ K $ und des Quotienten wiederholen, beträgt der Quotient $ 0 $, wenn $ D $ durch $ K $ geteilt wird.
Lassen Sie uns dies implementieren.
N, K = map(int, input().split())
D = 0
while N:
N //= K
D += 1
print(D)
Bei beiden Berechnungszeit gab es kein Problem.
C - Rally
Die Frage ist zu beantworten, wo der Punkt (ganzzahliger Wert) ist, an dem der quadratische Fehler für diejenigen, die auf der geraden Linie der Zahl platziert sind, am kleinsten ist.
Die Minimum-Square-Methode ist mit der Problemstellung verbunden, aber sowohl N als auch X haben einen engen Bereich von 1 bis 100. Ich entschied, dass ich keine mathematischen Fähigkeiten brauchte, weil $ O (N ^ 2) $ ohne Probleme bestand, also suchte ich einfach überall.
N = int(input())
X = list(map(int, input().split()))
minLoss = 1e6
for i in range(1, 101):
minLoss = min(minLoss, sum([(x - i)**2 for x in X]))
print(minLoss)
Ich ging daran vorbei.
Ich denke, es wäre etwas effizienter, wenn der linke und der rechte Bereich auf die Minimal- und Maximalwerte von X anstatt von 1 bis 100 eingestellt würden.
D - Bouquet Wie viele Kombinationen können aus N verschiedenen Blüten entnommen werden? A und b können jedoch nicht herausgenommen werden. Ist das Problem.
TLE, weil ich versucht habe, eine Kombination mit $ _nC_r $ für jede Zahl n von 1 bis N zu finden. Ich gab auf.
Ich habe den Kommentar gesehen. "Alle Kombinationen für alle Zahlen" ist viel einfacher zu berechnen.
Für jede Blume gibt es nur zwei Optionen: "Verwenden" und "Nicht verwenden". Alle Kombinationen sind also $ 2 ^ N $. Die Kombination, die 0 verwendet, ist jedoch ausgeschlossen, sodass es sich genau um $ 2 ^ N-1 $ handelt.
Es kann durch Subtrahieren der Kombinationen erhalten werden, die von $ _nC_r $ für a und b ausgeschlossen werden sollen.
from scipy.misc import comb
m = 1000000007
n, a, b = map(int, input().split())
out = 2**n - comb(n, a) - comb(n, b)
print(out%m)
Das war nicht gut. Das Problem ist, dass 2 ** n, $ _nC_a und _nC_b $ zu viele sind.
Um das loszuwerden Es ist notwendig, die Berechnung durch eine mathematische Methode unter Verwendung der Bedingung "Rest geteilt durch $ 10 ^ 9 + 7 $" zu reduzieren.
Betrachten Sie zunächst den Multiplikator von 2. In Python können Sie "pow ()" anstelle von "**" verwenden, um die durch das dritte Argument zu teilende Zahl anzugeben, und die Restberechnung kann mit hoher Geschwindigkeit durchgeführt werden.
print(pow(2, 4, 3)) # 1
Als nächstes sollten Sie die Kombinationsberechnung beschleunigen.
Es gibt den Satz von Fermat. Wenn $ p $ eine Primzahl ist und $ a $ und $ p $ Primzahlen zueinander sind
Ist festgelegt. Mit anderen Worten ergibt das Teilen von a durch die p-1-Potenz von p 1. Es scheint. Ich wusste es nicht.
Ich habe es nicht wirklich gespürt, also werde ich es versuchen.
p = 29
for a in range(3, 29, 5):
print("a: {}, p: {}, a^(p-1)%p: {}".format(a, p, pow(a, p-1, p)))
'''
a: 3, p: 29, a^(p-1)%p: 1
a: 8, p: 29, a^(p-1)%p: 1
a: 13, p: 29, a^(p-1)%p: 1
a: 18, p: 29, a^(p-1)%p: 1
a: 23, p: 29, a^(p-1)%p: 1
a: 28, p: 29, a^(p-1)%p: 1
'''
Das ist wahr. Hmm. Der Beweis wird hier nicht erwähnt.
Gib die Geschichte zurück. Unter dieser Bedingung sind $ 10 ^ 9 + 7 $ und Y immer Primzahlen zueinander, daher gilt die folgende Gleichung.
Teilen Sie beide Seiten durch Y.
pow () verwenden, um wie zuvor mit hoher Geschwindigkeit zu berechnen. Die Begriffe, die in der Kombinationsberechnung erscheinen, werden in den Nenner X und das Molekül Y getrennt, und Y wird dieser Verarbeitung unterzogen.
m = 1000000007
n, a, b = map(int, input().split())
def comb(n, r, m):
X, Y = 1, 1
for i in range(r):
X *= n-i
Y *= i+1
X %= m
Y %= m
return int(X * pow(Y, m-2, m))
out = pow(2, n, m) - 1 - comb(n, a, m) - comb(n, b, m)
print(out%m)
Ich ging daran vorbei.
E - Roaming Wenn sich eine Person in jedem der n Räume k-mal bewegt, wie viele Raumbedingungen können es sein? Ist das Problem.
Ich konnte mir nicht vorstellen, wie ich es lösen sollte, also gab ich auf.
Ich habe den Kommentar gesehen.
Betrachten Sie zunächst eine Kombination von Räumen mit 0 Personen. Angenommen, $ m $ der Räume sind leer. Dann die Kombination der Auswahl von m Räumen aus allen n Räumen
Es kann von gefunden werden.
Betrachten Sie von dort aus die Kombination der Räume, in die der ursprüngliche Bewohner des m-Zimmers gezogen ist. Es gibt viele Denkweisen, aber der einfachste Weg besteht darin, die $ m $ Einwohner durch $ n-m-1 $ Wände zu teilen. Wenn der Bewohner 〇 ist und die Wand | ist, kann dies in das Problem geändert werden, über die Kombination von Mustern zum Anordnen von Zeichenketten nachzudenken.
〇〇|〇|〇〇 Sie können eine solche Kombination erstellen.
Diese Anordnung ist
Kann mit berechnet werden.
Wenn Sie diese Berechnung auf diese Situation anwenden, erhalten Sie die folgende Formel.
Daher kann die Kombination von $ _nC_m \ times _ {n-1} C _ {m} $ erhalten werden, wenn keine $ m $ Räume vorhanden sind. Sie können addieren, während Sie dieses $ m $ von 0 in $ k $ (oder $ n-1 $) ändern.
Zusätzlich kann das Berechnungsergebnis der Kombination für die nächste Kombinationsberechnung verwendet werden.
Deshalb ist es ein Implementierungsbeispiel. Ich schreibe, während ich den Code von fast anderen Leuten betrachte.
n, k = map(int, input().split())
c1 = 1
c2 = 1
mod = 10**9+7
ans = 0
for i in range(min(n, k+1)):
ans += c1 * c2
c1 *= (n-i) * pow(i+1, mod-2, mod)
c1 %= mod
c2 *= (n-i-1) * pow(i+1, mod-2, mod)
c2 %= mod
print(ans%mod)
Dies ist das Ende dieses Artikels.
Recommended Posts