[PYTHON] Codeforces Round # 645 (Div. 2) Bacha Review (9/10)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Diesmal fror der Computer ein und wurde wiederholt neu gestartet, was nicht sehr hilfreich war. Ich glaube jedoch, dass ich das D-Problem in kürzerer Zeit lösen konnte, daher möchte ich weiterhin mein Bestes geben.

Problem A

Ich mag Problemsätze nicht wirklich, aber es ist gut daran zu denken, Kacheln anzuordnen.

Ordne die $ 1 \ mal 2 $ Kacheln an. Wenn $ n \ times m $ gerade ist, können Sie die Kacheln einfach aneinanderreihen, sodass $ \ frac {n \ times m} {2} $ die Antwort ist. Wenn $ n \ times m $ ungerade ist, bleiben $ 1 \ times 1 $ Kacheln übrig, auch wenn sie gut angeordnet sind. Daher werden zusätzliche Kacheln benötigt. $ \ Frac {n \ times m -1} {2} + 1 $ Ist die Antwort.

A.py

for _ in range(int(input())):
    n,m=map(int,input().split())
    if n%2==0 or m%2==0:
        print(n*m//2)
    else:
        print((n*m-1)//2+1)

B-Problem

Das Problem war so lang, dass es scharf zu sein schien. Die Essenz war einfach und scharf.

Es ist leicht zu lösen, wenn Sie mit Beispiel denken. Außerdem wird die Anzahl der von jeder Person benötigten Personen in aufsteigender Reihenfolge angeordnet und in "a" gespeichert. Zu diesem Zeitpunkt ist es gut, Leute zu bewegen, die sich ** sofort ** bewegen können. Darüber hinaus beträgt die maximale Anzahl von Personen, die sich bewegen können, ** $ a [0], a [1],…, a [i] \ leqq i + 1 $ gilt **, was dem größten $ i $ +2 entspricht Es wird derjenige sein, der getan wurde. Hier $ a [0], a [1],…, a [i] \ leqq i + 1 \ leftrightarrow a [i] \ leqq i + 1 $, so dass es mit der for-Anweisung leicht bestimmt werden kann. .. Wenn es kein Element gibt, das $ a [i] \ leqq i + 1 $ enthält, lautet die Antwort 1.

B.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    for i in range(n-1,-1,-1):
        if a[i]<=i+1:
            print(i+2)
            break
    else:
        print(1)

C-Problem

Als ich anfing, dieses Problem zu lösen, war mein Computer kaputt und ich konnte nicht darüber nachdenken. Ich möchte ruhig sein, auch wenn ich von einem Unfall getroffen werde.

Wenn Sie überall suchen **, können Sie normalerweise an BFS ** denken, aber die Masse kann nicht $ (10 ^ 9) ^ 2 $ sein. Dann ** gehe vertikal oder horizontal ** zu $ \ _ {(x \ _2-x \ _1) + (y \ _2-y \ _1)} C _ {(x \ _2-x ) _1)} $ Es gibt also ich wollte darum bitten, aber es gibt nicht so viele. Mit anderen Worten, ** es kann dieselbe Zahl sein, wenn man verschiedenen Routen folgt **, also habe ich experimentiert und darüber nachgedacht. In Anbetracht der folgenden Abbildung gibt es beispielsweise $ \ _4 C \ _2 = 6 $ Routen, aber es gibt nur 5 Routen, $ 68,69,70,70,71,72 $.

Immerhin wollte ich herausfinden, wie viele Zahlen es gibt, also dachte ich, dass ** obere und untere Grenzen gefunden werden könnten **. Zu diesem Zeitpunkt ist, da die Anzahl von diagonal von oben nach unten zunimmt, zu sehen, dass die Route nach rechts und unten die kleinste und die Route nach unten und rechts die größte ist. Betrachten Sie daher ** den Unterschied finden ** (und wir müssen beweisen, dass die ganze Zahl zwischen der oberen und unteren Grenze durch einen geeigneten Pfad dargestellt werden kann, aber wir haben dies hier klargestellt).

Um den Unterschied zu finden, dachte ich an ein Beispiel für $ x \ _2-x \ _1 \ neq y \ _2-y \ _1 $ und betrachtete das folgende Beispiel.

Da der Unterschied nur berücksichtigt werden muss, wird er in Form von (+ Ganzzahl) ausgedrückt. Zu diesem Zeitpunkt können Sie anhand der obigen Abbildung sehen, dass die Anzahl der + nacheinander erhöht wird. Dies liegt daran, dass, wie Sie an der roten diagonalen Linie sehen können, der diagonale Unterschied zunimmt. Außerdem beträgt die Anzahl von + höchstens $ min (x \ _2-x \ _1, y \ _2-y \ _1) $. Mit anderen Worten, die Zahlen, die + als $ m = min (x \ _2-x \ _1, y \ _2-y \ _1)) $ sind, werden wie folgt zusammengefasst.

(1) Wenn die Anzahl von + erhöht wird

(1+2+…+m) \times 2 -m=m^2

-Ist das letzte, weil das untere linke Element zweimal gezählt wird.

(2) Wenn die Anzahl von + die Obergrenze erreicht hat

|(x\_2-x\_1)-(y\_2-y\_1)| \times m

Da die Differenz oben erhalten wurde, sollte sie daher (Differenz) +1 sein.

C.py

for _ in range(int(input())):
    x1,y1,x2,y2=map(int,input().split())
    a,b=(x2-x1+1),(y2-y1+1)
    if a>b:
        a,b=b,a
    print((a-2)*(a-1)+(a-1)+(a-1)*(b-a)+1)

D Problem

Ich konnte dieses Problem schnell lösen, aber es war schwierig zu implementieren.

Betrachten Sie den Fall, in dem die Tage in der Reihenfolge von 1 in jedem Monat zugewiesen werden und wenn Sie aufeinanderfolgende $ x $ Tage auswählen, ist die Summe der Tage das Maximum.

Zu diesem Zeitpunkt ist ** der größte Kandidat **, wenn Sie bis zum Ende eines jeden Monats ** auswählen. Da es $ n $ Monate gibt, habe ich festgestellt, dass es mit $ O (n) $ implementiert werden kann, indem ** $ x $ Tage parallel verschoben werden und das Bild ** verwendet wird, um die Unterschiede zu verwalten.

Das Problem bei der Implementierung ist "** Wie viele Monate wählen Sie, wenn Sie das Ende eines Monats wählen " und " Wie viele Tage wählen Sie für einen Monat mit einem ungeraden Datum **?" ". Dies kann implementiert werden, indem in ein vollständig ausgewähltes monatliches Minimum von $ now1 $ und ein Gesamtbetrag von $ now2 $ für diesen Tag sowie ein zusätzliches $ add1 $ für den ausgewählten Tag und ein Gesamtbetrag von $ add2 $ für diesen Tag aufgeteilt wird. Wenn es keinen vollständig ausgewählten Monat gibt, setzen Sie $ now1 = inf $.

Hier wird es implementiert, indem in absteigender Reihenfolge von $ i = n-1 \ rightarrow 0 $ gemäß den folgenden Fällen gearbeitet wird. Nehmen wir außerdem an, dass die Daten, die zusätzlich gesucht werden müssen, $ x $ sind und die Summe der Daten des $ i $ -ten Monats $ a [i] $ ist.

(1) Wenn $ now1 = inf $ oder $ now1 = i + 1 $

In diesem Fall gibt es keinen vollständig ausgewählten Monat. Initialisieren Sie ihn daher mit $ now1 = inf, now2 = 0, add1 = 0, add2 = 0 $ und suchen Sie nach $ check = x $ days.

[1] $ check <d [i] $ Es gibt keinen vollständig ausgewählten Monat und es gibt keine Änderung in $ now1, now2 $. $ add1, add2 $ muss aktualisiert werden, $ add1 = check, add2 = \ sum_ {j = 0} ^ {check-1} (d [i] -j) = \ frac {(2d [i] - check + 1) \ times check} {2} $.

[2] $ check \ geqq d [i] $ Es gibt einen vollständig ausgewählten Monat und $ now1 = i, now2 = a [i], check = x-d [i] $ werden bestätigt. Darüber hinaus kann es vollständig auswählbare Monate geben. Verringern Sie also $ now1 $ und addieren Sie zu $ now2 $, während Sie die while-Anweisung mit $ check \ geqq d [now1-1] $ als Schleifenbedingung drehen. Der Überschuss wird berechnet, indem er in $ add1 und add2 $ eingegeben wird.

(2) Im Fall von $ now1 \ neq inf $ und $ now1 \ neq i + 1 $

$ now1, now2 $ muss nicht initialisiert werden. Setzen wir außerdem $ check = add1 + d [i + 1] $, um zu prüfen, in welchem Monat der Überschuss $ add1 $ verteilt wird. Setzen Sie außerdem 0 für $ add1 und add2 $.

In (1) gab es keinen Monat, der vollständig ausgewählt wurde, also habe ich mit dem $ i $ -ten Monat begonnen, aber in (2) habe ich bereits vollständig bis $ now1 $ ausgewählt. Daher ist als nächstes $ now1-1 $ zu suchen, und eine ähnliche Implementierung kann erreicht werden, indem $ i $ in der Diskussion in (1) durch $ n-1 $ ersetzt wird.

✳︎… Es ist einfach zu implementieren, wenn Sie ** ** Fallklassifizierung, ② Initialisierung, ③ Differenzverarbeitung ** kennen.

D.py

n,x=map(int,input().split())
d=list(map(int,input().split()))
a=[i*(i+1)//2 for i in d]
inf=100000000000
ans=0
#now1:Wie weit bist du gekommen?(Wenn nicht vollständig-1)
now1=inf
#now2:Was ist die Summe der Teile, die vollständig entnommen wurden?
now2=0
#add1:Wie viel wurde hinzugefügt
add1=0
#add2:Was ist die Summe der zusätzlichen Teile genommen?
add2=0
for i in range(n-1,-1,-1):
    if now1==inf or now1==i+1:
        check=x
        now1=inf
        now2=0
        add1=0
        add2=0
        if check<d[i]:
            #now1 funktioniert nicht
            now2=0
            add1=check
            add2=(2*d[i]-check+1)*check//2
        else:
            now1=i
            now2=a[i]
            check-=d[i]
            while check>=d[now1-1]:
                check-=d[now1-1]
                now2+=a[now1-1]
                now1-=1
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
    else:
        #Bei Einnahme löschen
        #check ist ein zusätzlicher Wert
        check=add1+d[i+1]
        add1=0
        add2=0
        now2-=a[i+1]
        if check<d[now1-1]:
            #now1 funktioniert nicht
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
        else:
            while check>=d[now1-1]:
                check-=d[now1-1]
                now2+=a[now1-1]
                now1-=1
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
    #print(now1,now2,add1,add2)
    ans=max(now2+add2,ans)
print(ans)

Nach dem E-Problem

Ich werde diesmal überspringen