[GO] Über etwas vollständige Suche, die häufig bei Wettkampfprofis auftritt Aus den Augen von Anfängern mit Python

zunaechst

Ich war ein Wettkampfprofi und begann Algorithmen zu studieren. Ich möchte die Bit-Vollsuche, die den Beginn des Algorithmus darstellt, mit der Bedeutung der Ausgabe erklären. Ich bin noch ein junger Student, bitte weisen Sie auf Fehler hin. Ich werde in der Hauptgeschichte des Wettbewerbsprofis schreiben.

Was ist etwas vollständige Suche?

Dies ist eine der Methoden der vollständigen Suche. Diese Technik kann verwendet werden, wenn mehrere Variablen vorhanden sind und jede Variable zwei Werte annimmt. Bit bedeutet 0 und 1 im Computer und nimmt zwei Werte an. Es wird mit verglichen. Ich denke, es ist schwer aus der Erklärung der Charaktere zu verstehen, also werde ich ein Beispiel dafür geben.

Beispiel

0,1 Nur die beiden Nummern von können in die Liste aufgenommen werden. Die Länge der Liste beträgt 3. Listen Sie alle möglichen Listen auf.

Antworten

bit.py

for i in range(2**3): #1
    list=[0]*3 #2
    for k in range(3): #3
        if ((i>>k)&1): #4
            list[k]=1 #5
    print(list)

Kommentar

1 Jedes Element in der Liste hat zwei Typen, 1 oder 0, daher beträgt die Anzahl der Elemente 2 ** (die Anzahl der Elemente). 2 Erstellen Sie eine temporäre Liste. Es wird später entsprechend dem Ergebnis der Bitoperation umgeschrieben. Übrigens ist [0] * 3 = [0,0,0]. 3 Da die Länge der Liste 3 beträgt, können Sie sie bis zu zweimal verschieben. 4 Es ist der Kern der Bit-Vollsuche. i >> k bedeutet, i-mal k nach links zu verschieben. Da & und angibt, bedeutet diese Zeile "i >> k bedeutet, wenn i k-mal nach links verschoben wird und 1 wahr ist".

Beispiel im Wettbewerb pro

https://atcoder.jp/contests/abc045/tasks/arc061_a

Wichtige Sache

Bringen Sie nicht # 2 über die for-Schleife

4 ist der Bitoperator

& Ist das logische Produkt von Bitoperationen, | ist die logische Summe, ^ ist die exklusive logische Summe