[PYTHON] Codeforces Round # 618 (Div. 2) Bacha Review (9/26)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

(Seit ich es am 04.10. Geschrieben habe, ist mein Gedächtnis etwas vage.)

Diesmal ging es ohne WA gut. Ich habe jedoch zu viel Zeit mit dem Auftreten und der Lesbarkeit des D-Problems verbracht. Neulich fühlte sich ARC auch von dem Problem überwältigt, deshalb möchte ich mich an das Problem mit den hohen Schwierigkeitsgraden gewöhnen und Vertrauen gewinnen, damit ich unabhängig von der Punktzahl genau und konkurrenzlos denken kann.

Problem A

Stellen Sie sicher, dass weder die Summe noch das Produkt Null ist. Erstens ** ist es einfacher, über das Produkt nachzudenken ** und +1 zu jedem enthaltenen 0-Element hinzuzufügen, um zu verhindern, dass 0 enthalten ist. Wenn die Summe 0 ist, können Sie basierend darauf +1 zu einem geeigneten Element (außer -1) hinzufügen und die Anzahl von +1 bis jetzt ermitteln.

A.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    for i in range(n):
        if a[i]==0:
            a[i]=1
            ans+=1
    if sum(a)!=0:
        print(ans)
    else:
        print(ans+1)

B-Problem

Finden Sie den Wert, wenn die Differenz zwischen den Medianwerten bei Aufteilung in zwei ungerade Zahlen minimiert wird. Ich konnte nicht sofort eine Lösung finden, aber ich dachte, es wäre sowieso ein Knebel, weil einige Leute vorbeikamen. Also nahm ich die Differenz zwischen den beiden Werten in der Mitte, zählte vom kleinsten und probierte die Stichprobe aus, und sie stimmte überein, also reichte ich sie ein.

Ich würde es gerne mit einer gewissen Sicherheit einreichen, aber ich war ungeduldig und reichte dieses Problem ohne Beweise ein. Ich werde es nicht beweisen, weil ich nicht motiviert bin, aber ich muss nur zeigen, dass ein Median unter dem $ n $ -ten Element und der andere unter dem $ n + 1 $ -ten Element liegt. Wenn Sie beispielsweise davon ausgehen, dass die Medianwerte alle $ n $ oder weniger sind, können Sie dies mit der absurden Methode ** anzeigen.

B.py

for _ in range(int(input())):
    n=int(input())
    a=sorted(list(map(int,input().split())))
    print(a[n]-a[n-1])

C-Problem

Zuerst habe ich ein Experiment gemacht und darüber nachgedacht. Da es bitweise oder ** ist, sollten Sie auch die Operation für jedes Bit ** berücksichtigen. Wenn man nun bedenkt, was mit der Berechnung von $ f (x, y) = (x | y) -y $ bei jedem Bit passiert, ist es wie folgt.

Daher ist die Bedingung, dass die $ f (x, y) $ -Binäroperation in der Reihenfolge von vorne ausgeführt wird und das $ i $ -Bit schließlich auffällt, ** das Bit des ersten Elements 1 ist und danach nur 0 ausgegeben wird. Wenn es nicht kommt **. Betrachten Sie zunächst ** als Voraussetzung **, dass es nur eine Anzahl von ** $ i $ Bits gibt, die 1 sind. Durch Verarbeiten dieser Bedingung können Sie ein Maskenbit vorbereiten, das im $ i $ -Bit auffällt, wenn es nur eine Zahl gibt, in der das $ i $ -Bit 1 ist. Wenn Sie dann eine bitweise Operation zwischen der ersten Zahl ($ n $ Straße) und ihrem Maskenbit ausführen, finden Sie den Maximalwert der endgültigen Zahl, die Sie erhalten können. Außerdem hängt ** die endgültige Nummer nicht von der Reihenfolge der anderen Nummern als der ersten Nummer ** ab, sodass Sie sie entsprechend anordnen können.

C.py

n=int(input())
a=list(map(int,input().split()))
mask=0
for i in range(31):
    if [(j>>i)&1 for j in a].count(1)==1:
        mask+=(1<<i)
#Finde das Maximum
ans=[-1,-1]
for i in range(n):
    if ans[0]<(a[i]&mask):
        ans[0]=a[i]&mask
        ans[1]=i
realans=[]
realans.append(a[ans[1]])
for i in range(n):
    if i!=ans[1]:
        realans.append(a[i])
print(" ".join(map(str,realans)))

D Problem

Wenn Sie es sehen können, ist es eine einfache Sache. Ich persönlich fand es sehr schwierig, die Problemstellung zu lesen.

Um die Problemstellung zusammenzufassen, prüfen Sie zunächst, ob der äußere Rahmen, der beim parallelen Verschieben der angegebenen Figur unter Einbeziehung des Ursprungs erstellt wird, der ursprünglichen Figur ähnlich ist. Zu diesem Zeitpunkt dachte ich, es wäre gut, wenn es Seiten gäbe, die parallel wären und die gleiche Länge ** hätten (z. B. Diamant). Dieser intuitive Beweis kann durch die Darstellung der Bewegung bei paralleler Bewegung gesehen werden, um so weit wie möglich vom Ursprung entfernt zu sein, einschließlich des Ursprungs **. Ich hatte eine gute Vorstellung davon und habe Beispiel 2 illustriert. Dann wurde es intuitiv, also werde ich dies implementieren.

Da die Punkte gegen den Uhrzeigersinn angegeben werden, nutzen wir die Tatsache, dass das Verbinden benachbarter Punkte zu einer Seite wird, und speichern die Seiten (als Vektor) in der Reihenfolge, in der $ Kanten $ angegeben sind. Wenn ** $ n $ eine ungerade Zahl ist, wird sie nicht gepaart **, sodass NO im Voraus ausgegeben wird. Es gibt auch $ n $ Seiten, aber in $ Kanten $ werden die Seiten, die durch $ \ frac {n} {2} $ getrennt sind, gepaart, so dass die Paare parallel und gleich lang sind. Richter. Da dieses Urteil die Seiten als Vektor speichert, muss nur beurteilt werden, ob ** die Addition zu einem 0-Vektor ** wird.

D.py

n=int(input())
points=[]
for i in range(n):
    points.append(list(map(int,input().split())))
if n%2==1:
    print("No")
    exit()
edges=[]
for i in range(n-1):
    edges.append([points[i+1][0]-points[i][0],points[i+1][1]-points[i][1]])
edges.append([points[0][0]-points[n-1][0],points[0][1]-points[n-1][1]])
#print(edges)
for i in range(n//2):
    if edges[i][0]+edges[i+n//2][0]!=0 or edges[i][1]+edges[i+n//2][1]!=0:
        #print(i)
        #print(points[i][0]+points[i+n//2][0])
        #print(points[i][1]+points[i+n//2][1])
        print("No")
        exit()
print("Yes")

E Problem

Nach der Überlegung schien es möglich zu sein, es zu implementieren, wenn es einen Segmentbaum gab, der Intervalle hinzufügen und den Maximalwert annehmen konnte, aber es war unmöglich, weil es keine einfache Ganzzahl war, die ich in den Segmentbaum einfügen wollte.

Ich wollte den Segmentbaum wegen ACLBC verstehen, aber ich hatte nicht genug Motivation und habe ihn noch nicht genommen (ich verstehe RMQ). Ich habe auch ein Ameisenbuch gekauft, daher plane ich, es bald zu nehmen, und ich werde es zu diesem Zeitpunkt als Übung speichern.

F Problem

Ich werde diesmal überspringen