[PYTHON] AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
Die zweite Frage, die ich bereits gelöst habe
Benötigte Zeit
Problem A
Fall, ob der Sand ausgeht oder nicht
answerA.py
x,t=map(int,input().split())
print(max(x-t,0))
B-Problem
Alles was Sie tun müssen, ist die ungeraden Buchstaben zu holen Es kann präziser geschrieben werden, indem Schritte wie im zweiten festgelegt werden (Python-String-Manipulation). Zu gut)
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])
C-Problem
Die erste Methode kam während des Bachacon auf. Wenn Sie eine bestimmte Zahl x auswählen, müssen Sie nur die Gesamtzahl von x-1, x + 1 zusammen maximieren. Subtrahieren Sie also die maximale Anzahl von Indizes über i-1 vom Index der Zahl größer als i + 1. Sie können sehen, dass die Anzahl der Dinge von Hand geschrieben und experimentiert wurde. (Diese Methode war etwas schwierig. Es ist gut, die Dichotomie verwenden zu können. ** Die Suche nach den sortierten ist die Dichotomie! **) Die zweite Methode ist die ideale Lösung. Diese Lösung zeichnet einfach auf, wie viele von jeder Zahl sich in einem Array befinden, und gibt die mit der maximalen Summe von i-1, i, i + 1 aus. Einfach.
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)
D Problem
Da Sie nur zwei benachbarte tauschen können, ist es klar, dass das Wechseln von vorne am seltensten erfolgt. (Wie kann ich es beweisen ... ??) Wenn pi = i ist, wird das Vertauschen von pi und pi + 1, um pi ≠ i zu machen, in der Reihenfolge von i = 1 bis n-1 wiederholt, und pi ≠ i gilt, wenn i <= n-1, also das letzte i Tauschen Sie nur dann mit pn und pn - 1, wenn = n pi = i ist. Da zu diesem Zeitpunkt pn = n ist, sollte auch beachtet werden, dass pn - 1 ≠ n - 1 auch dann erfüllt ist, wenn es getauscht wird. Als ich es zuvor gelöst hatte, war mir die Präambel nicht bekannt und ich drehte die Schleife erneut mit i = n-1 ~ 1. (Es ist klar, dass nur pn und pn-1 Swap auftreten, wenn die Schleife gedreht wird, also ist es 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