Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe versucht, zwei Fragen gleichzeitig zu stellen, indem ich mich an Problem B gehalten habe, aber ich konnte es nicht lösen. Es war sehr enttäuschend, denn der 200. Platz war kein Traum, wenn er gelöst wurde. Ich werde jeden Tag hart arbeiten, um diese Probleme eines Tages während des Wettbewerbs zu lösen.

Außerdem habe ich das Problem vergessen, nachdem ich das Problem von Edufos Bacha überprüft habe, das ich letzte Woche gelöst habe. Wenn ich es also so löse, dass es in Zukunft nicht mehr passiert ** Ich werde es definitiv bis zum nächsten Tag überprüfen ** ich will

Problem A

** Ich habe das längste gemeinsame Präfix als den längsten gemeinsamen Teilstring missverstanden **, und es war gefährlich, weil es ein DP zu sein schien.

Da es sich um das längste gemeinsame Präfix handelt, sollte sich $ s [i], s [i + 1] $ um den angegebenen Betrag von $ a [i] $ unterscheiden. Zur Vereinfachung der Implementierung wird ** nur a oder b ** in der Zeichenfolge verwendet. Da $ a [i] $ bis zu 50 betragen kann, wird die Länge der Ausgabezeichenfolge ** auf 50 ** vereinheitlicht.

Wenn die Zeichenfolge, die am $ i $ th ausgegeben werden soll, $ s [i] $ ist, unterscheidet sich das $ s [i + 1] $ von dem $ s [i] $ von vorne zum $ a [i] $ th ( A sollte b sein, b sollte a) sein und $ a [i] + 1 $ sollte ab dem dritten gleich sein.

`A.py`


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s="a"*50
    ans=[s]
    for i in range(n):
        s=""
        for j in range(50):
            if j<a[i]:
                s+=ans[-1][j]
            else:
                if ans[-1][j]=="a":
                    s+="b"
                else:
                    s+="a"
        ans.append(s)
    for i in range(n+1):
        print(ans[i])

B1-Problem, B2-Problem

Zuerst dachte ich, ich würde die Anzahl der Sekunden (oder wie hoch die Welle ist) an jedem Punkt speichern und DP machen, aber das ** B2-Problem schien zu spät zu sein, also $ O (N) Ich dachte an eine neue Richtlinie **, die $ wäre.

Hier kann die Zeit, die an jedem Punkt sein kann, $ 0 $ ~ $ min (k, l-d_i) $ und $ 2t-min (k, l-d_i) $ unter $ mod \ 2K $ sein. Es wird ~ $ 2t-1 $, und Sie können sehen, dass es sich um einen ** durchgehenden Abschnitt ** handelt. Da es 1 Sekunde dauert, um zum nächsten Punkt zu schwimmen, ** Denken Sie über den gemeinsamen Teil des Abschnitts nach, indem Sie den Abschnitt verschieben? Ich dachte nach **, aber ich konnte nicht auf die Idee kommen, die Abschnitte zu einem zu kombinieren, oder ich vergaß, über den Fall nachzudenken, in dem der Abschnitt $ 2k $ betragen würde (später beschrieben), also musste ich zum Punkt des Bedauerns gehen.

(Von hier aus wird es nach dem Wettbewerb eine Überlegung sein.)

Zunächst wird der Abschnitt oben in zwei Abschnitte unterteilt. Wenn es sich jedoch um $ -min (k, l-d_i) $ ~ $ min (k, l-d_i) $ handelt, ** kombinieren Sie die Abschnitte zu einem **. Ich kann. Darüber hinaus ist es einfach zu handhaben, da es ** bei ** 0 symmetrisch wird.

Betrachten Sie auf dieser Grundlage ** die gierige Methode **, die die Grundlage des Übergangsproblems (dann DP) bildet. Hier werden wir uns mit der fünften Stichprobe befassen. Die Eingabe ist wie folgt. (Sie können auch sehen, dass die gierige Methode mit ** $ O (N) $ ** durchgeführt werden muss.)

7 2 3
3 0 2 1 3 0 1

Darüber hinaus wird der Abschnitt von der obigen Eingabe unten gezeigt. Die Zeitachse ist von oben nach unten.

Ziehen Sie in der obigen Abbildung den Übergang von der linken Seite (näher am Strand) in Betracht. In der folgenden Abbildung ist jedoch ein Beispiel dargestellt. Die rote Linie zeigt, wie es 1 Sekunde dauert, um zum nächsten Punkt im Übergang zu gelangen.

Hier geht der rote Pfeil diagonal nach unten, daher sollte die Quelle des ** Pfeils so hoch wie möglich sein ** (um in das Intervall zu passen). Wenn der Abschnitt $ 2k $ beträgt, können Sie immer dort bleiben **, so dass Sie jederzeit abreisen können. Daher habe ich versucht, den obersten Teil des Abschnitts ** als Quelle des Pfeils ** auszuwählen, aber für den grünen Pfeil funktioniert dies nicht. Wenn sich die Pfeilspitze wie folgt über dem Abschnitt befindet, können Sie den Pfeil ** so verschieben, dass sich die Pfeilspitze oben im Abschnitt befindet. Durch Wiederholen dieses Vorgangs kann Nein ausgegeben werden, wenn die Pfeilspitze in keinem Abschnitt über den Abschnitt hinausragt. Ja, und wenn sogar ein Abschnitt hervorsteht.

`B.py`


#Gierig simulieren
#So klein wie möglich sein
for _ in range(int(input())):
    n,k,l=map(int,input().split())
    d=list(map(int,input().split()))
    seg=[]
    for i in range(n):
        if l-d[i]<0:
            print("No")
            break
        #Stellen Sie sicher, dass das Ende 0 oder mehr ist
        seg.append([-min(l-d[i],k),min(l-d[i],k)])
    else:
        now=seg[0][0]
        for i in range(1,n):
            if seg[i]==[-k,k]:
                now=seg[i][0]
            else:
                now+=1
                if now<seg[i][0]:
                    now=seg[i][0]
                elif now>seg[i][1]:
                    print("No")
                    break
        else:
            print("Yes")

C-Problem

Ist es gut oder schlecht, weil ich es mit Esper zur Hälfte bestanden habe?

Im Folgenden ist das $ i $ th von $ a, b $ $ a_i, b_i $ und die größeren (oder kleineren) Alphabete sind in alphabetischer Reihenfolge.

Es war nur eine Frage der Gier. Vorerst wird $ a_i, b_i simuliert, indem $ verschiedene Alphabete geändert werden, aber ** sich in eine Richtung bewegen, die keinen Verlust verursacht **. Vorher können Sie nicht von $ a $ nach $ b $ wechseln, wenn $ a_i> b_i $, da dieses Problem das Alphabet nur vergrößern kann (andernfalls ändert es sich immer von $ a $ nach $ b $). Sie können).

Da Sie das Alphabet nur vergrößern können, können Sie zunächst feststellen, dass es besser erscheint, sich für das kleinere Alphabet ** $ a $ ** zu entscheiden. Wenn es nur ein Alphabet gibt, das Sie für $ a $ ändern möchten, müssen Sie nur dieses Alphabet ändern. Wenn es jedoch mehrere Alphabete gibt, die Sie für ** $ a $ ** ändern möchten, entsprechen alle Alphabete jedem. Es ist am besten, zum kleinsten der von Ihnen verwendeten $ b $ -Alphabete zu wechseln. Dies liegt daran, dass es keinen Verlust gibt, selbst wenn Sie es ändern **, und es besteht die Möglichkeit, dass Sie neue mit demselben Alphabet erstellen können (dies ist das erste Muster des Beispiels. ** ← Wenn Sie es nicht verstehen, versuchen Sie es mit dem Beispiel! **).

Da in $ a und b $ höchstens 20 Alphabete vorkommen, kann die Simulation in etwa 20 Mal abgeschlossen werden, und Sie können ein ausreichend schnelles Programm schreiben.

`C.py`


for _ in range(int(input())):
    n=int(input())
    a=list(input())
    b=list(input())
    for i in range(n):
        if a[i]>b[i]:
            print(-1)
            break
    else:
        s=sorted(list(set(a)|set(b)))
        ans=0
        for j in s:
            f=False
            x=set()
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    x.add(b[k])
                    f=True
            x=sorted(list(x))
            for k in range(n):
                if a[k]==j and a[k]!=b[k]:
                    a[k]=x[0]
            if f:ans+=1
        print(ans)

Nach D Problem

Ich werde diesmal überspringen

[PYTHON] Codeforces Runde # 659 (Div. 2) Bacha Review (8/5)