[PYTHON] Codeforces Runde # 609 (Div. 2) Bacha Review (10/6)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe versucht, die Fehlinterpretation von gestern zu korrigieren, aber ich habe sie aufgrund eines C-Problems falsch gelesen. Es ist zu eng ... ** Wenn Sie es nicht in 30 Minuten lösen können, brauchen Sie möglicherweise den Mut, es schnell zu schneiden **.

Problem A

Ich werde es bequem machen. Da es sich um eine Subtraktion von Zahlen handelt, ** achten Sie auf Gerade und Ungerade **.

Wenn $ n $ gerade ist, sind sowohl $ a als auch b $ gerade. Wenn beispielsweise $ b = 4 $ ist, ist $ a $ sogar größer als $ 4 $, sodass das Thema zufrieden ist.

Wenn $ n $ ungerade ist, ist einer von $ a und b $ gerade und der andere ungerade. Wenn beispielsweise $ b = 9 $ ist, ist $ a $ sogar größer als $ 9 $, sodass das Thema zufrieden ist.

A.py

n=int(input())
if n%2==0:
    print(n+4,4)
else:
    print(n+9,9)

B-Problem

Sie können sie sortieren, um zu überlegen, wie viele Reste sich in ** $ a $ und $ b $ ** befinden, und das Problem unter der Annahme lösen, dass die Antwort unter den Bedingungen immer gültig ist. Beachten Sie auch, dass $ m $ bis zu 10 ^ 9 Möglichkeiten haben kann, sodass das Hinzufügen von jeweils 1 $ 10 ^ 9 $ zeitliche Berechnungen erfordert.

Im Ausgangszustand wird das Element im Wörterbuch in der Form gespeichert, dass der Rest von $ x $ $ y $ enthält. Da ich in aufsteigender Reihenfolge des Restes speichern möchte, speichere ich nach dem Generieren des Wörterbuchs die Menge der (Rest, Anzahl) Paare in aufsteigender Reihenfolge des Restes ($ c, d ) ( c, d $ sind $). Entspricht a und b $.). Zu diesem Zeitpunkt sind die Längen von $ c und d $ gleich und überschreiten $ n $ nicht.

Fügen Sie zu diesem Zeitpunkt $ x $ zu jedem Element hinzu und dividieren Sie durch $ m $, um das Minimum $ x $ zu ermitteln, das für die Übereinstimmung der verbleibenden Reste $ a $ und $ b $ erforderlich ist. Konzentrieren Sie sich hier auf das letzte Element von ** $ a $ (maximaler Rest) **, und wenn Sie mehrere Zahlen hinzufügen, ist der nächste Satz, der übereinstimmen kann, der erste von ** $ b $. Wenn es mit dem Element von übereinstimmt (der Rest ist der kleinste) **. Entfernen Sie daher das letzte Element von $ a $ und fügen Sie es erneut als erstes Element von $ a $ hinzu, um den ** Unterschied zu ermitteln, der für diese Operation erforderlich ist **. Außerdem ist der Anfangswert $ x = 0 $, die Differenz wird der Reihe nach zu $ x $ addiert und $ x $, wenn $ a und b $ addiert werden, bis sie übereinstimmen, wird ausgegeben.

B.py

from collections import Counter
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#0,1,Sortieren nach dem Rest von ...
#Verschieben Sie einfach ein, um dies zu erreichen
#Höchstens n Mal
c=sorted([list(i) for i in list(Counter(a).items())],key=lambda x:x[0])
d=sorted([list(i) for i in list(Counter(b).items())],key=lambda x:x[0])
n=len(c)
#Löschen Sie die Rückseite und kleben Sie sie nach vorne(Differenzmanagement)
x=0
for i in range(n):
    p=c.pop(-1)
    #Es ist möglicherweise nicht notwendig, herumzugehen
    dp=(d[0][0]+m-p[0])%m
    x+=dp
    c.insert(0,p)
    #print(c,d)
    for j in range(n):
        c[j][0]+=dp
        c[j][0]%=m
    if c==d:
        print(x%m)
        break

C-Problem

Ich habe es falsch verstanden und überflutet ...

(Die $ i $ -Ziffer (0-indiziert) vom Anfang der angegebenen Zahl ist $ a \ _i $, und die $ i $ -Ziffer vom Anfang der endgültigen Zahl ist $ b \ _i $. .)

$ a \ _i = a \ _ {i + k} $ macht eine ** mysteriöse Fehlinterpretation **, die nur in einer Entfernung von $ k $ und $ a \ _i = a \ _ {i + 2k} $ gilt Ich dachte es müsste nicht sein. Warum….

Mit anderen Worten, wenn $ a \ _i = a \ _ {i + k} $ gilt, haben alle Ziffern mit dem gleichen Rest nach Division durch ** $ k $ den gleichen Wert **. Wenn Sie also $ b \ _i = a \ _i $ in $ 0 \ leqq i \ <k $ festlegen, wird $ b \ _i $ eindeutig für $ i \ geqq k $ bestimmt.

Wenn Sie nun $ i \ geqq k $ vom kleinsten von $ i $ aus betrachten, achten Sie auf die Ziffer, die zu $ b \ _i \ \ neq a \ _i $ wird. Das heißt, wenn ** $ b \ _i > a \ _i $ zuerst erscheint, dann gilt $ b> a $ **. Es gibt auch kein kleineres $ b $ als dieses, also geben Sie dies als Antwort aus. Wenn umgekehrt ** $ b \ _i \ <a \ _i $ zuerst erscheint, muss ** eine der Ziffern um +1 erhöhen. Wenn +1 hinzugefügt wird, werden alle Ziffern mit demselben Rest geteilt durch $ k $ um +1 erhöht. ** Unabhängig davon, welche Restziffer in $ b \ _i (i \ <k) $, $ b \ um +1 hinzugefügt wird _i> a \ _i $ gilt **. Daher ist es am besten, +1 zu der $ i $ -Ziffer hinzuzufügen, wobei $ i \% \ k = k-1 $ gilt und $ b> a $ gilt. Wenn es keine Ziffer gibt, die zu $ b \ _i \ \ neq a \ _i $ wird, ist $ b = a $, sodass das Subjekt zufrieden ist.

C.py

#Ich werde mir den Rest ansehen

#Ich habe alle Themen falsch verstanden
#Ich dachte es wäre nur einmal
n,k=map(int,input().split())
a=list(map(int,input()))
ans=[-1]*n
upper=False
lower=False
#Aktualisierungen erfolgen unten und oben
#Ist es in Ordnung, dass das Update stattfindet?
for i in range(k):
    ans[i]=a[i]
for i in range(k,n):
    ans[i]=ans[i-k]
    if ans[i]==a[i]:
        pass
    elif ans[i]>a[i]:
        #Wenn es zuerst oben wird
        #Du musst dich nicht ändern
        if lower==False and upper==False:
            upper=True
    else:
        #Wenn Sie zuerst niedriger werden
        #Ändern Sie einfach den unteren Teil
        #Wird es überschreiten, wenn es geändert wird?
        if lower==False and upper==False:
            lower=True
            #Ändern Sie denjenigen, der das Beste getan hat
            #9 ist nicht gut
            #Darunter ist 0
            for j in range(k-1,-1,-1):
                if ans[j]!=9:
                    break
            for l in range(i+1):
                if l%k==j:
                    ans[l]+=1
                elif l%k>j:
                    ans[l]=0

print(n)
print("".join(map(str,ans)))

D Problem

Ich dachte über DP und eine gute Konfigurationsmethode nach, aber es scheint, dass es ein Wissensproblem war. Ich denke, es kann nicht geholfen werden, wenn dies fallen gelassen wird.

** Es scheint am besten, Dominosteine in einem Schachbrettmuster zu verbreiten ** (Referenz).

Wenn Sie ein Schachbrettmuster in Schwarzweiß erstellen, können Sie feststellen, dass es kleiner oder gleich min ist (Anzahl der weißen Quadrate, Anzahl der schwarzen Quadrate) (✳︎). Darüber hinaus besteht die Antwort darin, den Maximalwert zu finden, der als min angezeigt werden kann (Anzahl der weißen Zellen, Anzahl der schwarzen Zellen). Siehe hier für den Beweis. Ich denke, es wird auf intuitive Weise gezeigt.

D.py

n=int(input())
a=list(map(int,input().split()))
#Ich weiß es nicht
#Dominosteine ausbreiten → In einem Schachbrettmuster auftragen(Was?)
w,b=0,0
for i in range(n):
    if i%2==0:
        w+=a[i]//2
        b+=a[i]-a[i]//2
    else:
        b+=a[i]//2
        w+=a[i]-a[i]//2
print(min(b,w))

Nach dem E-Problem

Ich werde diesmal überspringen.