Le bitmask come piccoli set
Rappresentare i sottoinsiemi come interi
Le bitmask come piccoli set è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Un intero come insieme
Un singolo intero può rappresentare un intero insieme: se il bit i vale 1, l’elemento i appartiene all’insieme. In questo modo i sottoinsiemi vengono compressi in un unico valore compatto e veloce. 🎒
Gli insiemi vuoto e completo
Il numero 0 rappresenta l’insieme vuoto, mentre un valore con i n bit meno significativi tutti attivi indica che sono presenti tutti gli elementi.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAggiungere un elemento
Per aggiungere l’elemento i all’insieme, si attiva il suo bit con OR. È esattamente l’operazione per impostare un bit, vista ora come una unione con un elemento.
s = 0
s |= (1 << 2) # add element 2Rimuovere un elemento
Per rimuovere l’elemento i, si calcola l’AND con il bit invertito. L’elemento lascia l’insieme e tutti gli altri rimangono invariati. Si tratta della differenza tra insiemi applicata a un elemento.
s &= ~(1 << 2) # remove element 2Verificare l’appartenenza
Per verificare se l’elemento i appartiene all’insieme, si calcola l’AND con il suo bit. Un risultato diverso da zero indica che è un elemento dell’insieme.
if s & (1 << 2):
print('2 is in the set')Unione e intersezione
Calcolate l’OR di due maschere per ottenerne l’unione; calcolate l’AND per ottenerne l’intersezione. Le operazioni su interi insiemi diventano così una singola istruzione della macchina ciascuna.
union = a | b
inter = a & bLa dimensione dell’insieme è il popcount
Il numero di elementi in una maschera di bit è semplicemente il conteggio dei bit impostati. Si può usare bit_count per ottenere immediatamente la dimensione.
size = mask.bit_count()Scorrere tutti i sottoinsiemi
Per n elementi, gli interi da 0 a 2 elevato alla n meno 1 enumerano ogni sottoinsieme. Un semplice ciclo su un intervallo li copre tutti.
for mask in range(1 << n):
pass # mask is one subsetIterare rapidamente sui sottomaschera
Per visitare solo i sottoinsiemi di una determinata maschera, si usa il classico ciclo sui sottomaschera. Il ciclo attraversa ogni sottoinsieme in ordine decrescente.
sub = mask
while sub:
sub = (sub - 1) & maskQui entra in gioco la DP con maschere di bit
Le maschere di bit rappresentano lo stato in molti problemi di DP, come il problema del commesso viaggiatore, in cui la maschera tiene traccia dei nodi già visitati.
Mantenere n piccolo
Con 2 elevato alla n sottoinsiemi, questo trucco rimane pratico solo per valori piccoli di n, di solito fino a circa 20. Oltre quel limite, il conteggio cresce esplosivamente. ⚠️
Verifica rapida
Un’ultima domanda sugli insiemi rappresentati come maschere.
Riepilogo: gli insiemi con maschere di bit
È possibile memorizzare un insieme in un solo intero, aggiungere e rimuovere elementi con le maschere e scorrere ogni sottoinsieme. Questo apre la strada a una DP veloce con maschere di bit. 🎉
Domande Frequenti
La lezione «Le bitmask come piccoli set» è gratuita?
Sì — il testo completo di «Le bitmask come piccoli set» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Le bitmask come piccoli set»?
Rappresentare i sottoinsiemi come interi Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Le bitmask come piccoli set»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- AND, OR, XOR e shift
- Impostare, azzerare e invertire un bit
- Contare i bit e il bit impostato meno significativo
- Le bitmask come piccoli set