[PYTHON] AtCoder Beginner Contest 098 Revue des questions précédentes

Temps requis

Impressions

Dans le passé, je ne pouvais pas résoudre le problème XOR, mais une fois que j'ai appris les bases qu'il serait plus facile de calculer en divisant chaque chiffre en binaire, je pouvais le résoudre. L'explication et le code de D sont difficiles à comprendre, j'attends donc des suggestions d'amélioration.

Problème A

Trouvez simplement max.

answerA.py

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))

Problème B

Il existe N-1 façons de se diviser en x et y, et en faisant de x et y un ensemble au lieu d'une chaîne pour chacun, la taille du plus grand ensemble de produits est la réponse.

answerB.py

n=int(input())
s=input()
ans=0
for i in range(n-1):
    s1=s[:i+1]
    s2=s[i+1:]
    s3=set(s1)&set(s2)
    ans=max(ans,len(s3))
print(ans)

Problème C

Au moment de choisir un chef, vous pouvez compter le nombre de personnes à l'ouest de ce chef qui font face à l'ouest et celles qui sont à l'est de ce chef qui font face à l'est, mais le nombre de personnes est O ( Doit être calculé par 1) ou O (log (n)). Ici, puisque le nombre de personnes est ** somme cumulative **, il peut être calculé par O (1) en calculant le nombre de personnes faisant face à l'ouest et celles faisant face à l'est comme somme cumulée.

answerC.py

n=int(input())
s=input()
l=[0]*n
r=[0]*n
for i in range(1,n):
    l[i]=l[i-1]+(s[i-1]=="W")
for i in range(n-2,-1,-1):
    r[i]=r[i+1]+(s[i+1]=="E")
ans=n-1
for i in range(n):
    ans=min(ans,l[i]+r[i])
print(ans)

Problème D

Tout d'abord, j'ai pensé à paraphraser parce que xor devient égal à +. Ensuite, dans XOR, j'ai remarqué qu'il n'y a pas de report ** car le nombre de 1 dans chaque chiffre est 1 lorsqu'il s'agit d'un nombre impair et 0 lorsqu'il est pair lorsqu'il est converti en nombre binaire. Par conséquent, lors de l'ajout, vous pouvez voir que ** s'il n'y a pas de report pour tous les chiffres **, le sujet est satisfait. De plus, en d'autres termes, il n'y a pas de report dans le i-ième chiffre **, ce qui équivaut au nombre de $ A_l… A_r $ où le i-ième chiffre est 1 ou moins **. Je vais. À partir de ce qui précède, préparez d'abord un tableau qui stocke le nombre de 1 dans chaque chiffre. Sur cette base, nous rechercherons des candidats pour l et r, mais en considérant si $ A_l… A_ {r + 1} $ tient quand $ A_l… A_r $ tient, $ A_l… A_r $ et $ A_l… A_ { Lorsque vous faites attention à chaque chiffre de r + 1} $, le nombre de ** 1 est soit augmenté soit inchangé **. Par conséquent, lorsque l est fixé, l'ensemble de (l, r) qui ne dépasse pas 2 compte tenu du nombre de 1 dans chaque chiffre de $ A_l… A_r $ pour r = l + k (k> = 1) est le sujet. Rencontrer. De plus, si vous utilisez la ** méthode de mise à l'échelle ** à ce stade, vous pouvez compter tous les candidats (l, r) en déplaçant ** r pour satisfaire le thème, puis en déplaçant l **. Je vais. Comme j'ai oublié comment implémenter la méthode scale, je vais revoir le code de la méthode scale, mais pour plus de détails, reportez-vous à l'article de Kenchon S'il vous plaît. La chose importante à propos de ce problème est que lorsque ** (l, r) tient, (l + 1, r) tient également ** (comme vous pouvez le voir dans la discussion jusqu'à présent). Par conséquent, lors de la prise de l'échelle, lorsque l est fixe et r est augmenté tout en satisfaisant le sujet, ** (l + 1, r) vaut également pour tout r **. Par conséquent, il est possible de tourner efficacement l en tournant 0 → n-1 en tournant l'instruction for, et en maintenant et en augmentant r séparément de l'instruction for. À propos, Python n'a pas réussi même avec cette méthode d'échelle, alors je l'ai passé avec PyPy.

L'explication est difficile à comprendre et le code est un peu difficile à comprendre, alors faites-le moi savoir si vous avez des suggestions d'amélioration.

Post-scriptum (11/04/2020)

Considérant le cas où il n'y a pas de report pour tous les chiffres, les résultats de l'opération + et de l'opération ^ seront les mêmes, donc en sauvegardant respectivement les résultats de l'opération + et de l'opération ^, "pour chaque chiffre" Il peut être utilisé comme alternative à un tableau qui stocke le nombre de 1 (de cette façon, vous pouvez également utiliser Python, voir les commentaires pour plus d'informations). De plus, le deuxième code est implémenté de cette manière.

answerD.py

n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^Parce que c'est 20
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
print(ans)

answerD2.py

n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
np,nx=a[0],a[0]
for left in range(n):
    while np==nx:
        right+=1
        if right==n:
            break
        np+=a[right]
        nx^=a[right]
    else:
        np-=a[right]
        nx^=a[right]
    right-=1
    ans+=(right-left+1)
    np-=a[left]
    nx^=a[left]
print(ans)