[PYTHON] Codeforces Runde # 658 (Div. 2) Bacha Review (7/29)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe es wieder falsch verstanden, wie beim letzten Mal. Siehe C-Problem für Details. Es ist ineffizient, nur 3 Fragen innerhalb von 2 Stunden zu lösen, daher werden wir die Anzahl der Probleme, die gelöst werden können, schrittweise erhöhen.

Problem A

Wenn die kürzeste gemeinsame Teilzeichenfolge von $ a $ und $ b $ vorhanden ist, beträgt die Länge 1, sodass Sie eines der gemeinsamen Zeichen von $ a $ und $ b $ ausgeben können. Außerdem können Sie hier herausfinden, ob in $ a $ Zeichen enthalten sind, die auch in $ b $ enthalten sind, und wenn eines davon eine festgelegte Struktur hat, können Sie dies mit $ O (N) $ überprüfen.

A.py

t=int(input())
for _ in range(t):
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    b=set(map(int,input().split()))
    for i in a:
        if i in b:
            print("YES")
            print(f"1 {i}")
            break
    else:
        print("NO")

B-Problem

Zuallererst ist es ein Spielproblem, also ** achte auf den Endzustand **. Wenn Sie auf den Endzustand achten, werden alle Berge 0 sein, aber kurz davor bleibt nur der letzte Berg so wie er ist.

Ich habe hier darauf geachtet, ob ich jeden Berg verlassen soll oder nicht (** Binarisierung! **). Das heißt, wenn die Anzahl der Steine in jedem Berg mehr als 1 beträgt, kann der Spieler, der diesen Berg auswählt, dem Gegner keine Wahl geben. Dies kann erreicht werden, indem nur ein Stein vom Berg entfernt und der anderen Partei übergeben wird.

Wenn ** die Anzahl der Steine im Berg ursprünglich eins ist **, hat der Spieler, der den Berg auswählt, keine andere Wahl, als diesen einen Stein zu entfernen. Wenn Sie auf einem Berg mit mehr als einer Klappe arbeiten, können Sie daher einstellen, ob Sie einen Stein verlassen oder alle Steine von diesem Berg entfernen möchten, je nachdem, ob die Anzahl der Steine im nächsten Berg eins beträgt oder nicht. Wenn ein Berg mit nur einem Stein vom ersten Berg weitergeht, hat der Spieler keine Wahl, sodass der Spieler, der zum ersten Mal einen Berg ohne einen Stein wählen kann, die Wahl hat und gewinnt. Kann als möglich bezeichnet werden

B.py

t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=["First","Second"]
    ans=0
    for i in range(n):
        if a[i]!=1:
            ans=i
            break
    else:
        ans=n-1
    print(s[ans%2])

C1-Problem

Ich habe es komplett falsch verstanden. Ich dachte, dass die Inversionsoperation die gesamte Zeichenfolge ist, aber sie wurde geschrieben, als ich die Problemstellung oft sah, wenn ich sie nur mit dem von mir gewählten Präfix tat. In Codeforces habe ich den englischen Originaltext so gelesen, wie er ist, und es gibt viele Fehler. Daher möchte ich mich darauf konzentrieren, solche nicht wesentlichen Fehler zu beseitigen.

Was das Problem betrifft, sollte die erste Richtlinie darin bestehen, zu berücksichtigen, was mit dem $ i $ -ten Bit passiert (** Abstraktion **). Betrachten Sie zu diesem Zeitpunkt den Fall, dass nur das $ i $ -te Bit invertiert wird. Hier ist dies jedoch möglich, indem Sie in der Reihenfolge $ i $ → $ 1 $ → $ i $ auswählen. Außerdem wird es in dieser Simulation ungefähr 3n $ mal sein. Die erste $ i $ -Operation ändert das $ i $ -te Element in das $ 1 $ -te Element, sodass die $ 1 $ -Operation nur das ursprünglich $ i $ -te Element an diesem $ 1 $ -ten Element und schließlich $ umdreht Betrachten Sie es als Rückgängigmachen mit i $. Wenn Sie es nicht wissen, sollten Sie es zeigen. Ich bin der Meinung, dass solche Probleme nur auffindbar gelöst werden können, daher denke ich, dass das Wichtigste ** Vertrautheit und Experimentieren ** ist.

C1.py

#falsch verstanden ...
t=int(input())
for _ in range(t):
    n,a,b=int(input()),input(),input()
    ans=[]
    for i in range(n):
        if a[i]!=b[i]:
            ans.append(f"{i+1}")
            ans.append("1")
            ans.append(f"{i+1}")
    print(f"{len(ans)}"+" "+" ".join(ans))

Nach C2 Problem

Ich werde diesmal überspringen