[PYTHON] Codeforces Round # 651 (Div.2) Critique Bacha (8/20)

Les résultats de cette fois

Impressions de cette époque

J'ai passé énormément de temps sans voir B comme un bâillon. Je suis très déçu. Je n'ai pas pu le voir car j'ai essayé de trouver la valeur maximale en ** mal interprétant l'énoncé du problème **. Le modèle qui devrait être facile mais étrange est généralement ** oublié dans l'énoncé du problème **, alors portons un jugement calme.

Problème A

Considérons le $ a, b $ qui satisfait $ 1 \ leqq a <b \ leqq n $ avec le plus grand $ gcd (a, b) (= X) $. À ce stade, $ a et b $ sont des multiples de $ X (\ geqq 1) $, et les deux $ a = X et b = 2X $ sont les plus grands parmi $ n $ ou moins. Par conséquent, $ X = [\ frac {n} {2}] $ est la réponse.

A.py

for _ in range(int(input())):
    n=int(input())
    print(n//2)

Problème B

** J'ai négligé l'énoncé du problème ** et j'ai essayé de trouver le pgcd maximum. En fait, vous devez sortir de sorte que pgcd supérieur à 1 soit satisfait.

Il est facile de penser à ** pour que pgcd soit 2. En d'autres termes, vous pouvez ajouter des nombres impairs les uns aux autres et des nombres pairs pour former une paire. Pour le moment, il y a au plus deux ** nombres qui ne peuvent pas être transformés en ** paires pour chacune des paires impaires et paires, vous pouvez donc toujours créer plus de $ n-1 $ paires. Par conséquent, vous pouvez générer cette paire $ n-1 $.

B.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    xy=[[] for i in range(2)]
    for i in range(2*n):
        xy[a[i]%2].append(i+1)
    ans=[]
    for i in range(2):
        for j in range(len(xy[i])//2):
            ans.append([xy[i][2*j],xy[i][2*j+1]])
    for i in range(n-1):
        print(" ".join(map(str,ans[i])))

Problème C

Je n'ai pas pu penser correctement à cause de l'impatience de B. Dans de tels cas, assurez-vous de ** faire une pause **. Dans ce qui suit, $ Ashishgup $ sera $ A $ et $ FastestFinger $ sera $ F $.

Il y a deux opérations pour $ n $ dans le problème: ① Divisez $ n $ par une fraction impaire de $ n $ à l'exclusion de 1, ou ② Soustrayez 1 de $ n $.

La personne qui peut enfin définir $ n $ à 1 gagne, nous visons donc à le définir d'abord sur 1. Tout d'abord, considérons le cas où ** $ n $ est impair **. À ce stade, vous pouvez le diviser par $ n $ pour en faire 1, vous gagnez donc $ A $. Cependant, si ** $ n = 1 $ **, la perte de $ A $ est confirmée, donc $ F $ gagne.

Ensuite, considérons le cas où ** $ n $ est pair **. À ce stade, si vous utilisez ②, vous perdrez $ A $, alors envisagez de faire fonctionner ①. Cependant, si ** $ n = 2 $ **, vous pouvez soustraire 1 pour gagner $ n $ 1 afin que $ A $ puisse gagner.

Ici, soit $ fac (n) $ ** combien de cotes sont incluses dans $ n $ une fois factorisées en facteurs premiers **. Quand ** $ fac (n) = 0 $ ** ne peut pas opérer ①, $ A $ n'a d'autre choix que d'opérer ②, et $ F $ l'emporte. Ici, quand ** $ fac (n)> 0 $ et $ n $ sont des multiples de 4, $ n $ peut être changé en $ fac (n) = 0 $ et $ n> 2 $ par l'opération de ②. Donc $ A $ gagne.

La dernière chose qui reste est ** $ fac (n)> 0 $ et même $ n $ ** qui n'est pas un multiple de 4. Ici, quand ** $ fac (n) = 1 $ **, dans le cas de l'opération ②, il devient un nombre impair et perd, et dans le cas de l'opération ①, $ n = 2 $, donc $ F $ gagne. Faire. Par contre, lorsque ** $ fac (n)> 1 $ ** peut être divisé par un nombre impair pour faire $ fac (n) = 1 $, $ A $ gagne.

J'ai senti qu'il fallait résoudre calmement le problème car les échantillons devaient être triés dans l'ordre ** et les échantillons sont gentils. De plus, il est facile de penser que de tels ** problèmes de jeu asymétriques ** sont conscients que la première frappe a un avantage considérable.

C.py

from math import sqrt
def fac(n):
    if n==1:return 0
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return fac(i)+fac(n//i)
    if n%2==1:
        return 1
    else:
        return 0
for _ in range(int(input())):
    ans=["Ashishgup","FastestFinger"]
    n=int(input())
    #print(fac(n)+(n%2==0)+(n%4==0))
    if n==1:
        print(ans[1])
    elif n==2:
        print(ans[0])
    elif n%2==1:
        print(ans[0])
    elif fac(n)==0:
        print(ans[1])
    elif n%4==0:
        print(ans[0])
    else:
        if fac(n)>1:
            print(ans[0])
        else:
            print(ans[1])

Problème D

Essayez de minimiser le maximum de chacun des index pairs et impairs pour la sous-colonne sélectionnée. De plus, la taille de ces sous-colonnes est fixée à $ k (\ geqq 2) $.

** Au début, j'ai réfléchi à la façon de choisir avec gourmandise parmi le plus petit **. En d'autres termes, les plus petits sont sélectionnés dans l'ordre. Cependant, cette méthode essaie de réduire à la fois l'élément d'index impair et l'élément d'index pair, donc j'ai senti qu'il y avait un moyen de le réduire ($ \ parce que $ ** si un seul élément d'index devient plus petit). Parce que c'est bon **).

Maintenant, envisagez de réduire uniquement les index impairs (ainsi que les index pairs uniquement). De plus, comme il est difficile de sélectionner exactement des éléments $ k $, j'ai envisagé une dichotomie car il semble qu'il y ait encore de la place pour trouver la valeur minimale (cette considération est ** limitée par la valeur minimale). Vous pouvez être sûr qu'il a une monotonie ** qui se réunit ou change selon les conditions et qu'il ** compte le nombre de fois **.).

Par conséquent, déterminez si vous pouvez sélectionner ** $ k $ (ou plus) éléments ** tout en vous assurant que seuls les index impairs sont inférieurs ou égaux à une certaine valeur de $ X $. Sous cela, les éléments peuvent être ** sélectionnés avec gourmandise **. En d'autres termes, pour les éléments de l'index impair, sélectionnez l'élément qui apparaît en premier sous $ X $ en tant que sous-colonne, et pour l'élément de l'index pair, sélectionnez l'élément à côté de l'élément de l'index impair. Si vous pouvez sélectionner des éléments $ k $ (ou plus) de cette manière, renvoyez True, et si vous ne pouvez pas sélectionner, vérifiez l'heure de l'index pair.

Vous pouvez également implémenter la dichotomie sans bugs en regardant cet article. Au début, il suffit de faire attention à la plage de $ l et r $ définie par la valeur initiale **.

D.py

#Vous pouvez en choisir un facilement
n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
    global n,k,a
    #Peut-il être inférieur à x(C'est le nombre impair)
    check=0
    now=1
    for i in range(n):
        if now:
            if a[i]<=x:
                now=1-now
                check+=1
        else:
            now=1-now
            check+=1
    if check>=k:
        #print(check)
        return True
    #Nombre pair
    check=0
    now=0
    for i in range(n):
        if now:
            if a[i]<=x:
                now=1-now
                check+=1
        else:
            now=1-now
            check+=1
    if check>=k:
        #print(check)
        return True
    else:
        #print(check)
        return False
l,r=0,10**9+1
#Trouvez la valeur minimale
while l+1<r:
    m=l+(r-l)//2
    #print(f(m))
    if f(m):
        r=m
    else:
        l=m
print(r)

Problème E

Considérez le nombre minimum d'opérations pour faire correspondre $ S $ avec $ T $ en sélectionnant à plusieurs reprises une sous-chaîne d'une chaîne binaire et en décalant les caractères un par un dans le sens des aiguilles d'une montre.

Ici, ** 0 et 1 doivent être égaux en nombre pour correspondre à **, donc -1 a été généré. Par conséquent, dans ce qui suit, nous n'avons besoin de considérer que les chaînes avec le même nombre de 0 et de 1. (À l'inverse, les chaînes avec le même nombre de 0 et de 1 peuvent toujours être mises en correspondance, mais la preuve est omise ici.)

Tout d'abord, pensez à ** décider avidement de la fin **. Pour de tels problèmes, vous pouvez réduire le nombre d'opérations par ** une méthode gourmande qui change autant de caractères que possible **. De plus, vous n'avez pas à penser à ce qui correspond déjà, alors ne pensez qu'aux différentes positions.

Cependant, je ne pouvais pas penser à une solution, alors j'ai pensé à ** regarder l'échantillon et expérimenter ** (je ne peux pas le résoudre sans un bon échantillon, donc je ne veux pas trop me fier à l'échantillon **. est.). À ce moment, j'ai prêté attention aux modèles suivants.

8
10101010
01010101

Dans ce modèle, ** toutes les positions sont différentes, mais c'est $ S \ rightarrow T $ ** en une seule opération. Pour généraliser cela, si ** 0 et 1 sont des sous-colonnes décalées et même de longueur **, vous pouvez effectuer une opération pour faire correspondre toutes les parties sélectionnées.

À ce stade, j'ai essayé de simuler tout en générant des sous-chaînes commençant par 0 et 1, mais cette politique a échoué car la mise en œuvre était trop gênante. Voici un ** moyen plus simple de simuler **. En d'autres termes, il vous suffit d'enregistrer ** le nombre de sous-chaînes alternatives commençant par 0 et 1 lorsque vous regardez un certain caractère. De plus, je veux que chaque sous-colonne soit aussi longue que possible, donc si elle peut être connectée **, connectez-la aux sous-colonnes restantes **.

Par conséquent, $ v \ _1: $ 0 numéro de sous-colonne de départ, $ v \ _2: $ 0 numéro de sous-chaîne de départ se terminant à 0 (inachevé), $ w \ _1: $ 1 numéro de sous-chaîne de départ, $ w \ _2: $ 1 Placez le nombre de sous-colonnes commençant et finissant par 1 (inachevé) et les variables. Ensuite, le $ i $ th vaut 0 ou 1, et les observations sont divisées comme suit.

(1) Lorsque le $ i $ th est 0 [1] Lorsque $ w \ _2 $ est supérieur à 0 → Ajoutez 0 à la sous-colonne inachevée, $ w \ _2 $ - = 1. → À ce stade, vous pouvez voir que ** le nombre de sous-colonnes n'augmente pas **. [2] Lorsque $ w \ _2 $ vaut 0 → Lorsque $ v \ _1> v \ _2 $, vous pouvez augmenter le nombre de sous-colonnes inachevées, soit $ v \ _2 $ + = 1. → À ce stade, vous pouvez voir que ** le nombre de sous-colonnes n'augmente pas **. → Quand $ v \ _1 = v \ _2 $ ** Il est nécessaire d'ajouter une nouvelle sous-colonne **, qui est $ v \ _1 $ + = 1 et $ v \ _2 $ + = 1.

(2) Lorsque le $ i $ th est 1. [1] Lorsque $ v \ _2 $ est supérieur à 0 → Ajoutez 0 à la sous-colonne inachevée, $ v \ _2 $ - = 1. → À ce stade, vous pouvez voir que ** le nombre de sous-colonnes n'augmente pas **. [2] Lorsque $ v \ _2 $ vaut 0 → Lorsque $ w \ _1> w \ _2 $, vous pouvez augmenter le nombre de sous-colonnes inachevées, soit $ w \ _2 $ + = 1. → À ce stade, vous pouvez voir que ** le nombre de sous-colonnes n'augmente pas **. → Quand $ w \ _1 = w \ _2 $ ** Il est nécessaire d'ajouter une nouvelle sous-colonne **, et $ w \ _1 $ + = 1 et $ w \ _2 $ + = 1.

A la condition que les nombres de 0 et de 1 ne soient pas égaux et selon cette méthode gourmande, ** finalement $ v \ _2, w \ _2 $ sera 0 ** (la preuve est omise). Par conséquent, la réponse est $ v \ _1 + w \ _1 $ après avoir exécuté la méthode gourmande.

E.py

#Simplifiez la mise en œuvre!
n=int(input())
s=input()
t=input()
if s.count("1")!=t.count("1"):
    print(-1)
    exit()

#De la corde+Montant de calcul de
x=[s[i] for i in range(n) if s[i]!=t[i]]

#v commence à 0
#w est 1 début
#1 est le total
#2 est le surplus
v1,v2,w1,w2=0,0,0,0
for i in x:
    if i=="0":
        if w2==0:
            if v1==v2:
                v1+=1
            v2+=1
        else:
            w2-=1
    else:
        if v2==0:
            if w1==w2:
                w1+=1
            w2+=1
        else:
            v2-=1
print(v1+w1)

Après problème F

Je vais sauter cette fois