[PYTHON] Codeforces Round # 675 (Div.2) Examen Bacha (10/30)

Les résultats de cette fois

Impressions de cette époque

Je ne pouvais pas bien comprendre l'énoncé du problème du problème A, et j'ai fait une erreur stupide dans l'expérience du problème C, et j'ai eu beaucoup de problèmes.

J'ai le plus besoin de basculer ici, je vais donc m'entraîner à plusieurs reprises pour améliorer la précision.

Problème A

Un carré $ n $ non rétracté peut être créé en reliant les points $ n $ de manière appropriée s'ils ne sont pas sur une ligne droite. De plus, puisque $ \ leftrightarrow $ (pas sur une ligne droite) (le côté le plus long est inférieur à la somme des autres côtés), $ d = a + b + c- pour les $ a, b, c $ donnés. Cela devrait être de 1 $.

A.py

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

Problème B

** C'est bien s'il s'agit d'une circulaire dans le sens des lignes et dans le sens des colonnes **. Par conséquent, ** jusqu'à 4 places ** doivent avoir le même numéro. Aussi, pour le composant $ (i, j) $, lorsque $ n $ est un nombre impair et $ i = [\ frac {n} {2}] $, il n'y a pas de composant qui doit être le même nombre dans le sens de la colonne, et $ m Il est également ** note ** que lorsque $ est impair et $ j = [\ frac {m} {2}] $, il n'y a pas de composants qui doivent avoir le même nombre dans le sens des lignes.

Par conséquent, selon la règle ci-dessus, ** divisez par le composant qui a le même nombre (✳︎1) **, puis ** (✳︎) quel composant a le même nombre afin qu'il soit égal à la valeur médiane. Le nombre d'opérations est minimisé en opérant +1 ou -1. Par conséquent, le total de ceux-ci devrait être la réponse.

(✳︎1)… Pour diviser en les mêmes composants, il suffit de sauvegarder les composants non vérifiés dans une matrice et de scanner les composants de toutes les matrices.

(✳︎2)…f(x)=\sum_{i} |a\_i-x|Minimisera\_iÀ la valeur médiane lors de l'organisation dans l'ordre croissantxIl est temps de faire. Je peux le prouver, mais j'omettrai la preuve parce qu'elle est célèbre.

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)

Problème C

(Ci-après, lorsque le chiffre $ i $ est mentionné, il est indexé à 0 et la valeur de ce chiffre est $ s [i] $.)

Pour de tels problèmes **, il est bon de considérer la contribution de chaque chiffre **. Lorsque le chiffre $ i $ est de 10 $ ^ k $ en $ i \ geqq k $, la contribution peut être calculée à partir de la figure ci-dessous.

D'après la figure ci-dessus, la contribution est $ k \ fois 10 ^ k \ fois s [i] $. Par conséquent, pour tout $ i $ et $ 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]

Par conséquent, ** le calcul de la somme intérieure ne dépend pas de $ k , il peut donc être pré-calculé **, et la somme cumulée du côté opposé peut être considérée ( O (n) $). De plus, si vous faites le pré-calcul, vous pouvez également calculer la somme extérieure avec $ O (n) $, de sorte que le montant total du calcul sera $ O (n) $.

C.py

mod=10**9+7
s=list(map(int,input()))[::-1]
n=len(s)
if n==1:
    print(0)
    exit()
#10^à la kème puissance
po=[1]
for i in range(n):
    po.append(po[-1]*10%mod)
#S_Cumulable à partir de l'ordre inverse de 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)

Problème après D

Je ne résoudrai pas cette fois.