[PYTHON] Codeforces Round # 675 (Div. 2) Bacha Review (30.10.)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich konnte die Problemstellung von Problem A nicht gut verstehen, und ich habe im Experiment von Problem C einen dummen Fehler gemacht, und ich hatte große Probleme.

Ich muss hier am meisten umschalten, deshalb werde ich wiederholt üben, um die Genauigkeit zu verbessern.

Problem A

Ein nicht zurückgezogenes $ n $ Quadrat kann erstellt werden, indem die $ n $ Punkte entsprechend verbunden werden, wenn sie nicht auf einer geraden Linie liegen. Da $ \ leftrightarrow $ (nicht auf einer geraden Linie) (die längste Seite ist kleiner als die Summe der anderen Seiten), ist $ d = a + b + c- für das gegebene $ a, b, c $. Es sollte 1 $ sein.

A.py

for _ in range(int(input())):
    x=list(map(int,input().split()))
    print(sum(x)-1)

B-Problem

** Es ist gut, wenn es in Zeilen- und Spaltenrichtung kreisförmig ist **. Daher müssen ** bis zu 4 Plätze ** dieselbe Nummer haben. Wenn für die $ (i, j) $ -Komponente $ n $ eine ungerade Zahl und $ i = [\ frac {n} {2}] $ ist, gibt es keine Komponente, die in Spaltenrichtung dieselbe Zahl haben muss, und $ m Es ist auch ** beachten **, dass wenn $ ungerade ist und $ j = [\ frac {m} {2}] $, es keine Komponenten gibt, die in Zeilenrichtung dieselbe Nummer haben müssen.

Daher teilen Sie gemäß der obigen Regel ** durch eine Komponente mit derselben Nummer (✳︎1) ** und dann ** (✳︎), welche Komponente dieselbe Nummer hat, so dass sie dem Medianwert entspricht. Die Anzahl der Operationen wird durch Betrieb von +1 oder -1 minimiert. Daher sollte die Summe davon die Antwort sein.

(✳︎1)… Um sich in dieselben Komponenten zu unterteilen, speichern Sie einfach die nicht aktivierten Komponenten in einer Matrix und scannen Sie die Komponenten aller Matrizen.

(✳︎2)…f(x)=\sum_{i} |a\_i-x|Minimierena\_iAuf den Medianwert beim Anordnen in aufsteigender ReihenfolgexEs ist Zeit zu tun. Ich kann das beweisen, aber ich werde den Beweis weglassen, weil er berühmt ist.

B.py

for _ in range(int(input())):
    n,m=map(int,input().split())
    mat=[list(map(int,input().split())) for i in range(n)]
    check=[[0]*m for i in range(n)]
    segments=[]
    for i in range(n):
        for j in range(m):
            if check[i][j]==0:
                seg_sub=[]
                check[i][j]=1
                seg_sub.append(mat[i][j])
                if n%2==0 or i!=n//2:
                    check[n-1-i][j]=1
                    seg_sub.append(mat[n-1-i][j])
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        check[n-1-i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                        seg_sub.append(mat[n-1-i][m-1-j])
                else:
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                segments.append(seg_sub)
    ans=0
    for i in segments:
        seg=sorted(i)
        m=len(seg)//2
        for i in seg:
            ans+=abs(i-seg[m])
    print(ans)

C-Problem

(Wenn im Folgenden die $ i $ -Ziffer erwähnt wird, ist sie 0-indiziert und der Wert dieser Ziffer ist $ s [i] $.)

Für solche Probleme ** ist es gut, den Beitrag jeder Ziffer ** zu berücksichtigen. Wenn die $ i $ -Ziffer $ 10 ^ k $ in $ i \ geqq k $ ist, kann der Beitrag aus der folgenden Abbildung berechnet werden.

Aus der obigen Abbildung ergibt sich ein Beitrag von $ k \ mal 10 ^ k \ mal s [i] $. Daher gilt für alle $ i $ und $ k $:

\sum_{k=0}^{n-2} \sum_{i=k}^{n-1} k \times 10^k \times s[i] \leftrightarrow \sum_{k=0}^{n-2} k \times 10^k \sum_{i=k}^{n-1} s[i]

Daher hängt ** die Berechnung der inneren Summe nicht von $ k $ ab, so dass sie vorberechnet werden kann ** und die kumulative Summe von der gegenüberliegenden Seite berücksichtigt werden kann ($ O (n) $). Wenn Sie die Vorberechnung durchführen, können Sie auch die äußere Summe mit $ O (n) $ berechnen, sodass der Gesamtbetrag der Berechnung $ O (n) $ beträgt.

C.py

mod=10**9+7
s=list(map(int,input()))[::-1]
n=len(s)
if n==1:
    print(0)
    exit()
#10^zur k-ten Macht
po=[1]
for i in range(n):
    po.append(po[-1]*10%mod)
#S_Kumuliert aus der umgekehrten Reihenfolge von i
si=[0]*n
si[n-1]=s[n-1]
for i in range(n-2,-1,-1):
    si[i]=si[i+1]+s[i]
ans=0
for k in range(n-1):
    ans+=((k+1)*si[k+1])*po[k]
    #print(ans)
    ans%=mod
for k in range(n-1):
    ans+=s[k]*((n-1-k)*(n-1-k-1)//2+(n-1-k))*po[k]
    #print(ans)
    ans%=mod
#print()
print(ans)

Nach D Problem

Ich werde diesmal nicht lösen.