Löse mit Python [100 ausgewählte Fragen aus der Vergangenheit, die Anfänger und Fortgeschrittene lösen sollten] (010 --014 Vollständige Suche: Bit vollständige Suche)
1. Zweck
Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.
Dieser Artikel ist "010 - 014 Vollständige Suche: Bit Vollständige Suche".
2. Zusammenfassung
Bisher wurde `itertools.product``` verwendet, um` (0, 1) `` `zu generieren, wenn eine Vollbit-Suche durchgeführt wurde, aber ich habe versucht, es mit Bitverschiebung für später zu lösen. ..
3. Hauptgeschichte
010 --014 Vollständige Suche: Bit Vollständige Suche
010. ALDS_5_A - Runde
Antworten
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
check_list = [0] * (2000 * 20 + 1)
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
check_list[total] = 1
for m in M:
if check_list[m]:
print('yes')
else:
print('no')
Legt fest, ob alle Elemente in der Liste "A" verwendet werden oder nicht und ob die Summe in der Liste "M" enthalten ist. Zuerst habe ich den folgenden Code verwendet, aber es war eine Triple-for-Schleife und ich konnte es nicht rechtzeitig schaffen. Da die Geschwindigkeit langsamer ist, wenn die berechnete "Summe" jedes Mal mit der "m" verglichen wird, wird die "Checkliste" mit der berechneten "Summe" als Index markiert. Danach müssen Sie den Index `` `m``` erneut überprüfen.
#Ich kann es nicht rechtzeitig schaffen
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
for m in M:
ans = 'no'
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
if total == m:
ans = 'yes'
break
print(ans)
Antworten
N, M = map(int, input().split()) #N ist die Anzahl der Schalter, M ist die Anzahl der Glühbirnen
lights = [[0] * N for _ in range(M)]
for i in range(M):
temp = list(map(int, input().split())) #Der 0. gibt die Anzahl der Schalter an, und der 1. und die nachfolgenden Schalter geben die Schalter an.
k = temp[0]
switches = temp[1:]
for j in range(k):
lights[i][switches[j]-1] = 1
P = list(map(int, input().split())) #Leuchtet, wenn die durch 2 geteilte Zahl gleich dem Element ist
answer_count = 0
for i in range(2**N): #Bit-Suche
flag = True
for k in range(M): #Informieren Sie sich über alle Glühbirnen
count = 0
for j in range(N): #Führen Sie für Zahlen mit 1 Flag in Bit
if (i >> j) & 1:
count += lights[k][j]
if count % 2 != P[k]: #Wenn auch nur eine Glühbirne nicht mit p übereinstimmt, setzen Sie das Flag auf False und brechen Sie
flag = False
break
if flag: #Löschen Sie alle und erhöhen Sie die Anzahl, wenn das Flag True ist
answer_count += 1
print(answer_count)
Die Problemstellung ist etwas schwer zu verstehen. Da es schwierig ist, mit der Eingabe umzugehen, haben wir einen Weg gefunden, um die Eingabe zu empfangen, und eine zweidimensionale Anordnung von Glühbirnen auf der vertikalen Achse und Schalter auf der horizontalen Achse erstellt. In dieser Anordnung wird 1 eingestellt, wenn jede Glühbirne und jeder Schalter angeschlossen sind, und 0 wird eingestellt, wenn sie nicht angeschlossen sind.
Wenn dieses Array erstellt wird, kann die Bitsuche einfach durchgeführt werden. Die Politik ist
- Erstellen Sie eine zweidimensionale Anordnung von Glühbirnen und Schaltern wie oben beschrieben
- Bei allen Schaltern Bit-Vollsuche, ob ein- oder ausgeschaltet werden soll (realisiert durch i und j in der for-Anweisung).
- Überprüfen Sie, ob alle Glühbirnen im Zustand jedes Bits leuchten (realisiert durch k in der for-Anweisung).
- Wenn Sie prüfen, ob die Glühbirne leuchtet, setzen Sie die Informationen mit
`flag``` und wenn`flagzu `` `Falsewird, - Zählen Sie die Anzahl der Zustände, in denen
`flag``` zu`True``` wird und das ist die Antwort ist.
012. AtCoder-Anfängerwettbewerb 002 D - Fraktion
Antworten
import itertools
N, M = map(int, input().split()) #N ist die Anzahl der Mitglieder, M ist die Anzahl der Beziehungen
members = list(range(N))
relation = [[0] * N for _ in range(N)] #Beziehungsmatrix
for _ in range(M):
x, y = map(int, input().split())
x -= 1
y -= 1
relation[x][y] = 1
relation[y][x] = 1
max_answer = 0
for group_num in range(1, N+1): #Probieren Sie alle Personen in der Gruppe aus
temp_answer = 0
for c in itertools.combinations(members, group_num): #Listen Sie eine bestimmte Anzahl von Mitgliedern auf
flag = True
for base_c in c: #Eine Person, die Beziehungen überprüft
for check_c in c: #Zu überprüfende Mitglieder
if base_c == check_c: #Überprüfe mich nicht
continue
if relation[base_c][check_c] == 0: #Brechen Sie sofort, wenn keine Beziehung besteht
flag = False
break
if not flag:
break
if flag: #OK, nur wenn das Flag True ist
temp_answer = group_num
max_answer = max(max_answer, temp_answer)
print(max_answer)
Ich konnte es nicht ohne itertools tun, also hatte ich keine andere Wahl, als itertools zu verwenden.Ich habe Kombinationen verwendet.
Der Code ist etwas kompliziert, aber was ich mache, ist einfach:
1. ```N```Beliebig viele Personen, die aus den Mitgliedern des Landtages extrahiert werden sollen```group_num``Konkretisieren. Diese 1~Ich werde bis zu N Leute machen
2. ```N```Person```members```Von```group_num```Listen Sie alle Fälle auf, um Personen zu extrahieren
3.Jedes Mitglied(```base_c```)Über die in 2 oben extrahierten Mitglieder(```check_c```)Überprüfen Sie, ob Sie es wissen
4.Achten Sie darauf, sich beim Überprüfen nicht zu überprüfen, und wenn Sie sich nicht sofort kennenlernen```break```Ich werde tun
5.Alle Gesetzgeber(```base_c```)Wenn beurteilt wird, dass es eine Bekanntschaftsbeziehung in gibt(```flag==True```)Ist das```group_num```Ist ein Kandidat für die Antwort
6. 1~Wiederholen Sie 6```group_num```Maximalwert ist die Antwort
ist.
---
### 013. [JOI 2008 Qualifying 5-Reis-Cracker](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e)
####Antworten
```python
import numpy as np
R, C = Karte (int, Eingabe (). Split ()) # R: vertikal, C: horizontal
grid = np.array([list(map(int, input().split())) for _ in range(R)])
max_answer = 0
for i in range(2**R):
copy_grid = grid.copy () # Erstellen Sie eine Kopie, da die Matrix neu geschrieben wird
for row in range(R):
if (i >> row) & 1: # Führen Sie eine Bitsuche für eine kleine Anzahl von Zeilenrichtungen durch
copy_grid [row ,:] = copy_grid [row ,:] ^ 1 # Invertiere 0,1 mit Bitoperation
col_sum = copy_grid.sum (axis = 0) # Ermittelt die Summe jeder Spalte
for col in range(C):
if col_sum [col]> = R // 2 + 1: # 1 Drehen Sie um, wo es viele gibt
copy_grid[:, col] = copy_grid[:, col] ^ 1
answer = R * C - copy_grid.sum()
max_answer = max(max_answer, answer)
print(max_answer)
Wie Sie im Hinweis sehen können, ist die Obergrenze von R klein. Führen Sie daher eine vollständige Suche nach R durch und nehmen Sie Feineinstellungen auf der C-Seite vor. Die Politik ist 1.Probieren Sie alle Stellen aus, um in R-Richtung umzudrehen 2.Drehen Sie nach dem Umdrehen in R-Richtung als Feineinstellung in C-Richtung nur den Teil um, in dem sich viele Reihen befinden, die 1 sind. 3.Zählen Sie die Anzahl der Nullen in der resultierenden Matrix(Ganzes Quadrat-gesamt) 4.Die Antwort ist diejenige, die das Maximum jedes gezählten Ergebnisses nimmt
ist.
Das Verfahren zum Konvertieren von 0 in 1 und 1 in 0, bei dem es sich um eine umzudrehende Operation handelt, ist eine Bitoperation.^1Wird genutzt.
014. Square869120Contest #4 B - Buildings are Colorful!
####Antworten
import itertools
N, K = map (int, input (). Split ()) # N ist die Anzahl der Gebäude, malen mehr als K Farbe
A = list(map(int, input().split()))
N_index = Liste (Bereich (1, N)) # Weil das am weitesten links stehende fest ist
min_cost = float('inf')
für target_indexes in itertools.combinations (N_index, K-1): Probieren Sie alle Möglichkeiten aus, um K-1 aus #N_index auszuwählen
cost = 0
copy_A = A.copy()
for i in target_indexes:
if copy_A[i] <= max(copy_A[:i]):
diff = max (copy_A [: i]) --copy_A [i] # Stellen Sie für das Zielgebäude 1 größer als max des Gebäudes links davon ein
copy_A[i] += diff + 1
cost += diff + 1
min_cost = min(min_cost, cost)
print(min_cost)
Die Politik ist
1.Das Gebäude ganz links ist fixiert
2.Ab dem zweiten GebäudeK-1Versuchen Sie den ganzen Weg zu wählen
3.Index des ausgewählten Gebäudestarget_indexes Lagern Sie in und überprüfen Sie die Höhe jedes Gebäudes
4.GebäudeiIst die maximale Höhe des Gebäudes davor+Gebäude zu sein 1iStellen Sie die Höhe descostAggregieren als
5.Nachdem Sie alle oben genannten Schritte ausgeführt habencostDie Antwort ist die, die den Mindestwert von annimmt
ist.
Recommended Posts