[PYTHON] Codeforces Runde # 663 (Div. 2) Bacha Review (8/16)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Persönlich möchte ich nicht so oft unbewertete Zeiten lösen, aber ich habe es nicht bemerkt.

Problem A

Ich war auch überrascht über das Knebelproblem. Hat Kodfo eine solche Tendenz ...?

$ a \ _x + a \ _y \ neq a \ _z $ sollte aus einem beliebigen ($ x, y, z $) bestehen. Dies gilt, wenn sich alle Elemente in derselben Zahlenfolge befinden. Daher müssen Sie nur 1 für die angegebene Anzahl von Elementen ausgeben (obwohl andere Zahlen in Ordnung sind).

A.py

for _ in range(int(input())):
    print(" ".join(map(str,[1]*int(input()))))

B-Problem

Ich glaube, ich habe ein ähnliches Problem mit AtCoder gesehen, aber ich erinnere mich nicht.

Ich dachte darüber nach, ** $ GCD (a, b) $ zu maximieren, um $ LCM (a, b) $ zu minimieren. Da $ GCD (a, b) $ ein Bruchteil von $ n $ ist, wählen Sie den größten Bruchteil von $ N $ ($ X $) ohne $ n $ (✳︎1).

Zu diesem Zeitpunkt ist $ N = X \ mal K $ ($ K $ ist eine ganze Zahl von 2 oder mehr). Wenn $ a = X \ mal Y $ ($ Y $ ist eine positive ganze Zahl kleiner als $ K $), dann ist $ b = X \ mal (K-Y) $. Hier kann gesagt werden, dass sich $ Y $ und $ K-Y $ aus der Bedingung von $ X $ gegenseitig ausschließen, also $ LCM (a, b) = X \ mal Y \ mal (K-Y) $. Und da $ X $ und $ K $ bereits bestimmt wurden, ist $ Y $ positiv und $ LCM (a, b) $ nimmt monoton ** in Bezug auf ** $ Y $ ab, also ist $ Y = K-1 $ Ist das Minimum. Wenn also $ a = X \ mal (K-1), b = X $, gibt $ LCM (a, b) $ dies mindestens aus (✳︎2).

Außerdem wurde (✳︎1) aufgrund meiner Vermutung während des Wettbewerbs nicht gezeigt, aber es kann umgekehrt zu (✳︎2) gezeigt werden.

B.py

for _ in range(int(input())):
    n,m=map(int,input().split())
    a=[input() for i in range(n)]
    ans=0
    for i in range(m-1):
        ans+=(a[n-1][i]=="D")
    for i in range(n-1):
        ans+=(a[i][m-1]=="R")
    print(ans)

C-Problem

Ich wurde von der Tatsache getäuscht, dass es in der Problemstellung weniger als $ 10 ^ {18} $ mal war. In der Realität gibt es maximal zwei Mal.

Zuerst habe ich gierig die Position der Nummer geändert, also habe ich ein Experiment mit Probe 2 durchgeführt. Dann wird es wie folgt.

Mit anderen Worten, aus dem obigen Experiment kann gesagt werden, dass ** es nicht notwendig ist, diejenige zu ändern, die bereits der Position an der Kante entspricht **, und wenn es ** gibt, die dieselbe Position ** ohne die Kante ** hat (Probe) Wie Sie sehen können, muss es anscheinend zweimal ersetzt werden. Es ist auch offensichtlich, dass Sie es nicht einmal austauschen können, aber Sie können auch das Gefühl haben, dass es zweimal ausgetauscht werden kann. Mit anderen Worten, die Sequenz $ a \ _1, a \ _2, ..., a \ _n $ vor dem Austausch wird gegen die Sequenz $ b \ _1, a \ _2, ..., a \ _n $ ausgetauscht, und schließlich wird der Austausch durchgeführt. Es wäre schön zu zeigen, dass es gegen $ 1,2,…, n $ eingetauscht werden kann. Zu diesem Zeitpunkt müssen $ b \ _i \ neq a \ _i $ und $ b \ _i \ neq i $ für jedes $ i $ gelten. Während des Wettbewerbs kam ich zu dem Schluss, dass solche $ b \ _i $ durch den erfolgreichen Austausch mehrerer Zeilen hergestellt werden könnten.

Auch der obige Beweis scheint möglich zu sein, ist aber nicht störend. ** Ich denke, ich kann es zeigen, weil es nur notwendig ist, eine [perfekte Reihenfolge](https://ja.wikipedia.org/wiki/complete Bestellung) Beziehung ** zueinander zu haben. ** Es ist intuitiv, wenn Sie ein kleines Muster von $ n $ anzeigen können, ist es möglich, es mit einem größeren $ n $ zu erstellen **.

Wenn es außer dem Ende niemanden gibt, der mit der Position übereinstimmt, ist es möglich, sie einmal zu ersetzen, und wenn alle Positionen von Anfang an übereinstimmen, ist es nicht erforderlich, sie zu ersetzen, so dass es möglich ist, sie 0 Mal zu ersetzen. ..

C.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if a==[i+1 for i in range(n)]:
        print(0)
        continue
    #Ohne die Kanten
    for i in range(n):
        if a[i]!=i+1:
            break
    for j in range(n-1,-1,-1):
        if a[j]!=j+1:
            break
    #Indexfehler
    for k in range(i,j+1):
        if a[k]==k+1:
            print(2)
            break
    else:
        print(1)

D Problem

Das Debuggen war schwierig und die verbleibende Zeit war kurz, da ich eine gierige Methode mit einer umfangreichen Implementierung verwendete, die richtig berücksichtigt wurde. ** Machen Sie keine gierigen Methoden, deren Gültigkeit nicht nachgewiesen werden kann **.

Erstens verschwinden jedes Mal zwei Zahlen, und eine Zahl verschwindet insgesamt, sodass ** $ [\ frac {n} {2}] $ Zahlen verschwinden **. Erwägen Sie daher, die Summe dieser Zahlen so klein wie möglich zu halten. Das heißt, $ [\ frac {n} {2}] $ Zahlen werden ** wahrscheinlich nicht willkürlich ausgewählt **, also werde ich experimentieren. Dann ist es wie in der folgenden Abbildung gezeigt.

Aus der obigen Abbildung können Sie ersehen, dass beim Löschen von $ [\ frac {n} {2}] $ -Nummern ** die Zahlen nebeneinander nicht gelöscht werden können **. Ordnen Sie die Zahlen auch so an, dass sie nicht nebeneinander liegen ** und $ a \ _1, a \ _3,…, a \ _ {n-2}, a \ _n, a \ _2, a \ _4,…, Es wird ein \ _ {n-3}, ein \ _ {n-1} $. Wenn Sie diese fortlaufenden $ [\ frac {n} {2}] $ -Nummern auswählen, ist keine beliebige Zahl aufeinanderfolgend. Andernfalls können Sie die Zahlen nebeneinander löschen Sie können den Maximalwert einer Reihe von $ [\ frac {n} {2}] $ -Zahlen ($ n $ Straßen) ermitteln, während Sie die Differenz zählen.

D.py

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
    print(-1)
    exit()
if n==1 or m==1:
    print(0)
    exit()
inf=10000000000000
if n==2 or m==2:
    bitcheck=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(1):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*4 for i in range(4)]
    for j in range(4):
        for k in range(4):
            for i in range(2):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==2:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*4 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(4):
                for k in range(4):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
        else:
            for k in range(4):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
    print(min(dp[n-1]))
    exit()
if n==3 or m==3:
    bitcheck=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(2):
                if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
                    bitcheck[j][k]=False
                    break
            else:
                bitcheck[j][k]=True
    bitcalc=[[0]*8 for i in range(8)]
    for j in range(8):
        for k in range(8):
            for i in range(3):
                if ((j>>i)&1)^((k>>i)&1):
                    bitcalc[j][k]+=1
    if n==3:
        n,m=m,n
        b=[list(x) for x in zip(*a)]
    else:
        b=[i for i in a]
    dp=[[inf]*8 for i in range(n)]
    for i in range(n):
        if i!=0:
            for j in range(8):
                for k in range(8):
                    if bitcheck[j][k]:
                        dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
        else:
            for k in range(8):
                dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
    print(min(dp[n-1]))
    exit()

Nach dem E-Problem

Ich werde diesmal überspringen