[PYTHON] Codeforces Round # 654 (Div. 2) Bacha Review (8/18)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Dieses Mal konnte ich es mit einem sehr guten Gefühl lösen. Ich habe Gokan jedoch vermisst, weil ich unterwegs zu Mittag gegessen habe. Ich bin sehr enttäuscht. Ich habe das Gefühl, dass meine Sinne allmählich geschärft werden, deshalb möchte ich weiterhin mein Bestes geben. Ich werde mein Bestes tun, um AtCoder Blue und Codeforces Purple anzustreben, die meine Ziele während der Sommerferien sind.

Problem A

Wenn es eine gerade Anzahl von Stöcken gibt, machen Sie einen Stock mit einer Länge von $ n + 1 $, und wenn es eine ungerade Anzahl von Stöcken gibt, machen Sie einen Stock mit einer Länge von $ n $. Die Anzahl der Sticks beträgt $ [\ frac {n} {2}] $.

Es kann bewiesen werden, indem man die Stöcke der Länge betrachtet, die in aufsteigender Reihenfolge hergestellt werden können, aber ich werde es hier weglassen.

A.py

for _ in range(int(input())):
    n=int(input())
    print(-(-n//2))

B-Problem

Es ist ein Problem, das eine Falle zu sein scheint, aber Sie können die richtige Antwort erhalten, indem Sie jeden Fall sorgfältig klassifizieren.

Erwägen Sie zunächst, aufeinanderfolgende $ n $ Tage für die Verbindung auszuwählen, aber ** eine Woche ** stellt immer eine Verbindung her, wenn $ n $ Tage enthalten sind, während ** mehrere Wochen ** Wenn Sie sich überspannen, sind möglicherweise $ n $ Tage nicht verbunden. Wenn eine Woche $ i (1 \ leqq i \ leqq r) $ Tage ist, betrachten Sie daher den Fall von $ i \ geqq n $ und den Fall von $ i <n $.

(1) Im Fall von $ i \ geqq n $ Wenn Sie aufeinanderfolgende $ n $ Tage für die Verbindung auswählen, wird dies wie in der folgenden Abbildung gezeigt, und für jedes $ i $ entspricht die Form $ 1 $, wenn Sie sich parallel bewegen, also wenn $ r \ geqq n $, 1 Wenn $ r <n $ auf der Straße ist, gibt es 0 Straßen.

(2) Wenn $ i <n $ Wenn Sie aufeinanderfolgende $ n $ Tage für die Verbindung auswählen, müssen Sie mehrere Wochen wie folgt umfassen: Daher können Formen, die beim parallelen Verschieben nicht identisch sind, am ersten Tag aufeinanderfolgender $ n $ Tage ** unterschieden werden, was zu $ i $ Straßen führt.

Da es sich um $ 1 \ leqq i \ leqq min (n-1, r) $ handelt, ist $ \ sum \ _ {i = 1} ^ {min (n-1, r)} i = \ _ {min (n, r) +1)} C \ _2 $ ist die Antwort. Außerdem habe ich einen Fehler im Bereich von ** $ i $ ** gemacht. Ich habe nicht in die Stichprobe gepasst.

B.py

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

C-Problem

Der erste Gasttyp wird aus den meisten Cookies ausgewählt, und der zweite Gasttyp wird aus der geringsten Anzahl von Cookies ausgewählt. Überlegen Sie zu diesem Zeitpunkt, ob die Bestellung des Gastes so entschieden werden kann, dass bei der Auswahl eines Cookies für jeden Gast kein Cookie mehr vorhanden ist.

Erstens scheint der zweite Gasttyp ** nur wenige Möglichkeiten zu haben, da er den kleineren Cookie ** wählt. Deshalb möchte ich so viele kleinere Cookies wie möglich behalten. Daher dachte ich, dass es besser wäre, zuerst den zweiten Gasttyp auszuwählen, und denke, dass die Anzahl der Cookies, die vom zweiten Gasttyp ausgewählt werden können, höchstens $ min (a, b) $ beträgt. Es war. Wenn der zweite Gasttyp ein Cookie auswählt, ** kann die verbleibende Anzahl des kleineren Cookies nicht zweimal ausgewählt werden **, sodass $ min (a, b) $ das maximal zu wählende Cookie ist. Es wird die Anzahl der Blätter sein. Wenn es sich also um $ m \ leqq min (a, b) $ handelt, kann der zweite Gasttyp immer den kleineren Cookie auswählen und den Cookie verlassen. Außerdem bleibt $ (min (a, b) -m) + max (a, b) = a + bm $ Cookie in **, nachdem der zweite Gast ausgewählt wurde, aber der Rest Alle Cookies des ersten Typs können vom ersten Gasttyp ausgewählt werden. Wenn es sich also um $ a + bm \ leqq n $ handelt, kann der erste Gasttyp auch das Cookie auswählen. Aus dem oben Gesagten sollte "Nein" ausgegeben werden, wenn $ m> min (a, b) $ oder $ a + b <n + m $, und "Ja" sollte zu anderen Zeiten ausgegeben werden.

C.py

for _ in range(int(input())):
    a,b,n,m=map(int,input().split())
    if m>min(a,b):
        print("No")
    elif n+m>a+b:
        print("No")
    else:
        print("Yes")

D Problem

Ich persönlich mag es, Symmetrie zu verwenden, weil es eine bessere Sichtbarkeit bietet (obwohl mein Geschmack wahrscheinlich anders ist).

Das Problem besteht darin, $ f (A) = (max (R) -min (R)) ^ 2 + (max (C) -min (C)) ^ 2 $ so klein wie möglich zu machen. Zunächst ist es leicht zu verstehen, wenn Sie über den eindimensionalen Fall nachdenken. Wenn Sie jedoch die Anzahl der Einsen so gleichmäßig wie möglich teilen, wird $ f (A) $ kleiner.

Überlegen Sie nun, $ k $ 1 in jeder Zeile und Spalte so gleichmäßig wie möglich anzuordnen. Bei gleichmäßiger Verteilung habe ich darüber nachgedacht, während ich beobachtet habe, dass ich mir der Symmetrie bewusst bin und einige Regeln festgelegt habe. Außerdem werden $ max (R) -min (R) $ und $ max (C) -min (C) $ nicht 0, wenn $ k % n! = 0 $, also ** setzen Sie sie jeweils auf 1. Betrachten Sie die gewünschte Platzierung **. Dann können Sie sehen, dass es nach dieser Regel angeordnet werden kann, indem Sie in der folgenden Abbildung in der Reihenfolge ① → ② → ③ →… verteilen.

Zunächst kam ich im Fall von (1) auf die Idee, weil es sich um eine diagonale Komponente handelt und eine hohe Symmetrie aufweist. Außerdem dachte ich, ich sollte 1 in die ** diagonale Komponente ** (grüner Teil) daneben setzen, aber zu diesem Zeitpunkt auch $ max (R) -min (R) $ Und $ max (C) -min (C) $ ändern sich immer, während 0 oder 1 beibehalten werden. Dies liegt daran, dass die ** Zeilen und Spalten in den blauen, grünen und gelben Komponenten jeweils $ n $ sind und sich alle voneinander unterscheiden **, sodass die Summe nicht mehr als 2 größer als die anderen Zeilen und Spalten ist. ist. Daher kann verallgemeinert werden, dass sie so angeordnet sein sollten, dass sie sich alle voneinander unterscheiden, und dass sie in der Reihenfolge in den diagonalen Komponenten wie in der obigen Abbildung angeordnet sein sollten. Diese Komponente kann auch als $ (i, (i + j) % n) $ in $ 0 \ leqq i, j \ leqq n-1 $ ausgedrückt werden, und $ i, j $ wird verschoben, um nach $ k $ zu gelangen. Alles was Sie tun müssen, ist die Ausgabe, in der 1 platziert ist.

D.py

for _ in range(int(input())):
    n,k=map(int,input().split())
    ans=[[0]*n for i in range(n)]
    f=False
    for j in range(n):
        for i in range(n):
            if k==0:
                f=True
                break
            k-=1
            ans[i][(i+j)%n]=1
        if f:
            break
    r=[sum(ans[i]) for i in range(n)]
    mar,mir=max(r),min(r)
    c=[sum([ans[i][j] for i in range(n)]) for j in range(n)]
    mac,mic=max(c),min(c)
    print((mar-mir)**2+(mac-mic)**2)
    for i in range(n):
        print("".join(map(str,ans[i])))

E1-Problem

Ich habe zu Mittag gegessen und konnte es nicht umsetzen, tut mir leid! !!

** Ich gehe davon aus, dass du alle Feinde besiegst **. Wenn du also zu Beginn $ x $ Süßigkeiten hast, kämpfe gegen den $ i (0 \ leqq i \ leqq n-1) $ -ten Feind Manchmal habe ich $ x + i $ Süßigkeiten. Da es nur notwendig ist, mehr Süßigkeiten als der Feind zu haben, kann die $ i $ -te Person gewinnen **, wenn der Feind ** $ x + i $ oder weniger Süßigkeiten hat. Wie Sie einen solchen Feind auswählen können, finden Sie unter bisect_right, wenn Sie ** die Anzahl der feindlichen Süßigkeiten sortieren ** (ich habe 1WA ohne Sortierung ausgegeben ...). Da die Person vor der ** $ i $ -ten Person bereits die Feinde der $ i $ -Person ** ausgewählt hat, kann tatsächlich "($ x + i $ oder weniger Süßigkeiten) ausgewählt werden. Anzahl der Feinde) - $ i $ "Personen. Wenn es eine Person gibt, deren Wert weniger als $ 0 $ beträgt, gibt es 0 Möglichkeiten, einen Feind auszuwählen, und er ist durch $ p $ teilbar, sodass das Thema nicht erfüllt wird. Wenn $ x \ geqq max (a) $, ** ein beliebiger Feind ausgewählt werden kann, also $ n! $ Street **, und wenn $ x <min (a) $, **, gibt es keine Auswahlmethode. Ab $ 0 $ street ** sind beide durch $ p $ teilbar, daher sollten Sie nach einem suchen, der nicht durch $ p $ im Bereich von $ min (a) \ leqq x <max (a) $ teilbar ist. ..

E.py

n,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=[]
from bisect import bisect_right
for i in range(min(a),max(a)):
    for j in range(n):
        b=bisect_right(a,i+j)-j
        if b<=0:
            break
        elif b%p==0:
            break
    else:
        ans.append(i)
print(len(ans))
print(" ".join(map(str,ans)))

Nach dem E2-Problem

Ich werde diesmal überspringen