[PYTHON] Codeforces Round # 645 (Div.2) Critique Bacha (9/10)

Les résultats de cette fois

Impressions de cette époque

Cette fois, l'ordinateur s'est figé et a redémarré à plusieurs reprises, ce qui n'a donc pas été très utile. Cependant, je pense que j'ai pu résoudre le problème D en moins de temps, alors j'aimerais continuer à faire de mon mieux.

Problème A

Je n'aime pas vraiment les phrases à problèmes, mais il est bon de penser à disposer les carreaux.

Disposez les tuiles $ 1 \ fois 2 $. Quand $ n \ times m $ est pair, vous pouvez simplement aligner les tuiles, donc $ \ frac {n \ times m} {2} $ est la réponse. Lorsque $ n \ times m $ est impair, même s'ils sont bien disposés, il restera des tuiles $ 1 \ fois 1 $, donc des tuiles supplémentaires seront nécessaires. $ \ Frac {n \ times m -1} {2} + 1 $ Est la réponse.

A.py

for _ in range(int(input())):
    n,m=map(int,input().split())
    if n%2==0 or m%2==0:
        print(n*m//2)
    else:
        print((n*m-1)//2+1)

Problème B

Le problème était si long qu'il paraissait aigu. L'essence était simple et nette.

C'est facile à résoudre si vous pensez utiliser Exemple. En outre, le nombre de personnes requises par chaque personne est organisé par ordre croissant et enregistré dans «a». En ce moment, il est bon de déplacer les personnes qui peuvent bouger ** à la fois **. De plus, le nombre maximum de personnes pouvant se déplacer est de ** $ a [0], a [1],…, a [i] \ leqq i + 1 $ hold **, qui est le plus grand $ i $ +2 Ce sera celui qui a été fait. Ici, $ a [0], a [1],…, a [i] \ leqq i + 1 \ leftrightarrow a [i] \ leqq i + 1 $, donc vous pouvez facilement déterminer avec l'instruction for. .. S'il n'y a pas d'élément contenant $ a [i] \ leqq i + 1 $, la réponse est 1.

B.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    for i in range(n-1,-1,-1):
        if a[i]<=i+1:
            print(i+2)
            break
    else:
        print(1)

Problème C

Quand j'ai commencé à résoudre ce problème, mon ordinateur est tombé en panne et je ne pouvais pas y penser. Je veux être calme même si je suis frappé par un accident.

Normalement, si vous recherchez complètement **, vous pouvez penser à BFS **, mais la masse ne peut pas être $ (10 ^ 9) ^ 2 $. Ensuite, ** allez verticalement ou horizontalement ** à $ \ _ {(x \ _2-x \ _1) + (y \ _2-y \ _1)} C _ {(x \ _2-x ) _1)} $ Il y en a donc j'ai voulu demander ça, mais il n'y en a pas beaucoup. En d'autres termes, ** il peut s'agir du même nombre en suivant des itinéraires différents **, alors j'ai expérimenté et pensé. Par exemple, en considérant la figure ci-dessous, il y a des routes $ \ _4 C \ _2 = 6 $, mais il n'y a que 5 routes, 68,69,70,70,71,72 $.

Après tout, je voulais savoir combien il y avait de nombres, alors j'ai pensé que des ** limites supérieures et inférieures pouvaient être trouvées **. À ce moment-là, comme le nombre augmente de diagonale du haut vers le bas, on peut voir que l'itinéraire allant vers la droite et descendant est le plus petit et l'itinéraire qui descend et va vers la droite est le plus grand. Par conséquent, considérez ** trouver la différence ** (et nous devons prouver que l'entier entre les limites supérieure et inférieure peut être représenté par un chemin approprié, mais nous l'avons précisé ici).

Pour trouver la différence, j'ai pensé à un exemple de $ x \ _2-x \ _1 \ neq y \ _2-y \ _1 $, et j'ai considéré l'exemple suivant.

Comme il suffit de considérer la différence, elle est exprimée sous la forme de (+ entier). À ce stade, vous pouvez voir que le nombre de + est augmenté un par un en regardant la figure ci-dessus. En effet, comme vous pouvez le voir sur la ligne diagonale rouge, la différence diagonale augmente. De plus, le nombre de + n'est que de $ min (x \ _2-x \ _1, y \ _2-y \ _1) $ au plus. En d'autres termes, les nombres qui sont + comme $ m = min (x \ _2-x \ _1, y \ _2-y \ _1)) $ sont résumés comme suit.

(1) Lorsque le nombre de + est augmenté

(1+2+…+m) \times 2 -m=m^2

-Est le dernier car l'élément inférieur gauche est compté deux fois.

(2) Lorsque le nombre de + est atteint la limite supérieure

|(x\_2-x\_1)-(y\_2-y\_1)| \times m

Par conséquent, puisque la différence a été obtenue ci-dessus, elle devrait être de (différence) +1.

C.py

for _ in range(int(input())):
    x1,y1,x2,y2=map(int,input().split())
    a,b=(x2-x1+1),(y2-y1+1)
    if a>b:
        a,b=b,a
    print((a-2)*(a-1)+(a-1)+(a-1)*(b-a)+1)

Problème D

J'ai pu trouver ce problème rapidement, mais c'était difficile à mettre en œuvre.

Supposons que les jours soient attribués dans l'ordre de 1 par mois et que lorsque vous sélectionnez des jours $ x $ consécutifs, le total des jours est le maximum.

Pour le moment, ** le plus gros candidat est ** si vous sélectionnez jusqu'à la fin de chaque mois **. De plus, comme il y a $ n $ de mois, j'ai trouvé qu'il pouvait être implémenté avec $ O (n) $ en déplaçant ** $ x $ jours en parallèle et en utilisant l'image ** pour gérer les différences.

Le problème lors de la mise en œuvre est "** Combien de mois sélectionnez-vous lorsque vous sélectionnez la fin d'un mois " et " Combien de jours sélectionnez-vous pour un mois dont la date est impaire ** ". Cela peut être mis en œuvre en divisant en un minimum mensuel entièrement sélectionné $ now1 $ et un total de $ now2 $ pour ce jour, et un $ add1 $ supplémentaire pour le jour sélectionné et un total de $ add2 $ pour ce jour. De plus, s'il n'y a pas de mois complètement sélectionné, définissez $ now1 = inf $.

Ici, il est implémenté en opérant dans l'ordre décroissant de $ i = n-1 \ rightarrow 0 $ selon les cas suivants. Aussi, laissez les dates totales des mois $ x $ et $ i $ ème être $ a [i] $ pour les dates qui doivent être recherchées en plus.

(1) Quand $ now1 = inf $ ou $ now1 = i + 1 $

Dans ce cas, il n'y a pas de mois complètement sélectionné, alors initialisez-le avec $ now1 = inf, now2 = 0, add1 = 0, add2 = 0 $ et recherchez $ check = x $ days.

[1] $ chèque <d [i] $ Il n'y a pas de mois complètement sélectionné, et $ now1, now2 $ reste inchangé. $ add1, add2 $ doit être mis à jour, $ add1 = check, add2 = \ sum_ {j = 0} ^ {check-1} (d [i] -j) = \ frac {(2d [i] - check + 1) \ times check} {2} $.

[2] $ chèque \ geqq d [i] $ Il y a un mois entièrement sélectionné, et $ now1 = i, now2 = a [i], check = x-d [i] $ sont confirmés. De plus, il peut y avoir des mois plus complètement sélectionnables, donc décrémentez $ now1 $ et ajoutez à $ now2 $ tout en tournant l'instruction while avec $ check \ geqq d [now1-1] $ comme condition de boucle. , Le surplus est calculé en le mettant en $ add1 et add2 $.

(2) Dans le cas de $ now1 \ neq inf $ et $ now1 \ neq i + 1 $

$ now1, now2 $ n'a pas besoin d'être initialisé. Aussi, définissons $ check = add1 + d [i + 1] $ pour considérer quel mois le surplus $ add1 $ sera distribué. Définissez également 0 pour $ add1 et add2 $.

En (1), il n'y avait aucun mois qui était complètement sélectionné, donc j'ai commencé à partir du $ i $ ème mois, mais en (2), j'ai déjà complètement sélectionné jusqu'à $ maintenant 1 $. Par conséquent, la prochaine chose à rechercher est $ now1-1 $, et une implémentation similaire peut être obtenue en remplaçant $ i $ dans la discussion de (1) par $ n-1 $.

✳︎… Il est facile à mettre en œuvre si vous connaissez ** ① la classification des cas, ② l'initialisation, ③ le traitement des différences **.

D.py

n,x=map(int,input().split())
d=list(map(int,input().split()))
a=[i*(i+1)//2 for i in d]
inf=100000000000
ans=0
#now1:Jusqu'où l'as-tu pris complètement(Quand pas complètement-1)
now1=inf
#now2:Quel est le total des pièces prises complètement?
now2=0
#add1:Combien a été ajouté
add1=0
#add2:Quel est le total des pièces supplémentaires prises?
add2=0
for i in range(n-1,-1,-1):
    if now1==inf or now1==i+1:
        check=x
        now1=inf
        now2=0
        add1=0
        add2=0
        if check<d[i]:
            #now1 ne fonctionne pas
            now2=0
            add1=check
            add2=(2*d[i]-check+1)*check//2
        else:
            now1=i
            now2=a[i]
            check-=d[i]
            while check>=d[now1-1]:
                check-=d[now1-1]
                now2+=a[now1-1]
                now1-=1
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
    else:
        #Supprimer lors de la prise
        #le chèque est une valeur supplémentaire
        check=add1+d[i+1]
        add1=0
        add2=0
        now2-=a[i+1]
        if check<d[now1-1]:
            #now1 ne fonctionne pas
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
        else:
            while check>=d[now1-1]:
                check-=d[now1-1]
                now2+=a[now1-1]
                now1-=1
            add1=check
            add2=(2*d[now1-1]-check+1)*check//2
    #print(now1,now2,add1,add2)
    ans=max(now2+add2,ans)
print(ans)

Après le problème E

Je vais sauter cette fois