#47 Problème
** Pensées ** En regardant les contraintes, $ N et M $ sont aussi petits que 10 ou moins, alors j'ai pensé que je pourrais les résoudre par la force, alors je l'ai implémenté. Puisque le commutateur est activé / désactivé, tous les bits sont recherchés. Le montant du calcul sera $ O (2 ^ N) $, mais comme $ N $ est petit, ce ne sera pas TLE. Créez une liste booléenne dans laquelle chaque élément affiche l'état marche / arrêt de chaque interrupteur et vérifiez l'état d'éclairage de l'ampoule dans chaque état.
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): #recherche peu complète
if ((i>>j) & 1):
on[n - j - 1] = True
g = 0
for j in range(m): #État de chaque ampoule
c = 0
for s in range(1,len(ks[j])):
if on[ks[j][s]-1]:
c += 1
if c % 2 == p[j]: #Si l'ampoule est allumée, g+=1
g += 1
if g == m: #Ans si tous les g sont allumés+=1
ans += 1
print(ans)
Récemment, je l'ai mis en œuvre à peu près parce que la quantité de calcul est faible, je ferai donc de mon mieux pour lire attentivement l'explication et la mettre en œuvre proprement. A bientôt, bonne nuit.
Recommended Posts