Code de l'éducation forces Round 92 Bacha Review (7/30)

résultat

スクリーンショット 2020-07-31 13.49.47.png

Impressions

** Cette fois, j'ai fait une grosse erreur parce que la politique était appropriée ** ou ** j'ai abandonné parce que je pensais que ce serait difficile **. En conséquence, j'ai pu résoudre 5 questions (bien que j'aie vu des réponses), donc j'aimerais les résoudre lors de la production réelle.

Voir également @ e869120 cet article.

(1) Divisez le processus autant que possible et divisez-le en fonctions (2) Laisser non seulement une note de réflexion mais aussi une note de mise en œuvre ③ Correspondre au mémo d'implémentation en commentant selon ②

J'ai senti que c'était important. Je veillerai à le mettre en œuvre en gardant cela à l'esprit.

Problème A

Tous les $ x $, $ y $, $ lcm (x, y) $ sont compris entre $ l $ ou plus et $ r $ ou moins, et ** $ lcm (x, y) $ est le maximum parmi eux ** Ce sera. De plus, $ lcm (x, y) $ est un multiple de $ x $ et sa valeur minimale est $ 2x $ à partir de la condition que $ x <y $. Par conséquent, lorsque $ x = l, y = 2l, lcm (x, y) = 2l $, vous devriez vérifier si $ 2l $ est inférieur à $ r $.

A.py


t=int(input())
for _ in range(t):
    l,r=map(int,input().split())
    x,y=l,2*l
    if y<=r:
        print(x,y)
    else:
        print("-1 -1")

Problème B

L'ordre de Janken change en fonction de la position, mais ** $ c_1c_2… c_n $ jouera chacun $ n $ fois contre une autre main ($ s_1s_2… s_n $) ** (** Paraphrase du sujet et de l'objet) **). Par conséquent, pour $ c_i $, vous pouvez jouer contre $ s_1s_2… s_n $ et choisir le coup gagnant. Si «R» est le plus dans $ s_1s_2… s_n $, «P» et «S» sont les premiers. S'il y en a beaucoup, "R" et "P" devraient être les plus nombreux, et s'il y en a beaucoup, "S" devrait être utilisé. De plus, comme il se compose de n'importe quel $ i $, vous pouvez afficher la chaîne de caractères du nombre de fois de Janken.

B.py


t=int(input())
for i in range(t):
    S=input()
    l=len(S)
    r=S.count("R")
    s=S.count("S")
    p=S.count("P")
    m=max(r,s,p)
    if m==r:
        print("P"*l)
    elif m==s:
        print("R"*l)
    else:
        print("S"*l)

Problème C

Je pensais qu'il ne devrait pas y avoir de personnes excédentaires qui lisent mal, mais si vous regardez de près, cela dit qu'il y a peut-être des personnes excédentaires. C'est une réflexion.

Dans ce cas, ** les programmeurs les plus qualifiés doivent être combinés afin de dépasser ** $ x $. De plus, il peut y avoir des combinaisons de programmeurs qui ne dépassent pas $ x $ même à la fin, mais vous pouvez ignorer ces combinaisons.

Aussi, avec cette méthode gourmande, ** le plus petit nombre de personnes peut former un groupe **, on peut donc dire que le nombre de groupes est le plus grand.

C.py


t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    now=[100000000000,0]
    for i in range(n):
        now=[min(now[0],a[i]),now[1]+1]
        if now[0]*now[1]>=x:
            d.append(now)
            now=[100000000000,0]
    print(len(d))

Problème D

J'ai également mal lu cela et j'ai rendu difficile de penser que ** Berserk peut spécifier deux personnes discontinues **. En fait, ce n'est pas si difficile car il n'y a que deux personnes d'affilée.

Les personnes qui sont continues peuvent être vaincues, alors faites attention à la partie où la personne qui bat est continue ** (ci-après dénommée partie continue). De plus, si vous voulez vaincre la dernière personne restante dans une partie continue avec Berserk, l'une des personnes non vaincues ($ L $ et $ R $) qui prend cette partie en sandwich doit avoir ** plus de pouvoir que cette personne * * Donc, nous avons besoin des informations de la personne qui les prend en sandwich.

Ici, si la longueur de la partie continue est divisée par $ k $ et qu'un reste apparaît, il faut réduire le reste par Berserk, et à ce moment, la personne avec la puissance maximale dans la partie continue ($ X $) Il est préférable de sélectionner et de vaincre les personnes situées des deux côtés.

De plus, si $ X $ a une puissance supérieure à $ L $ et $ R $, vous devez ** vaincre ce $ X $ avec Fireball **, et Fireball ne peut pas être utilisé ($ \ leftrightarrow $ longueur de la partie continue). Lorsque (est plus court que $ k $) et que l'ordre des personnes restantes est différent, le sujet n'est pas satisfait, donc -1 doit être affiché.

Au moment de l'implémentation, déterminez si $ X $ a une puissance plus élevée que $ L $ et $ R $ → S'il est déterminé, vaincre-le d'abord avec Fireball → Diviser la longueur de la partie continue par $ k $ Battez la partie avec Berserk → Répétez le reste avec Fireball et Berserk, ce qui est plus efficace, et ce sera plus facile.

Quand je l'ai résolu ** je n'ai pas pu organiser l'implémentation **, donc le code est un peu compliqué. Je veux aussi pouvoir faire attention à la propreté de la mise en œuvre.

D.py


n,m=map(int,input().split())
x,k,y=map(int,input().split())
a=list(map(int,input().split()))
c=list(map(int,input().split()))
b=set(c)
d=[]
now=[]
for i in range(n):
    if a[i] not in b:
        now.append(i)
        if i==n-1:
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
    else:
        if now!=[]:
            #Indice de bord et max(Le bord est-1,n peut être)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#Celui dont la position n'est pas en ordre
now=0
lc=len(c)
for i in range(n):
    if a[i]==c[now]:
        now+=1
        if now==lc:
            break
else:
    exit(print(-1))
l=len(d)
ans=0
for i in range(l):
    e=d[i]
    f=e[2]-e[0]-1
    if e[0]==-1:
        m=a[e[2]]
    elif e[2]==n:
        m=a[e[0]]
    else:
        m=max(a[e[0]],a[e[2]])
    if m>a[e[1]]:
        ans+=(f%k*y)
        ans+=min((f//k)*x,(f//k)*k*y)
    else:
        if f<k:exit(print(-1))
        ans+=(f%k*y)
        #Je dois les vaincre une fois avec k
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

Problème E

Envisagez de trouver $ x + (y-1) d = y + (x-1) d \ (mod \ w) $ sous $ 1 \ leqq x, y \ leqq min (d, m) $. Ici, vous pouvez effectuer une ** transformation d'expression ** avec $ x + (y-1) d = y + (x-1) d \ leftrightarrow (d-1) (x-y) = 0 $. Par conséquent, quand $ d-1 = 0 \ (mod \ w) $, tout $ x, y $ satisfera cela, donc si vous définissez $ z = min (d, m) $, alors $ \ _ {z } C \ _2 $ Ce sera tel quel.

Ici, quand ** $ d-1 \ neq 0 \ (mod \ w) $, cela semble être $ x = y \ (mod \ w) $, mais c'est faux **. Correctement, $ v = gcd (w, d-1) $ est $ x = y \ (mod \ v) $ (✳︎).

<détails>

** (✳︎) description ** </ summary>

Lorsque $ XY = 0 \ (mod \ m) $, il peut être divisé dans les deux cas suivants.

(1) Lorsque $ X = 0 \ (mod \ m) $ (2)Y=0 \ (mod \ \frac{m}{gcd(m,X)})

(2) est intuitivement facile à comprendre étant donné que $ XY = 0 $ est valable lorsque $ m = 6 $ et $ X = 2, Y = 3 $.


Par conséquent, ** $ mod \ v $ vaut $ 1 $ ~ $ min (d, m) $, et il y a plusieurs valeurs différentes **, mais ** $ mod \ v $ est difficile à penser au début de 1 * * Alors, considérez combien de façons il y a pour $ 0 $ ~ $ min (d, m) -1 $.

De plus, si vous définissez $ X = [\ frac {min (d, m) -1} {v}], Y = (min (d, m) -1) % v $, alors $ 0 $ ~ $ Y \ ( Dans le cas de mod \ v) $, il y a $ X + 1 $ façons, donc il y a $ _ {X + 1} C_2 $ façons de choisir respectivement $ x et y $. De plus, lorsque $ Y + 1 $ ~ $ v-1 \ (mod \ v) $, il y a des rues $ X $, vous pouvez donc choisir respectivement $ x et y $ $ \ _ {X} C \ _2 $. Ce sera une rue.

Par conséquent, à partir de ce qui précède, comment sélectionner le total $ x, y $ est $ \ _ {X + 1} C_2 \ times (Y + 1) - \ _ {X} C \ _2 \ times Y $, et ceci est affiché. Simplement fais-le.

E.py


t=int(input())
from math import gcd
for _ in range(t):
    m,d,w=map(int,input().split())
    z=min(d,m)
    d-=1
    if d%w==0:
        print(z*(z-1)//2)
        continue
    w//=gcd(d,w)
    z-=1
    x=z//w
    y=z%w+1
    print(x*(x-1)//2*(w-y)+(x+1)*x//2*y)

Après problème F

Je ne peux pas résoudre cette fois.

Recommended Posts

Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 94 Bacha Review (9/3)
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 # 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 # 610 (Div.2) Critique Bacha (10/5)
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 # 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 # 613 (Div.2) Examen Bacha (10/1)
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 # 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)
Code de l'Éducation Forces Round 87
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
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
Codeforces Round # 609 (Div.2) (jusqu'à B)