[PYTHON] Educational Codeforces Round 91 Bacha Review (7/28)

Ergebnis

Impressionen

Seit gestern habe ich beschlossen, jeden Tag so viel Kodofo Bacha wie möglich zu machen, um die Anzahl der Lösungen zu erhöhen. AtCoders D ~ F wird durch ein Problem blockiert, das jedes Mal ein wenig mehr gelöst zu sein scheint. Lösen Sie also div2 oder edufo von Kodofo in der Nähe des Pegelbandes. ABC war in Ordnung, aber ich füllte ungefähr 70% der Probleme aus und hatte das Gefühl, dass es nur wenige Probleme auf dem Niveau gab, also entschied ich mich, Kodofo zu lösen.

Dieses Mal habe ich die C- und D-Probleme falsch verstanden und sie lange verwendet, sodass ich das D-Problem während des Wettbewerbs nicht lösen konnte. Beides ist überhaupt nicht schwierig. Wenn Sie es nicht wissen, versuchen Sie, das Problem erneut zu lesen **.

Problem A

Trotz dieses Problems stimmte das Beispiel nicht überein, da ich bei der Ausgabe einen Fehler gemacht habe **. Für die gegebene Zahlenfolge $ p $ wird die Zahl aufgezeichnet und zusammen mit vorher und nachher ausgegeben, wenn es nur eine ** Umkehrung von Zunahme / Abnahme (Extremwert) ** gibt. Wenn es keinen Extremwert gibt, nimmt die gesamte Zahlenfolge monoton ab oder zu, so dass es keine Menge von $ i, j, k $ gibt, die das Subjekt erfüllt, und Nein sollte ausgegeben werden.

A.py

#falsch verstanden(Ausgabefehler)
t=int(input())
for _ in range(t):
    n=int(input())
    p=list(map(int,input().split()))
    for i in range(1,n-1):
        if p[i-1]<p[i] and p[i]>p[i+1]:
            print("Yes")
            print(i,i+1,i+2)
            break
    else:
        print("No")

B-Problem

Die Reihenfolge von Janken ändert sich je nach Position, aber ** $ c_1c_2… c_n $ spielt jeweils $ n $ mal gegen eine andere Hand ($ s_1s_2… s_n $) ** (** Paraphrase von Subjekt und Objekt) **). Daher können Sie für $ c_i $ gegen $ s_1s_2… s_n $ spielen und den Gewinnzug wählen. Wenn „R“ in $ s_1s_2… s_n $ am meisten ist, sind „P“ und „S“ die ersten. Wenn es viele gibt, sollten "R" und "P" am meisten sein, und wenn es viele gibt, sollte "S" verwendet werden. Da dies für jedes $ i $ gesagt werden kann, ist es auch ausreichend, eine Zeichenfolge mit der Länge der Häufigkeit von Janken auszugeben.

B.py

t=int(input())
for i in range(t):
    S=input()
    l=len(S)
    r=S.count("R")
    s=S.count("S")
    p=S.count("P")
    m=max(r,s,p)
    if m==r:
        print("P"*l)
    elif m==s:
        print("R"*l)
    else:
        print("S"*l)

C-Problem

Ich dachte, dass es keine überschüssigen Leute geben sollte, die es falsch verstanden haben, aber wenn Sie genau hinschauen, heißt es, dass es möglicherweise überschüssige Leute gibt. Es ist ein Spiegelbild.

In diesem Fall sollten ** die erfahrensten Programmierer kombiniert werden, um ** $ x $ zu überschreiten, und es besteht die Möglichkeit, dass einige Programmierer $ x $ nicht überschreiten, selbst wenn sie am Ende kombiniert werden. Solche Kombinationen können ignoriert werden.

Mit dieser gierigen Methode kann ** die kleinste Anzahl von Personen eine Gruppe bilden **, so dass gesagt werden kann, dass die Anzahl der Gruppen die größte ist.

C.py

t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    now=[100000000000,0]
    for i in range(n):
        now=[min(now[0],a[i]),now[1]+1]
        if now[0]*now[1]>=x:
            d.append(now)
            now=[100000000000,0]
    print(len(d))

D Problem

Ich habe das auch falsch verstanden und es schwierig gemacht zu glauben, dass ** Berserk zwei diskontinuierliche Personen spezifizieren kann **. Eigentlich ist es nicht so schwierig, weil nur zwei Leute hintereinander sind.

Menschen, die kontinuierlich sind, können besiegt werden. Achten Sie daher auf den Teil, in dem die Person, die besiegt, kontinuierlich ist ** (im Folgenden als kontinuierlicher Teil bezeichnet). Wenn Sie die letzte verbleibende Person in einem fortlaufenden Teil mit Berserk besiegen möchten, muss eine der nicht besiegten Personen ($ L $ und $ R $), die diesen Teil einklemmt, ** mehr Macht als diese Person * haben. * Wir brauchen also die Informationen der Person, die sie einschließt.

Wenn hier die Länge des fortlaufenden Teils durch $ k $ geteilt wird und ein Rest angezeigt wird, muss der Rest durch Berserk und zu diesem Zeitpunkt die Person mit der maximalen Leistung im fortlaufenden Teil ($ X $) reduziert werden. Es ist am besten, die Menschen auf beiden Seiten auszuwählen und zu besiegen.

Wenn $ X $ eine höhere Potenz als $ L $ und $ R $ hat, müssen Sie diese $ X $ mit Fireball ** besiegen, und Fireball kann nicht verwendet werden ($ \ leftrightarrow $ kontinuierliche Teillänge). Wenn (kürzer als $ k $ ist) und wenn die Reihenfolge der verbleibenden Personen unterschiedlich ist, ist das Thema nicht erfüllt, daher sollte -1 ausgegeben werden.

Das obige ist implementiert und sieht wie folgt aus, aber da ich nicht sehr gut darüber nachdenken konnte, wird der Code ein wenig chaotisch.

D.py

n,m=map(int,input().split())
x,k,y=map(int,input().split())
a=list(map(int,input().split()))
c=list(map(int,input().split()))
b=set(c)
d=[]
now=[]
for i in range(n):
    if a[i] not in b:
        now.append(i)
        if i==n-1:
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
    else:
        if now!=[]:
            #Kanten- und Maximalindex(Die Kante ist-1,n kann sein)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#Derjenige, dessen Position nicht in Ordnung ist
now=0
lc=len(c)
for i in range(n):
    if a[i]==c[now]:
        now+=1
        if now==lc:
            break
else:
    exit(print(-1))
l=len(d)
ans=0
for i in range(l):
    e=d[i]
    f=e[2]-e[0]-1
    if e[0]==-1:
        m=a[e[2]]
    elif e[2]==n:
        m=a[e[0]]
    else:
        m=max(a[e[0]],a[e[2]])
    if m>a[e[1]]:
        ans+=(f%k*y)
        ans+=min((f//k)*x,(f//k)*k*y)
    else:
        if f<k:exit(print(-1))
        ans+=(f%k*y)
        #Ich muss sie einmal mit k besiegen
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

Nach dem E-Problem

Ich kann diesmal nicht lösen.