[PYTHON] Educational Codeforces Round 86 Bacha Review (9/17)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Diesmal war ich wie immer ungeduldig, aber ich konnte in letzter Minute D wechseln und passieren, also ist es ein guter Punkt. Wenn das Problem ungeduldig ist, ist das Problem schließlich nicht organisiert und ** das Memo ist in der Regel unübersichtlich **. Machen Sie sich also ** so sauber wie möglich ** und **, wenn Sie es wirklich nicht verstehen Ich möchte eine saubere Kopie machen **.
Problem A
Ich denke, es gab zuvor ein ähnliches Problem in ABC.
Die Vorzeichen von $ x und y $ sind gleich und $ x <y $. Zu diesem Zeitpunkt ist es am besten, alle monoton zu reduzieren. Da sich die Operation von ** ② gleichzeitig bewegt **, reduzieren Sie $ y $ durch die Operation von ① auf $ x $. Da $ y = x $ ist, können Sie außerdem die am besten geeignete Operation für die Operationen ① und ② auswählen, und der zu erhaltende Mindestwert ist $ (yx) \ mal a + min (x \ mal b, 2 \ mal x \ mal a) $. Es wird sein.
A.py
for _ in range(int(input())):
x,y=map(int,input().split())
a,b=map(int,input().split())
if x>y:
x,y=y,x
print((y-x)*a+min(x*b,2*x*a))
B-Problem
In letzter Zeit habe ich das Gefühl, dass es möglich geworden ist, Probleme im Zusammenhang mit der Konstruktion von Kodofo mit hoher Geschwindigkeit zu lösen. Ich würde mich freuen, wenn Sie mit ABC herauskommen könnten (ich bin sehr enttäuscht, weil es beim letzten Mal bei ABC-F der Fall war ...).
Zunächst dachte ich, dass ** der Zyklus ziemlich klein gemacht werden könnte **. Dies liegt daran, dass der Zeitraum 2 ist, wenn Sie eine Zeichenfolge mit dem Wert $ 0101… $ oder $ 1010… $ erstellen können. Die auf dieser Richtlinie basierenden Überlegungen lauten wie folgt.
Zuerst,
B.py
for _ in range(int(input())):
t=input()
if all(i=="0" for i in t) or all(i=="1" for i in t):
print(t)
else:
print(len(t)*"01")
C-Problem
Als ich die anfängliche Richtlinie erstellt habe, war ich ungeduldig, weil ich einen Fehler in ** $ i, j $ gemacht habe, den ich geschrieben habe **, und ich konnte nicht die richtige Antwort finden. Danach habe ich trotz des typischen Problems ** versucht, es analytisch zu lösen **.
Zunächst ist es offensichtlich, dass die Berechnung in der Abfrage nicht rechtzeitig erfolgt, also ** vorberechnen **. Wenn Sie zu diesem Zeitpunkt alle möglichen Zahlen aufschreiben, sind es $ 10 ^ 9 $ **, also ist es offensichtlich nicht rechtzeitig.
Achten Sie also auf $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a $, $ i = x \ mod \ a, j = x \ mod \ b $ Wenn Sie die obige Formel kennen, können Sie sich die obige Formel vorstellen, also habe ich über $ ab $ der Kombination von $ i, j $ nachgedacht, aber ** Wenn Sie das Bild des chinesischen Restsatzes haben, müssen Sie nur den Rest von $ ab $ ** kennen verstanden. Dies kann $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a \ leftrightarrow (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a \ leftrightarrow sein Es kann aus der Tatsache gesagt werden, dass es k \ mod \ a) \ mod \ b \ neq (k \ mod \ b) \ mod \ a $ wird.
Daher ist als Vorberechnung $ pre [i]: = $ ($ (i \ mod \ a) \ mod \ b \ neq (i \ mod ), wenn der Rest geteilt durch $ ab $ $ 0 $ ~ $ i $ ist b) Suchen (die Anzahl von \ mod \ a $) (die kumulative Summe wird verwendet, da sie später benötigt wird).
Suchen Sie in der Abfrage außerdem, dass die Anzahl von $ i \ in [l, r] $ $ (i \ mod \ a) \ mod \ b \ neq (i \ mod \ b) \ mod \ a $ ist. Wird berechnet, indem die Zahl bei $ i \ in [0, l-1] $ von der Zahl bei ** $ i \ in [0, r] $ ** subtrahiert wird. Wenn die Zahl in $ i \ in [0, x] $ $ f (x) $ ist, kann sie auch mit $ f (r) -f (l-1) $ berechnet werden.
Auf dieser Grundlage sollten Sie $ f (x) $ mithilfe der Vorberechnung finden, aber der Rest geteilt durch ** $ ab $ ist $ 0 $ ~ $ ab-1 $, und die Zahlen werden in der Reihenfolge von 0 wiederholt. Betrachten Sie ** und die Anzahl der Schleifen, $ f (x) = [\ frac {x} {a \ times b}] \ times pre [ab-1] + pre [x \ mod \ ( Es kann berechnet werden als \ times b)] $.
Daher wird jede Abfrage mit $ O (1) $ berechnet, sodass Sie ein Programm öffnen können, das für $ O (t \ times (a \ times b + q)) $ als Ganzes ausreicht.
C.py
from itertools import accumulate
def f(i):
global a,b,pre
x=i//(a*b)
y=i%(a*b)
return x*pre[-1]+pre[y]
for _ in range(int(input())):
a,b,q=map(int,input().split())
pre=[int((i%a)%b!=(i%b)%a) for i in range(a*b)]
pre=list(accumulate(pre))
ans=[]
for i in range(q):
l,r=map(int,input().split())
ans.append(str(f(r)-f(l-1)))
#print(f(r),f(l-1))
print(" ".join(map(str,ans)))
D Problem
Persönlich war es ein intuitiveres und leichter zu lösendes Problem als das C-Problem. Es kann sehr effektiv sein, das zu lösende Problem zu ändern, nachdem es etwa 30 Minuten lang hängen geblieben ist. Die Problemstellung war jedoch etwas schwer zu lesen.
(Im Folgenden nehmen wir an, dass die für die Verteilung auf die Testfälle angegebenen Sequenzen $ m $ sind. Diese sind ** absteigend sortiert **.)
Jeder Testfall ist eine Sammlung mehrerer Sequenzen einer bestimmten Länge (← Ich interessiere mich nur für die Länge, also ** interpretiere sie als Sammlung mehrerer Zahlen ** und löse das folgende Problem). Außerdem werden Testfälle verwendet, wenn die Anzahl der Testfälle so verteilt ist, dass die Anzahl der Testfälle reduziert wird, während die Bedingung erfüllt ist, dass $ i $ in jedem Testfall weniger als $ c \ _i $ enthält **. Betrachten Sie die Anzahl der. Es füllt auch $ n \ geqq c \ _1 \ geqq c \ _2 \ geqq… \ geqq c \ _k \ geqq 1 $, um sicherzustellen, dass die Mindestanzahl von Testfällen vorhanden ist.
Hier habe ich mich entschlossen, gierig zu entscheiden, welcher Testfall in der Reihenfolge aus der Zahl mit der größeren Einschränkung ** aufgenommen werden soll. Es kann auch gesagt werden, dass ** wenn eine bestimmte Anzahl festgelegt wird, die Einschränkungen danach immer erfüllt sind **.
Bereiten Sie zunächst ein Array $ ans $ vor, das den gesamten Testfall verwaltet (jeder Testfall enthält mehrere Elemente). Außerdem sei die Länge von $ ans $ $ l $ und der Index, den Sie im Testfall $ ans $ betrachten, $ now $. Fügen Sie dann $ [m [0]] $ als ersten Testfall zu $ ans $ hinzu und initialisieren Sie $ now $ mit 0 und $ l $ mit 1.
Fügen Sie basierend darauf $ m [1],…, m [n-1] $ zum Testfall in dieser Reihenfolge hinzu. Wenn Sie $ m [i] $ betrachten, wenn $ m [i-1]> m [i] $, $ c [m [i] -1]> c [m [i-1] - Es kann 1] $ sein. In diesem Fall können Sie ** $ now $ auf 0 ** aktualisieren und $ m [i] $ durch $ ans [now] $ ersetzen. Dieses Urteil lautet auch $ len (ans [0]) \ <c [m [i] -1] $ oder $ c [m [i-1] -1] \ <c [m [i] -1] $ Kann von gemacht werden
Wenn als nächstes $ c [m [i] -1] = c [m [i-1] -1] $ ist, besteht die Möglichkeit, dass es nach dem in ** $ now $ ** gezeigten Element hinzugefügt werden kann $ now + = 1 $, bis ein Element gefunden wird, das zu $ len (ans [now]) \ <c [m [i] -1] $ wird, und wenn es gefunden wird, fügen Sie es zu $ ans [now] $ hinzu. Wenn es nicht gefunden wird, gibt es nicht genügend Testfälle. Fügen Sie also $ [m [i]] $ zu $ ans $ hinzu.
Wenn Sie dies wiederholen, können Sie sich gierig entscheiden, die Anzahl der Testfälle so weit wie möglich zu reduzieren. Danach können Sie den endgültigen Testfall gemäß den Anweisungen des Problems ausgeben.
Es ist schwierig, das oben Gesagte in Worten zu erklären, aber ich bin der Meinung, dass die Implementierung reibungslos erfolgen kann, solange die Legitimität der Giermethode verstanden wird.
D.py
n,k=map(int,input().split())
m=sorted(list(map(int,input().split())),reverse=True)
c=list(map(int,input().split()))
ans=[[m[0]]]
#ans Länge
l=1
#Welche Sequenz muss eingegeben werden?(Achten Sie auf Updates)(Als ob frei)
now=0
for i in range(1,n):
if len(ans[0])<c[m[i]-1]:
now=0
ans[now].append(m[i])
else:
while now!=l:
if len(ans[now])<c[m[i]-1]:
break
now+=1
if now==l:
ans.append([m[i]])
l+=1
else:
ans[now].append(m[i])
print(len(ans))
for i in range(len(ans)):
print(len(ans[i]),end=" ")
print(" ".join(map(str,ans[i])))
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts