[PYTHON] Codeforces Runde # 651 (Div. 2) Bacha Review (8/20)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe viel Zeit verbracht, ohne B als Knebel zu sehen. Ich bin sehr enttäuscht. Ich konnte es nicht sehen, weil ich versucht habe, den Maximalwert zu finden, indem ich die Problemstellung falsch verstanden habe. Das Muster, das einfach, aber seltsam sein sollte, wird normalerweise in der Problemstellung übersehen. Lassen Sie uns also ein ruhiges Urteil fällen.
Problem A
Betrachten Sie das $ a, b $, das $ 1 \ leqq a <b \ leqq n $ mit dem größten $ gcd (a, b) (= X) $ erfüllt. Zu diesem Zeitpunkt sind sowohl $ a als auch b $ Vielfache von $ X (\ geqq 1) $, und sowohl $ a = X als auch b = 2X $ sind die größten unter $ n $ oder weniger. Daher ist $ X = [\ frac {n} {2}] $ die Antwort.
A.py
for _ in range(int(input())):
n=int(input())
print(n//2)
B-Problem
** Ich habe die Problemstellung übersehen ** und versucht, die maximale gcd zu finden. Eigentlich sollten Sie so ausgeben, dass gcd größer als 1 erfüllt ist.
Es ist leicht, an ** zu denken, so dass gcd 2 ist. Mit anderen Worten, ungerade Zahlen sollten gepaart und gerade Zahlen miteinander gepaart werden. Zu diesem Zeitpunkt gibt es höchstens zwei ** Zahlen, die nicht für ungerade und gerade ungerade ** Paare gebildet werden können, sodass Sie immer mehr als $ n-1 $ Paare bilden können. Daher können Sie dieses $ n-1 $ -Paar ausgeben.
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])))
C-Problem
Ich konnte wegen Bs Ungeduld nicht richtig denken. Machen Sie in solchen Fällen unbedingt eine Pause. Im Folgenden wird $ Ashishgup $ $ A $ und $ FastestFinger $ $ F $ sein.
Es gibt zwei Operationen für $ n $ im Problem: ① Teilen Sie $ n $ durch einen ungeraden Bruchteil von $ n $ ohne 1 oder ② subtrahieren Sie 1 von $ n $.
Die Person, die $ n $ endlich auf 1 setzen kann, gewinnt, daher versuchen wir, es zuerst auf 1 zu setzen. Betrachten Sie zunächst den Fall, in dem ** $ n $ ungerade ist **. Zu diesem Zeitpunkt können Sie es durch $ n $ teilen, um es zu 1 zu machen, sodass Sie $ A $ gewinnen. Wenn jedoch ** $ n = 1 $ ** ist, wird der Verlust von $ A $ bestätigt, sodass $ F $ gewinnt.
Betrachten Sie als nächstes den Fall, in dem ** $ n $ gerade ist **. Wenn Sie zu diesem Zeitpunkt ② betreiben, verlieren Sie $ A $. Ziehen Sie also in Betracht, ① zu betreiben. Wenn jedoch ** $ n = 2 $ ** ist, können Sie 1 subtrahieren, um $ n $ 1 zu erhalten, damit $ A $ gewinnen kann.
Hier sei $ fac (n) $ **, wie viele Gewinnchancen in $ n $ enthalten sind, wenn sie in Primfaktoren zerlegt werden **. Wenn ** $ fac (n) = 0 $ ** nicht operate funktionieren kann, hat $ A $ keine andere Wahl, als ② zu betreiben, und $ F $ gewinnt. Wenn ** $ fac (n)> 0 $ und $ n $ ein Vielfaches von 4 sind, kann $ n $ durch die Operation von ② in $ fac (n) = 0 $ und $ n> 2 $ geändert werden. Also gewinnt $ A $.
Das letzte, was noch übrig ist, ist ** $ fac (n)> 0 $ und sogar $ n $ **, das kein Vielfaches von 4 ist. Wenn hier ** $ fac (n) = 1 $ ** ist, wird es im Fall der Operation ② eine ungerade Zahl und verliert, und im Fall der Operation ① ist $ n = 2 $, also gewinnt $ F $. Machen. Wenn andererseits ** $ fac (n)> 1 $ ** durch eine ungerade Zahl geteilt werden kann, um $ fac (n) = 1 $ zu erhalten, gewinnt $ A $.
Ich hielt es für notwendig, das Problem ruhig zu lösen, da die Proben in der richtigen Reihenfolge sortiert werden sollten ** und die Proben freundlich sind. Es ist auch leicht zu glauben, dass solche ** asymmetrischen Spielprobleme ** sich bewusst sind, dass der erste Schlag einen erheblichen Vorteil hat.
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])
D Problem
Versuchen Sie, das Maximum jedes der ungeraden und geraden Indizes für die ausgewählte Unterspalte zu minimieren. Außerdem ist die Größe solcher Unterspalten auf $ k (\ geqq 2) $ festgelegt.
** Zuerst dachte ich darüber nach, wie ich gierig aus dem kleineren auswählen sollte **. Mit anderen Worten, die kleineren werden der Reihe nach ausgewählt. Diese Methode versucht jedoch, sowohl das ungerade als auch das gerade Indexelement zu verkleinern, sodass ich der Meinung war, dass es eine Möglichkeit gibt, es zu verkleinern ($ \ weil $ **, wenn nur ein Indexelement kleiner wird). Weil es gut ist **).
Reduzieren Sie nun nur die ungeraden Indizes (sowie nur die geraden Indizes). Da es schwierig ist, genau $ k $ -Elemente auszuwählen, habe ich eine Dichotomie in Betracht gezogen, da anscheinend immer noch Platz ist, um den Mindestwert zu finden (diese Überlegung ist ** durch den Mindestwert begrenzt). Sie können sicher sein, dass es eine Monotonie ** hat, die den Bedingungen entspricht oder sich entsprechend ändert, und dass es ** zählt, wie oft **.).
Überlegen Sie daher, ob Sie ** $ k $ (oder mehr) Elemente ** auswählen können, während Sie sicherstellen, dass nur ungerade Indizes kleiner oder gleich einem bestimmten Wert von $ X $ sind. Darunter können Elemente ** gierig ausgewählt ** werden. Mit anderen Worten, wählen Sie für die Elemente des ungeraden Index das Element aus, das zuerst unter $ X $ als Unterspalte angezeigt wird, und wählen Sie für das Element des geraden Index das Element neben dem Element des ungeraden Index aus. Wenn Sie bei dieser Auswahl $ k $ (oder mehr) Elemente auswählen können, geben Sie True zurück. Wenn Sie nicht auswählen können, überprüfen Sie die Zeit des geraden Index.
Sie können Dichotomie auch ohne Fehler implementieren, indem Sie [diesen Artikel] lesen (https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453). Zu Beginn ** müssen Sie nur auf den Bereich von $ l, r $ achten, der durch den Anfangswert ** festgelegt wird.
D.py
#Sie können bequem eine auswählen
n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
global n,k,a
#Kann es kleiner als x sein?(Dies ist die ungerade Zahl)
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
#Gerade Zahl
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
#Finden Sie den Mindestwert
while l+1<r:
m=l+(r-l)//2
#print(f(m))
if f(m):
r=m
else:
l=m
print(r)
E Problem
Berücksichtigen Sie die Mindestanzahl von Operationen, um $ S $ mit $ T $ abzugleichen, indem Sie die Operation zum Auswählen eines Teilstrings einer binären Zeichenfolge und Verschieben der Zeichen nacheinander im Uhrzeigersinn wiederholen.
Hier können ** 0 und 1 nicht übereinstimmen, es sei denn, sie sind gleich **, daher wird -1 ausgegeben. Daher müssen wir im Folgenden nur Zeichenfolgen mit der gleichen Anzahl von Nullen und Einsen berücksichtigen. (Umgekehrt können Zeichenfolgen mit der gleichen Anzahl von Nullen und Einsen immer abgeglichen werden, aber der Beweis wird hier weggelassen.)
Denken Sie zuerst an ** gierige Entscheidung vom Ende **. Bei solchen Problemen können Sie die Anzahl der Operationen durch eine gierige Methode reduzieren, bei der so viele Zeichen wie möglich geändert werden. Außerdem müssen Sie nicht darüber nachdenken, was bereits passt, sondern nur über verschiedene Positionen nachdenken.
Ich konnte mir jedoch keine Lösung vorstellen, also dachte ich darüber nach, ** die Probe anzusehen und zu experimentieren ** (ich kann sie nicht ohne eine gute Probe lösen, also möchte ich mich nicht zu sehr auf die Probe verlassen **. ist.). Zu diesem Zeitpunkt habe ich auf die folgenden Muster geachtet.
8
10101010
01010101
In diesem Muster ** sind alle Positionen unterschiedlich, aber es ist $ S \ rightarrow T $ ** in einer Operation. Um dies zu verallgemeinern: Wenn ** 0 und 1 versetzt sind und Teilspalten mit gerader Länge ** sind, können Sie eine Operation ausführen, die allen ausgewählten Teilen entspricht.
Zu diesem Zeitpunkt habe ich versucht, beim Generieren von Teilzeichenfolgen, die mit 0 und 1 beginnen, zu simulieren. Diese Richtlinie war jedoch nicht erfolgreich, da ihre Implementierung zu umständlich war. Hier ist eine ** einfachere Möglichkeit, ** zu simulieren. Mit anderen Worten, Sie müssen nur ** speichern, wie viele alternative Teilzeichenfolgen mit 0 und 1 beginnen, wenn Sie sich ein bestimmtes Zeichen ansehen. Außerdem möchte ich, dass jede Unterspalte so lang wie möglich ist. Wenn sie also verbunden werden kann **, verbinden Sie sie mit den verbleibenden Unterspalten **.
Daher $ v \ _1: Anzahl der Unterspalten, die mit $ 0 beginnen, $ v \ _2: Anzahl der Teilzeichenfolgen, die mit $ 0 beginnen und mit 0 enden (unvollendet), $ w \ _1: Anzahl der Teilzeichenfolgen, die mit $ 1 beginnen, $ w \ _2: $ 1 Platzieren Sie die Anzahl der Unterspalten, die mit 1 (unvollendet) beginnen und enden, und Variablen. Dann ist $ i $ th 0 oder 1, und die Fälle werden wie folgt aufgeteilt.
(1) Wenn das $ i $ th 0 ist [1] Wenn $ w \ _2 $ größer als 0 ist → Fügen Sie der unvollendeten Unterspalte 0 hinzu, $ w \ _2 $ - = 1. → Zu diesem Zeitpunkt sehen Sie, dass die Anzahl der Unterspalten nicht zunimmt **. [2] Wenn $ w \ _2 $ 0 ist → Wenn $ v \ _1> v \ _2 $, können Sie die Anzahl der unfertigen Unterspalten erhöhen, dh $ v \ _2 $ + = 1. → Zu diesem Zeitpunkt sehen Sie, dass die Anzahl der Unterspalten nicht zunimmt **. → Wenn $ v \ _1 = v \ _2 $ ** Es muss eine neue Unterspalte ** hinzugefügt werden, nämlich $ v \ _1 $ + = 1 und $ v \ _2 $ + = 1.
(2) Wenn das $ i $ th 1 ist. [1] Wenn $ v \ _2 $ größer als 0 ist → Fügen Sie der unvollendeten Unterspalte 0 hinzu, $ v \ _2 $ - = 1. → Zu diesem Zeitpunkt sehen Sie, dass die Anzahl der Unterspalten nicht zunimmt **. [2] Wenn $ v \ _2 $ 0 ist → Wenn $ w \ _1> w \ _2 $, können Sie die Anzahl der unfertigen Unterspalten erhöhen, dh $ w \ _2 $ + = 1. → Zu diesem Zeitpunkt sehen Sie, dass die Anzahl der Unterspalten nicht zunimmt **. → Wenn $ w \ _1 = w \ _2 $ ** Es muss eine neue Unterspalte ** hinzugefügt werden, und $ w \ _1 $ + = 1 und $ w \ _2 $ + = 1.
Unter der Bedingung, dass die Zahlen von 0s und 1s nicht gleich sind und gemäß dieser gierigen Methode ** schließlich $ v \ _2, w \ _2 $ 0 ** ist (Beweis wird weggelassen). Daher lautet die Antwort nach Ausführung der gierigen Methode $ v \ _1 + w \ _1 $.
E.py
#Machen Sie die Implementierung leichter!
n=int(input())
s=input()
t=input()
if s.count("1")!=t.count("1"):
print(-1)
exit()
#Von der Saite+Berechnungsbetrag von
x=[s[i] for i in range(n) if s[i]!=t[i]]
#v beginnt bei 0
#w ist 1 Start
#1 ist insgesamt
#2 ist der Überschuss
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)
Nach F Problem
Ich werde diesmal überspringen
Recommended Posts