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

Les résultats de cette fois

Impressions de cette époque

Je suis de nouveau tombé dans un mauvais schéma. La politique était correcte, mais j'ai complètement abandonné parce que je ne pouvais pas la résoudre. Fondamentalement, les problèmes de niveau qui apparaissent dans div2 peuvent être résolus si la considération est solidifiée, donc je veux ** garder ma concentration **. Plus tard, si je me sens accro au marais, j'essaierai de ** éclaircir mes pensées et de penser ensuite **.

Problème A

Demandez-vous si tout peut être pareil. À ce stade, ** le nombre de fois où chaque alphabet apparaît doit être un multiple de $ n $ **. Par conséquent, après avoir connecté toutes les chaînes de caractères qui apparaissent, j'ai décidé de les convertir en liste et de les trier, puis d'utiliser la fonction groupby pour combiner les mêmes. Je l'ai remarqué après la fin, mais je pense que ce sera plus facile à mettre en œuvre si vous utilisez Counter au lieu de la fonction groupby.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    s=""
    for i in range(n):
        s+=input()
    s=list(s)
    s.sort()
    for i,j in groupby(s):
        if len(list(j))%n!=0:
            print("NO")
            break
    else:
        print("YES")

Problème B

Si vous rencontrez des problèmes avec le premier problème, vous êtes plus susceptible d'échouer, alors essayez d'aborder le premier problème aussi soigneusement que possible.

(On suppose que $ a \ _i $ sont disposés dans l'ordre croissant.)

Premièrement, si vous augmentez $ c $ pour $ c ^ i $, cela augmentera de façon exponentielle, donc je pense que la valeur de ** $ c $ n'augmentera pas autant **.

Compte tenu de ce point, c'est comme suit. De plus, dans ce qui suit, $ \ sum $ est exécuté dans la plage de $ i $ = 0 ~ $ n $ -1.

Premier,c=1Quand, toutes les valeurs sont 1devenira\_i \geqq 1Alors\sum{|a\_i-c^i|}=\sum{(a\_i-1)}Ce sera. Donc,\sum{c^i} < \sum{a\_i}+(\sum{(a\_i-1)})Vous pouvez le chercher sous(\becauseQuand ce n'est pas satisfait\sum{|a\_i-c^i|} \geqq \sum{(a\_i-1)}Ce sera.).. Aussi, à ce rythme**cDifficile de trouver la limite supérieure de**Par conséquent, la transformation de formule suivante est appliquée.

\begin{align}
&\sum{c^i} < \sum{a_i}+(\sum{(a_i-1)}) \\
&\rightarrow c^{n-1}< 2\sum{a_i}-n\\
&\rightarrow c< \sqrt[n-1]{2\sum{a_i}-n}\\
\end{align}

Par conséquent, nous avons pu fixer la limite supérieure de $ c $. Aussi, nous pouvons voir à partir d'expériences que cela ne pousse pas trop dans les conditions de ce problème **. J'ai fait une erreur en transformant la formule ici et j'ai perdu trop de temps.

B.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=10**18
for c in range(2,int((2*sum(a)-n)**(1/(n-1)))+1):
    x=1
    ans_sub=abs(a[0]-x)
    for i in range(n-1):
        x*=c
        ans_sub+=abs(a[i+1]-x)
    ans=min(ans,ans_sub)
print(min(ans,sum(a)-n))

Problème C

Personnellement, j'aime ça parce que j'ai pu bien y réfléchir.

Puisqu'il s'agit d'un problème de construction, je pense à ** abstraire l'opération d'une manière agréable **. À la suite de l'expérimentation en regardant l'échantillon, si tous les nombres peuvent être rendus un multiple de $ n $ en deux opérations, ** sélectionnez le tout dans l'opération finale ** et tous les nombres peuvent être mis à 0. J'ai remarqué. De plus, si vous sélectionnez un segment d'une longueur de $ n-1 $ et effectuez une opération, ** $ n-1 $ et $ n $ sont mutuellement premiers, vous pouvez donc faire de n'importe quel nombre un multiple de $ n $ du théorème du reste chinois. J'ai remarqué ça **. Par conséquent, envisagez de simuler l'opération concrètement.

Dans ce qui suit, nous allons considérer la sélection et l'exploitation d'un segment d'une longueur de $ n $ → un segment d'une longueur de 1 → un segment d'une longueur de $ n-1 $.

(1) Lorsqu'un segment d'une longueur de $ n $ est sélectionné L'opération devrait faire de $ a [i] + n \ times x $ un multiple de $ n-1 $ ($ n \ times x $ est le nombre à ajouter à cet élément). Ici, lorsque la formule est transformée, elle devient $ (a [i] + x) + (n-1) \ times x $, donc $ x = (n-1) -a [i] % (n-1) ) $ Pour faire de $ a [i] + n \ times x $ un multiple de $ n-1 $. Faites ceci pour tout $ i $.

(2) Lorsqu'un segment de longueur 1 est sélectionné Selon l'opération, tout nombre sera un multiple de $ n-1 $, mais comme la longueur du dernier segment sélectionnable est $ n-1 $, un élément doit déjà être mis à 0. Ici, le premier élément est mis à 0.

(3) Lorsqu'un segment d'une longueur de $ n-1 $ est sélectionné À partir de (1) et (2), tous les segments d'une longueur de $ n-1 $ (à l'exclusion du premier élément) sont $ n-1 $, vous pouvez donc effectuer des opérations.

De plus, si ** $ n = 1 $, 0 division se produira, et si $ n = 2 $, elle se comportera de manière inattendue s'il s'agit de votre propre implémentation **, donc dans ces cas, c'est différent comme cas d'angle. Je vais le traiter.

C.py

n=int(input())
a=list(map(int,input().split()))
#first
if n==1:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"1 1")
    print("0")
    print(f"1 1")
    print("0")
    exit()
if n==2:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"2 2")
    print(f"{-a[1]}")
    print(f"1 1")
    print("0")
    exit()
print(f"1 {n}")
x=[(n-1-a[i]%(n-1))*n for i in range(n)]
print(" ".join(map(str,x)))
print(f"1 1")
print(f"{-a[0]-x[0]}")
print(f"2 {n}")
print(" ".join(map(str,[-(a[i]+x[i]) for i in range(1,n)])))

Problème D

Si vous pensez à l'image que ** vous n'avez qu'à éviter la pire situation jusqu'à la dernière étape **, le problème du jeu peut fonctionner (même si je ne suis pas très bon dans ce domaine).

Ici, supposons qu'il reste deux tours de pierre à la fin et que le nombre de chaque pierre soit $ x, y $. À ce moment, la personne qui sélectionne la ** tour supplémentaire gagnera . Parce que chaque personne ne peut choisir que la tour qui a été sélectionnée en premier, la personne qui manque de pierres perd la première. De plus, comme il s'agissait d'une comparaison entre deux tours ici, la personne qui aurait choisi le plus de tours gagnerait, mais même s'il y a plusieurs tours, le nombre de pierres dans la tour avec le plus de pierres est l'autre. Vous pouvez gagner si vous avez plus que le nombre total de pierres dans une tour ( si le nombre de pierres dans une tour dépasse la majorité du nombre total de pierres **). En d'autres termes, ** quand il est dans cet état depuis le début ** est la victoire du $ T $ précédent. De plus, lorsque $ n = 1 $, il est évident que $ T $ gagne.

Dans d'autres cas, il est préférable que chacun ** agisse de façon à ce qu'il n'y ait pas plus de la moitié des pierres ** ($ \ leftrightarrow $ ** sélectionnez dans la tour avec le plus de pierres **). Par conséquent, en répétant cela, il ne restera que deux tours et le nombre de pierres restantes sera de 1,1 $. A ce moment, chacun peut choisir, donc la personne qui a pris la dernière pierre gagne. En d'autres termes, ** considérez la bizarrerie du nombre total de pierres **, si c'est impair, ce sera la première victoire $ T $, et si elle est paire, ce sera la deuxième victoire $ HL $.

D.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if n==1:
        print("T")
    elif max(a) > sum(a)//2:
        print("T")
    else:
        print(["T","HL"][(sum(a)-1)%2])

Après le problème E

Je vais sauter cette fois