[PYTHON] Codeforces Round # 638 (Div.2) Examen Bacha (9/16)

Les résultats de cette fois

Impressions de cette époque

Je n'ai pas pu résoudre le problème parce que j'avais quelque chose à faire au milieu de l'examen du problème. Je suis déçu car il aurait été résolu s'il n'avait pas été inclus.

De plus, bien que le problème C puisse être grossièrement divisé en cas, il n'a pas réussi, alors je l'ai écrit après l'avoir réorganisé, et j'ai pu AC **. Je pense que j'ai fait un bon changement. Cependant, je ne pouvais pas changer le problème D à mi-chemin, donc je veux ** gérer le problème de manière cohérente **.

Problème A

Puisque $ 2 ^ + 2 ^ 2 +… + 2 ^ {n-1} <2 ^ n $, la somme de ceux contenant $ 2 ^ n $ doit être minimisée. Par conséquent, la valeur absolue de la différence à obtenir est $ (2 ^ 1 + 2 ^ 2 +… + 2 ^ {\ frac {n} {2} -1} + 2 ^ n) - (2 ^ {\ frac {n} {2}} + 2 ^ {\ frac {n} {2} + 1} +… + 2 ^ {n-1}) La différence est de $.

A.py

for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

Problème B

J'ai eu un problème avec le même thème dans ABC récent. Lorsque vous faites attention à des pièces de $ k $ consécutives, considérez ** la différence lorsque vous les glissez une par une **. Dans ce problème, les sommes sont égales, donc le nombre final résultant d'éléments séparés par $ k $ est égal **.

De plus, le fait que les parties séparées par $ k $ soient égales équivaut au fait qu'une période de ** longueur $ k $ apparaît dans la chaîne de caractères **. Si ce cycle ne peut inclure aucun nombre qui apparaît dans la séquence d'origine, alors il n'y a pas de séquence qui répond au sujet. Par conséquent, si (le type de nombre qui apparaît dans la séquence de nombres) $> k $, la séquence de nombres qui satisfait le thème ne peut pas être créée et -1 est généré.

Sur cette base, considérons une ** séquence de nombres pratique ** qui satisfait le sujet. À ce stade, il convient de noter que la relation de position des nombres dans la séquence de numéros d'origine ne change pas ** car seule l'opération d'insertion est effectuée. Par conséquent, il peut être mis en œuvre en définissant le point sur ** une séquence de numéros appropriée en utilisant n'importe quel caractère qui apparaît ** et en vérifiant s'il apparaît dans l'ordre tout en regardant la séquence de numéros d'origine. Cependant, cette fois, comme un tableau plus pratique, j'ai considéré ** une séquence de nombres dans laquelle chaque élément apparaît une fois dans chaque cycle **. En d'autres termes, si vous répétez $ n $ fois avec le même cycle que précédemment, vous pouvez créer une séquence de nombres qui satisfait le sujet sans vérification.

B.py

from collections import deque
for _ in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    if len(set(a))>k:
        print(-1)
        continue
    ans=[]
    for i in set(a):
        ans.append(str(i))
    for i in range(k-len(set(a))):
        ans.append(str(a[i]))
    realans=[]
    for i in range(n):
        realans+=ans
    print(len(realans))
    print(" ".join(realans))

Problème C

C'est un problème de marcher sur la valise d'angle si vous ne vous calmez pas. Cependant, l'échantillon est assez aimable pour vous amener à la bonne réponse.

Au début, je pensais qu'il valait mieux le diviser le plus uniformément possible **, mais j'ai réalisé que s'il y a plusieurs types de caractères, il vaut mieux les concaténer dans la même chaîne de caractères **. De plus, si le premier caractère a un caractère différent, un seul caractère différent est sorti. Ces considérations pourraient être obtenues expérimentalement, mais il est important de ** généraliser l'axe au cas par cas ** lors de sa mise en œuvre. Ici, nous nous concentrons sur ** le nombre de types de caractères ** et ** le premier caractère ** et les classons comme suit.

(1) Lorsqu'il n'y a qu'un seul type de caractère Triez les caractères aussi uniformément que possible, puis affichez la chaîne de caractères la plus longue.

(2) Lorsqu'un caractère différent apparaît au début Seul l'un des plus gros caractères apparaissant au début est sorti.

(Ce qui suit est le cas où les premiers caractères sont tous identiques mais il existe au moins deux types de caractères)

(3) Lorsqu'il y a trois types de caractères ou plus Après le deuxième caractère, tous les caractères restants doivent être concaténés dans une chaîne de caractères. Je pense qu'il vaut mieux y penser comme ayant de grandes lettres dans l'ordre du dictionnaire aussi loin que possible.

(4) Lorsqu'il existe deux types de caractères Si le plus petit caractère dans l'ordre du dictionnaire est exactement $ k $, le reste sera trié aussi uniformément que possible et la chaîne de caractères la plus longue sera sortie. Si ce n'est pas $ k $, vous pouvez concaténer tous les caractères restants dans une chaîne.

Concernant (✳︎) (3) et (4), je pense qu'il est plus rationnel de considérer ** le cas où il y a deux ou plusieurs types de caractères après le deuxième caractère **. Pendant le concours, je ne pensais pas être aussi organisé.

C.py

from collections import Counter
for _ in range(int(input())):
    n,k=map(int,input().split())
    s=sorted(input())
    t=list(Counter(s).items())
    if len(t)==1:
        print(s[0]*(-(-n//k)))
        continue
    now=s[0]
    ans=s[k-1]
    if now!=ans:
        print("".join(ans))
    elif len(t)>=3:
        print("".join(s[k-1:]))
    elif t[0][1]==k:
        print(t[0][0]+t[1][0]*(-(-n//k)-1))
    else:
        print("".join(s[k-1:]))

Problème D

(Dans ce qui suit, tout = est mis dans le nombre d'inégalité. Il y a quelques différences mathématiques, mais pardonnez-moi.)

À première vue, c'est un problème difficile à résoudre, mais ce n'est pas si difficile tant que vous en saisissez l'essence. Tout d'abord, concernant l'opération de fractionnement du slime, le slime dont la masse devrait être $ m \ _i + 1 $ cette nuit-là en se fractionnant est $ (\ frac {m \ _i} {2} + 1) + (\ frac Puisqu'il devient {m \ _i} {2} + 1) $, il est facile de comprendre que c'est ** une opération qui augmente la masse de +1 **. De plus, le nombre de slimes à sélectionner lors de la division est libre, et toute masse peut être exprimée sans la diviser même une fois, il est donc nécessaire de procéder en considérant qu'il n'y a pas de masse qui ne puisse pas être exprimée. Ici, afin d'augmenter la masse autant que possible, il est préférable de ** sélectionner et diviser tous les slimes existants **, mais ** vous ne pouvez pas simplement ajuster la masse à $ n $ à moins de l'ajuster par la dernière opération. **Je comprends ça.

En vertu de cela, le nombre de bactéries le matin de $ i $ est $ a \ _i $, $ i $ Le poids total des bactéries le matin du jour $ b \ _i $, $ i $ En supposant que le nombre de bactéries à sélectionner est $ x \ _i $, l'équation graduelle suivante est valable.

a\_{i+1}=a\_i+x\_i b\_{i+1}=b\_i+a\_{i+1}

Ici, ce que nous voulons enfin trouver, c'est le nombre de jours requis pour que $ b \ _i $ devienne $ n $, mais de ** $ n $, soustrayez $ a \ _i $ afin de le rendre 0 **. Il semble préférable d'y penser. Ici, cela peut être $ a \ _i \ leqq a \ _ {i + 1} \ leqq 2 a \ _i $, donc c'est bien si $ a \ _i \ leqq n \ leqq 2 a \ _i $ est satisfait le dernier jour. est. Aussi, si $ n> 2a \ _i $, je voudrais le diviser pour que $ a \ _ {i + 1} = 2 a \ _i $ autant que possible, mais ** un jour avant le dernier jour ** $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow 2 a \ _i \ leqq a \ _ {i + 2} \ leqq 4 a From \ _i $ $ 2 a \ _i \ leqq na \ _ {i + 1} \ leqq 4 a \ _i \ leftrightarrow 4a \ _i \ leqq n \ leqq 6 a \ _i $ doit être satisfait. Donc, si $ 2a \ _i <n <4a \ _i $, vous devez choisir $ x \ _i $, qui est inférieur à ** $ a \ _ {i} $, et juste ** à $ n $ le dernier jour suivant. Doit être.

Par exemple, si $ x \ i = 0 $, alors $ a {i + 1} = a \ _i $, donc $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow a \ _i \ leqq a \ _ {i + 2} \ leqq 2 a \ _ i $ from $ a \ _i \ leqq na \ _ {i + 1} \ leqq 2 a \ _i Il est temps de remplir \ leftrightarrow 2a \ _i \ leqq n \ leqq 3 a \ _i $.

Ce qui reste est quand $ 3a \ _i <n <4a \ _i $, mais par exemple, si $ x \ _i = [\ frac {a \ i} {2}] $, alors $ a {i + 1} = a \ _ i + [\ frac {a \ _ i} {2}] $, donc $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ Depuis leftrightarrow a \ _i + [\ frac {a \ _i} {2}] \ leqq a \ _ {i + 2} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _ i} {2}] $ $ a \ _i + [\ frac {a \ _i} {2}] \ leqq na \ _ {i + 1} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _i} {2}] \ leftrightarrow 2a \ _i + 2 [\ frac {a \ _i} {2}] \ leqq n \ leqq 3a \ _i + 3 [\ frac {a \ _ i} {2}] $ doit être satisfait. Comme cela inclut l'heure de $ 3a \ _i <n <4a \ _i $, il est également affiché lorsque $ 3a \ _i <n <4a \ _i $.

À partir de ce qui précède, $ x \ _i = na \ _i $, $ n \ leqq 3a \ _i $ pour $ n \ leqq 2a \ _i $, $ x \ _i = 0 $, $ n <4a \ _i $ Quand $ x \ _i = [\ frac {a \ _ i} {2}] $, $ n \ geqq 4a \ _i $, $ x \ _i = a \ _i $ donne le nombre minimum de jours Il est possible de produire des bactéries avec la masse totale de bactéries.

D.py

for _ in range(int(input())):
    n=int(input())
    ans=[]
    ai=1
    n-=1
    xi=0
    while True:
        if n<=2*ai:
            xi=n-ai
            ai=ai+xi
            n-=ai
            ans.append(xi)
            break
        elif n<=3*ai:
            xi=0
            ai=ai+xi
            n-=ai
            ans.append(xi)
        elif n<4*ai:
            xi=ai//2
            ai=ai+xi
            n-=ai
            ans.append(xi)
        else:
            xi=ai
            ai=ai+xi
            n-=ai
            ans.append(xi)
            #print(2)
        #print(ai,xi,n)
    print(len(ans))
    print(" ".join(map(str,ans)))

Après le problème E

Je vais sauter cette fois