#47 Problem
** Gedanken ** Angesichts der Einschränkungen sind $ N und M $ nur 10 oder weniger, daher dachte ich, ich könnte sie mit Gewalt lösen, also habe ich sie implementiert. Da der Schalter ein- / ausgeschaltet ist, werden alle Bits durchsucht. Der Berechnungsbetrag beträgt $ O (2 ^ N) $, aber da $ N $ klein ist, ist er nicht TLE. Erstellen Sie eine Bool-Liste, in der jedes Element den Ein / Aus-Zustand jedes Schalters anzeigt, und überprüfen Sie den Beleuchtungsstatus der Glühbirne in jedem Zustand.
n, m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
on = [False] * n
for j in range(n): #Bit vollständige Suche
if ((i>>j) & 1):
on[n - j - 1] = True
g = 0
for j in range(m): #Status jeder Glühbirne
c = 0
for s in range(1,len(ks[j])):
if on[ks[j][s]-1]:
c += 1
if c % 2 == p[j]: #Wenn die Glühbirne leuchtet, g+=1
g += 1
if g == m: #Ans wenn alle g leuchten+=1
ans += 1
print(ans)
Vor kurzem habe ich es grob implementiert, weil der Rechenaufwand gering ist. Deshalb werde ich mein Bestes tun, um die Erklärung sorgfältig zu lesen und sie ordentlich umzusetzen. Wir sehen uns wieder, gute Nacht.
Recommended Posts