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

Les résultats de cette fois

スクリーンショット 2020-10-31 8.39.22.png

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.

IMG_0732.jpg

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.

Recommended Posts

Codeforces Round # 658 (Div.2) Examen Bacha (7/29)
Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 666 (Div.2) Examen Bacha (9/2)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 612 (Div.2) Examen Bacha (10/2)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 675 (Div.2) Examen Bacha (10/30)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles