[PYTHON] Yukicoder-Wettbewerb 268 Bewertung

Ergebnis

Impressionen

Ich denke, der minimale Zug wurde gemacht. Ich finde es gut, dass ich das D-Problem lesen konnte, ohne aufzugeben. Ich konnte die B- und C-Probleme anhand der Antworten verstehen, aber ich werde diesmal überspringen, da es sich um eine Lösung handelt, die schwer zu erlernen scheint.

Problem A

Normalerweise würde ich DP gerne für ein solches Problem in Betracht ziehen, aber es ist schwierig, weil $ n $ höchstens $ 10 ^ {18} $ ist. Daher werden wir das Experiment durchführen und denken, dass es eine Art Regel haben könnte **.

Wenn bei den Koordinaten $ x $ sowohl $ x + 1 $ als auch $ x + 6 $ Spielübermasse sind, sind sowohl $ x + 2 $ als auch $ x + 5 $ Spielübermasse, $ x + 3 Wenn sowohl $ als auch $ x + 4 $ Spielübermasse sind, dann ist $ x $ auch Spielübermasse. Wenn Sie sich die Spielübermasse oben ansehen, erhöht sich daher die Spielübermasse in der Reihenfolge **. ** Experimentieren Sie, um zu überlegen, wie Sie die Übermasse des Spiels erhöhen können ** und die folgende Abbildung.

Wenn Sie es wie oben beschrieben ausschreiben, wenn eine Reihe von Spielübermassen vorhanden sind, sind die Quadrate, die ** 9 oder mehr von der kleineren Spielübermasse (✳︎) dieser Gruppe entfernt sind, immer die Spielübermasse **. Wenn also das Quadrat von (✳︎) bei den Koordinaten von 10 oder mehr existiert, ist das Spiel beendet. Wenn daher ein Quadrat (✳︎) vorhanden ist, wird Nein ausgegeben und der Ausgang ausgeführt. Um das Vorhandensein einer Menge von Spielübermassen zu bestimmen, bereiten Sie außerdem eine Mengenstruktur "b" vor, die die Spielübermasse verwaltet, und in der Reihenfolge der größeren Spielübermasse $ x $, $ x + 1, x + 3, x + 5 Finden Sie heraus, ob eines der $ im $ b $ enthalten ist.

Wenn als nächstes ** (✳︎) Quadrate bei Koordinaten von 9 oder weniger ** existieren, suchen Sie nach Quadrat 9 → 1, welches Quadrat vorbei ist, und das neu erstellte Spiel ist in der Reihenfolge von $ b $ Alles was Sie tun müssen, ist es zu speichern und schließlich festzustellen, ob $ b $ 1 enthält.

A.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=set(a)
for i in range(k-1,-1,-1):
    if a[i]<=9:
        break
    else:
        if a[i]+1 in b:
            print("No")
            exit()
        if a[i]+3 in b:
            print("No")
            exit()
        if a[i]+5 in b:
            print("No")
            exit()
for j in range(9,0,-1):
    if j in b:
        if j+1 in b:
            if j-3>=1:
                b.add(j-3)
        if j+3 in b:
            if j-2>=1:
                b.add(j-2)
        if j+5 in b:
            if j-1>=1:
                b.add(j-1)
if 1 in b:
    print("No")
    exit()
print("Yes")

B, C Problem

Ich werde diesmal überspringen.

D Problem

Ich denke, diesmal war es das einfachste Problem.

Scores können für jedes Bit ** berechnet werden **, da es nur bitweise oder und bitweise und Operationen gibt. Außerdem gibt es nur zwei Anfangswerte für jedes Bit, 0 oder 1, und wenn Sie ** die Punktzahl für jedes Bit vorberechnen **, können Sie sich einfach alle Bits ansehen, wenn der Anfangswert angegeben wird ** Sie finden es unter. Daher wird das Array zum Speichern in der Vorberechnung auf "check" und "$ check [i] [j]: = $ gesetzt (die Punktzahl, wenn der Anfangswert des $ i $ -Bits $ j $ ist, aber $ j = 0,1 $) (✳︎). Wir werden in Betracht ziehen, dies unten zu erfragen.

Berechnen Sie nun die Punktzahl, indem Sie das $ i $ -Bit und $ a \ _i $ in der Reihenfolge betrachten, in der der Anfangswert $ k $ ist. Außerdem ist die Ganzzahl, die ich gemäß der Problemstellung habe, $ x $ (natürlich $ x = k $ am Anfang). Und wenn Sie sich die $ j $ -te Ganzzahl ansehen (das $ i $ -Bit wird als $ a \ _ {ji} $ dargestellt), haben Sie die Ganzzahl $ x $ (aber den Wert des $ i $ -Bits) Vorausgesetzt, die auszuführende Operation ist entweder $ und $ oder $ oder $. Zu diesem Zeitpunkt sind die Änderung von $ x $ und die Änderung von $ check [i] [k] $ in der folgenden Tabelle aufgeführt.

Wenn Sie eine Tabelle wie oben erstellen **, können Sie $ x $ und die Punktzahl visuell erfassen ** und die Variablen $ i, k, j $ einfach umlaufen. .. Wenn Sie $ check [i] [j] $ haben, können Sie die Abfrage einfach berechnen, indem Sie sie addieren und multiplizieren.

(✳︎)… Um genau zu sein, ist $ check [i] [j] \ times 2 ^ i $ die Punktzahl für dieses Bit.

D.py

n,q=map(int,input().split())
a=list(map(int,input().split()))
check=[[0,0] for i in range(32)]
s=list(map(int,input()))
for i in range(32):
    #Ob der Ausgangszustand 0 oder 1 ist
    for k in range(2):
        x=k
        for j in range(n):
            if (a[j]>>i)&1:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
                else:
                    if x==0:
                        check[i][k]+=1
                        x=1
                    else:
                        check[i][k]+=0
                        x=1
            else:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=1
                        x=0
                else:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
#print(check)
t=list(map(int,input().split()))
for _ in range(q):
    z=t[_]
    ans=0
    for i in range(32):
        ans+=(check[i][(z>>i)&1]*(2**i))
        #print(ans)
    print(ans)

Nach dem E-Problem

Ich werde diesmal überspringen.