[PYTHON] Codeforces Round # 638 (Div. 2) Bacha Review (9/16)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich konnte das Problem nicht lösen, weil ich etwas zu tun hatte, während ich über das Problem nachdachte. Ich bin enttäuscht, weil es gelöst worden wäre, wenn es nicht enthalten gewesen wäre.
Auch wenn das C-Problem grob in Fälle unterteilt werden konnte, bestand es nicht, so dass ich es nach der Reorganisation schrieb und AC ** konnte. Ich denke, wir haben einen guten Wechsel gemacht. Ich konnte das D-Problem jedoch nicht auf halbem Weg umschalten, daher möchte ich das Problem konsequent behandeln.
Problem A
Da $ 2 ^ + 2 ^ 2 +… + 2 ^ {n-1} <2 ^ n $ ist, sollte die Summe derjenigen, die $ 2 ^ n $ enthalten, minimiert werden. Daher ist der absolute Wert der zu erhaltenden Differenz $ (2 ^ 1 + 2 ^ 2 +… + 2 ^ {\ frac {n} {2} -1} + 2 ^ n) - (2 ^ {\ frac {n}) {2}} + 2 ^ {\ frac {n} {2} + 1} +… + 2 ^ {n-1}) Der Unterschied beträgt $.
A.py
for _ in range(int(input())):
n=int(input())
a=2**n+sum(2**i for i in range(1,n//2))
b=sum(2**i for i in range(n//2,n))
print(a-b)
B-Problem
Ich hatte kürzlich ein Problem mit dem gleichen Thema im ABC. Berücksichtigen Sie beim Beachten aufeinanderfolgender $ k $ -Stücke ** den Unterschied, wenn Sie nacheinander gleiten **. In diesem Problem sind die Summen gleich, sodass die letzten Elemente in der durch $ k $ getrennten Zahlenfolge gleich sind **.
Die Tatsache, dass die durch $ k $ getrennten Teile gleich sind, entspricht der Tatsache, dass in der Zeichenfolge ** ein Punkt mit der Länge ** Länge $ k $ erscheint. Wenn dieser Zyklus keine Nummer enthalten kann, die in der ursprünglichen Sequenz enthalten ist, gibt es keine Sequenz, die dem Betreff entspricht. Wenn daher (der Typ der Nummer, der in der Nummernfolge erscheint) $> k $ ist, kann die Zahlenfolge, die das Thema erfüllt, nicht erstellt werden und -1 wird ausgegeben.
Betrachten Sie auf dieser Grundlage eine ** bequeme Zahlenfolge **, die das Thema erfüllt. Zu diesem Zeitpunkt ist zu beachten, dass sich die Positionsbeziehung der Zahlen in der ursprünglichen Zahlenfolge nicht ändert **, da nur die Einfügeoperation ausgeführt wird. Daher kann es implementiert werden, indem der Punkt mit einem beliebigen Zeichen ** auf ** eine geeignete Zahlenfolge gesetzt wird ** und überprüft wird, ob er in der richtigen Reihenfolge erscheint, während die ursprüngliche Zahlenfolge betrachtet wird. Dieses Mal habe ich jedoch als bequemeres Array ** eine Zahlenfolge betrachtet, in der jedes Element einmal in jedem Zyklus erscheint **. Mit anderen Worten, wenn Sie $ n $ mal mit demselben Zyklus wie zuvor wiederholen, können Sie eine Folge von Zahlen erstellen, die das Thema erfüllt, ohne dies zu überprüfen.
B.py
from collections import deque
for _ in range(int(input())):
n,k=map(int,input().split())
a=list(map(int,input().split()))
if len(set(a))>k:
print(-1)
continue
ans=[]
for i in set(a):
ans.append(str(i))
for i in range(k-len(set(a))):
ans.append(str(a[i]))
realans=[]
for i in range(n):
realans+=ans
print(len(realans))
print(" ".join(realans))
C-Problem
Es ist ein Problem, auf den Eckkasten zu treten, wenn Sie sich nicht beruhigen. Das Beispiel ist jedoch so freundlich, dass Sie die richtige Antwort erhalten.
Zuerst dachte ich, dass es besser wäre, es so gleichmäßig wie möglich zu teilen **, aber ich erkannte, dass es besser ist, wenn es mehrere Arten von Zeichen gibt, diese in derselben Zeichenfolge zu verketten **. Wenn das erste Zeichen ein anderes Zeichen hat, wird nur ein anderes Zeichen ausgegeben. Diese Überlegungen könnten experimentell erhalten werden, aber es ist wichtig, die Einzelfallachse zu verallgemeinern, wenn sie zur Implementierung angehoben wird. Hier konzentrieren wir uns auf ** die Anzahl der Zeichentypen ** und ** das erste Zeichen ** und klassifizieren sie wie folgt.
(1) Wenn es nur einen Zeichentyp gibt Sortieren Sie die Zeichen so gleichmäßig wie möglich und geben Sie dann die längste Zeichenfolge aus.
(2) Wenn am Anfang ein anderes Zeichen erscheint Es wird nur eines der größten Zeichen ausgegeben, das zuerst angezeigt wird.
(Das Folgende ist der Fall, wenn die ersten Zeichen alle gleich sind, es jedoch zwei oder mehr Arten von Zeichen gibt.)
(3) Wenn es drei oder mehr Arten von Zeichen gibt Nach dem zweiten Zeichen sollten alle verbleibenden Zeichen in einer Zeichenfolge verkettet werden. Ich denke, es ist am besten, sich vorzustellen, dass große Wörter in der Wörterbuchreihenfolge so weit wie möglich zurückliegen.
(4) Wenn es zwei Arten von Zeichen gibt Wenn das kleinere Zeichen in der Wörterbuchreihenfolge genau $ k $ ist, wird der Rest so gleichmäßig wie möglich sortiert und dann die längste Zeichenfolge ausgegeben. Wenn es nicht $ k $ ist, können Sie alle verbleibenden Zeichen in einer Zeichenfolge verketten.
In Bezug auf (✳︎) (3) und (4) halte ich es für rationaler, den Fall zu betrachten, in dem nach dem zweiten Zeichen zwei oder mehr Arten von Zeichen stehen. Während des Wettbewerbs konnte ich nicht so organisiert denken.
C.py
from collections import Counter
for _ in range(int(input())):
n,k=map(int,input().split())
s=sorted(input())
t=list(Counter(s).items())
if len(t)==1:
print(s[0]*(-(-n//k)))
continue
now=s[0]
ans=s[k-1]
if now!=ans:
print("".join(ans))
elif len(t)>=3:
print("".join(s[k-1:]))
elif t[0][1]==k:
print(t[0][0]+t[1][0]*(-(-n//k)-1))
else:
print("".join(s[k-1:]))
D Problem
(Im Folgenden wird all = in die Ungleichungszahl gesetzt. Es gibt einige mathematische Unterschiede, aber bitte verzeihen Sie mir.)
Auf den ersten Blick ist es ein schwieriges Problem, aber sobald Sie die Essenz verstanden haben, ist es nicht mehr so schwierig. In Bezug auf die Schleimaufteilungsoperation ist der Schleim, dessen Masse in dieser Nacht durch Aufteilen $ m \ _i + 1 $ betragen sollte, $ (\ frac {m \ _i} {2} + 1) + (\ frac Da es zu {m \ _i} {2} + 1) $ wird, ist es leicht zu verstehen, dass es ** eine Operation ist, die die Masse um +1 ** erhöht. Darüber hinaus ist die Anzahl der Schleime, die beim Teilen ausgewählt werden sollen, frei, und jede Masse kann ausgedrückt werden, ohne sie auch nur einmal zu teilen. Daher muss unter dem Gesichtspunkt vorgegangen werden, dass es keine Masse gibt, die nicht ausgedrückt werden kann. Um die Masse so weit wie möglich zu erhöhen, ist es am besten, alle vorhandenen Schleime auszuwählen und zu teilen. Sie können die Masse jedoch nicht einfach auf $ n $ einstellen, es sei denn, Sie passen sie durch die letzte Operation an. **Ich verstehe das.
Darunter beträgt die Anzahl der Bakterien am Morgen des $ i $ -Tages $ a \ _i $, $ i $. Das Gesamtgewicht der Bakterien am Morgen des $ i $ -Tages beträgt $ b \ _i $, $ i $ Unter der Annahme, dass die Anzahl der auszuwählenden Bakterien $ x \ _i $ ist, gilt die folgende allmähliche Gleichung.
Was wir hier endlich herausfinden wollen, ist die Anzahl der Tage, die erforderlich sind, damit $ b \ _i $ zu $ n $ wird, aber von ** $ n $ subtrahieren Sie $ a \ _i $, um 0 zu machen **. Es scheint besser darüber nachzudenken. Hier kann es $ a \ _i \ leqq a \ _ {i + 1} \ leqq 2 a \ _i $ sein, also ist es gut, wenn $ a \ _i \ leqq n \ leqq 2 a \ _i $ am letzten Tag erfüllt ist. ist. Auch wenn $ n> 2a \ _i $, möchte ich es so teilen, dass $ a \ _ {i + 1} = 2 a \ _i $ so viel wie möglich, aber ** einen Tag vor dem letzten Tag ** $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow 2 a \ _i \ leqq a \ _ {i + 2} \ leqq 4 a Von \ _i $ $ 2 a \ _i \ leqq na \ _ {i + 1} \ leqq 4 a \ _i \ leftrightarrow 4a \ _i \ leqq n \ leqq 6 a \ _i $ muss erfüllt sein. Wenn also $ 2a \ _i <n <4a \ _i $ ist, müssen Sie $ x \ _i $ auswählen, was weniger als ** $ a \ _ {i} $ ist, und am nächsten letzten Tag nur ** bis $ n $. Muss sein.
Wenn zum Beispiel $ x \ i = 0 $ ist, dann ist $ a {i + 1} = a \ _i $, also $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow a \ _i \ leqq a \ _ {i + 2} \ leqq 2 a \ _i $ von $ a \ _i \ leqq na \ _ {i + 1} \ leqq 2 a \ _i Es ist Zeit, \ leftrightarrow 2a \ _i \ leqq n \ leqq 3 a \ _i $ zu füllen.
Was bleibt, ist, wenn $ 3a \ _i <n <4a \ _i $, aber zum Beispiel, wenn $ x \ _i = [\ frac {a \ i} {2}] $, dann $ a {i + 1} = a \ _ i + [\ frac {a \ _ i} {2}] $, also $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ Von links rechts a \ _i + [\ frac {a \ _i} {2}] \ leqq a \ _ {i + 2} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _ i} {2}] $ $ a \ _i + [\ frac {a \ _i} {2}] \ leqq na \ _ {i + 1} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _i} {2}] \ leftrightarrow 2a \ _i + 2 [\ frac {a \ _i} {2}] \ leqq n \ leqq 3a \ _i + 3 [\ frac {a \ _ i} {2}] $ muss erfüllt sein. Da dies die Zeit von $ 3a \ _i <n <4a \ _i $ beinhaltet, wird dies auch angezeigt, wenn $ 3a \ _i <n <4a \ _i $.
Aus dem Obigen ergibt sich $ x \ _i = na \ _i $, $ n \ leqq 3a \ _i $ für $ n \ leqq 2a \ _i $, $ x \ _i = 0 $, $ n <4a \ _i $ Wenn $ x \ _i = [\ frac {a \ _ i} {2}] $, $ n \ geqq 4a \ _i $, dann $ x \ _i = a \ _i $ und geben Sie die Mindestanzahl von Tagen an Es ist möglich, Bakterien mit der Gesamtmasse der Bakterien zu produzieren.
D.py
for _ in range(int(input())):
n=int(input())
ans=[]
ai=1
n-=1
xi=0
while True:
if n<=2*ai:
xi=n-ai
ai=ai+xi
n-=ai
ans.append(xi)
break
elif n<=3*ai:
xi=0
ai=ai+xi
n-=ai
ans.append(xi)
elif n<4*ai:
xi=ai//2
ai=ai+xi
n-=ai
ans.append(xi)
else:
xi=ai
ai=ai+xi
n-=ai
ans.append(xi)
#print(2)
#print(ai,xi,n)
print(len(ans))
print(" ".join(map(str,ans)))
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts