[PYTHON] AtCoder Beginner Contest 072 Revue des questions précédentes
La deuxième question passée que j'ai déjà résolue
Temps requis
Problème A
Cas à savoir si le sable s'épuise ou non
answerA.py
x,t=map(int,input().split())
print(max(x-t,0))
Problème B
Tout ce que vous avez à faire est de récupérer les lettres impaires Il peut être écrit de manière plus concise en définissant des étapes comme dans le second (manipulation de chaîne Python) Trop bon)
answerB.py
s=input()
l=len(s)
t=""
for i in range(l):
if i%2==0:
t+=s[i]
print(t)
answerB_better.py
s=input()
print(s[0:len(s):2])
Problème C
La première méthode est apparue pendant le bachacon. Lorsque vous sélectionnez un certain nombre x, il vous suffit de maximiser le nombre total de x-1, x + 1 combinés, soustrayez donc le nombre maximum d'index au-dessus de i-1 de l'indice du nombre supérieur à i + 1. Vous pouvez voir que le nombre de choses est écrit à la main et expérimenté. (Cette méthode était un peu difficile. C'est bien de pouvoir utiliser la dichotomie. ** La recherche des triés est la dichotomie! **) La deuxième méthode est la solution idéale. Cette solution enregistre simplement le nombre de chaque nombre dans un tableau et génère celui avec la somme maximale de i-1, i, i + 1. Facile.
answerC1.py
import bisect
n=int(input())
a=sorted([int(i) for i in input().split()])
ma=0
for i in range(10**5):
ma=max(bisect.bisect_right(a,i+1)-bisect.bisect_left(a,i-1),ma)
print(ma)
answerC2.py
import bisect
n=int(input())
a=[int(i) for i in input().split()]
b=[0]*(10**5)
for i in range(n):
b[a[i]]+=1
ma=0
for i in range(1,10**5-1):
ma=max(b[i-1]+b[i]+b[i+1],ma)
print(ma)
Problème D
Étant donné que vous ne pouvez échanger que deux éléments adjacents, il est clair que l'échange par l'avant est le moins de fois possible. (Comment puis-je le prouver ... ??) Lorsque pi = i, si pi et pi + 1 sont permutés et pi ≠ i est répété dans l'ordre de i = 1 à n-1, pi ≠ i est valable lorsque i <= n-1, donc le dernier i Swap avec pn et pn − 1 uniquement quand = n est pi = i. De plus, puisque pn = n à ce moment, il faut noter que pn − 1 ≠ n − 1 est satisfait même s'il est permuté. De plus, quand je l'ai résolu auparavant, je n'ai pas remarqué le préambule et je faisais à nouveau tourner la boucle avec i = n-1 ~ 1. (Il est clair que seul le swap pn et pn-1 se produit lorsque la boucle est tournée, donc c'est OK)
answerD.py
n=int(input())
p=[int(i) for i in input().split()]
c=0
for i in range(n-1):
if p[i]==i+1:
p[i],p[i+1]=p[i+1],p[i]
c+=1
if p[-1]==n:
p[-1],p[-2]=p[-2],p[-1]
c+=1
print(c)
Recommended Posts