Máscaras de Bits como Pequenos Conjuntos
Represente subconjuntos como inteiros.
Máscaras de Bits como Pequenos Conjuntos é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Um inteiro como conjunto
Um único inteiro pode representar um conjunto inteiro: se o bit i for 1, isso significa que o elemento i pertence ao conjunto. Assim, subconjuntos cabem em um único valor pequeno e rápido. 🎒
Os conjuntos vazio e completo
O número 0 é o conjunto vazio, enquanto um valor com os n bits mais baixos ativados significa que todos os elementos estão presentes.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAdicionar um elemento
Para adicionar o elemento i ao conjunto, aplique OR ao bit correspondente. Esse é exatamente o procedimento de ativar um bit, agora interpretado como uma união com um item.
s = 0
s |= (1 << 2) # add element 2Remover um elemento
Para remover o elemento i, aplique AND ao bit invertido. O elemento sai do conjunto e todos os demais permanecem no lugar. Essa é a diferença de conjuntos por um item.
s &= ~(1 << 2) # remove element 2Verificar pertencimento
Verifique se o elemento i pertence ao conjunto aplicando AND ao seu bit. Um resultado diferente de zero significa que ele é um membro do conjunto.
if s & (1 << 2):
print('2 is in the set')União e interseção
Aplique OR a duas máscaras para obter a união; aplique AND para obter a interseção. Operações sobre conjuntos inteiros tornam-se uma única instrução de máquina cada.
union = a | b
inter = a & bO tamanho do conjunto é a contagem de bits 1
A quantidade de elementos em uma máscara de bits é simplesmente sua contagem de bits definidos. Use bit_count para obter o tamanho instantaneamente.
size = mask.bit_count()Percorrer todos os subconjuntos
Para n elementos, os inteiros de 0 a 2 elevado a n menos 1 enumeram todos os subconjuntos. Um simples laço de intervalo cobre todos eles.
for mask in range(1 << n):
pass # mask is one subsetIterar rapidamente pelos subconjuntos de uma máscara
Para visitar apenas os subconjuntos de uma determinada máscara, use o laço clássico de submáscaras. Ele percorre cada subconjunto em ordem decrescente.
sub = mask
while sub:
sub = (sub - 1) & maskA DP com máscaras de bits acontece aqui
As máscaras de bits representam o estado em muitos problemas de DP, como o problema do caixeiro viajante, no qual a máscara registra quais nós você já visitou.
Mantenha n pequeno
Como existem 2 elevado a n subconjuntos, esse truque só é viável para valores pequenos de n, geralmente até cerca de 20. Depois disso, a quantidade cresce explosivamente. ⚠️
Verificação rápida
Mais uma pergunta sobre conjuntos representados por máscaras.
Recapitulação: conjuntos com máscaras de bits
Você pode armazenar um conjunto em um único inteiro, adicionar e remover elementos com máscaras e percorrer todos os subconjuntos. Isso permite usar DP rápida com máscaras de bits. 🎉
Perguntas Frequentes
A aula “Máscaras de Bits como Pequenos Conjuntos” é grátis?
Sim — o texto completo de “Máscaras de Bits como Pequenos Conjuntos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Máscaras de Bits como Pequenos Conjuntos”?
Represente subconjuntos como inteiros. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Máscaras de Bits como Pequenos Conjuntos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- AND, OR, XOR e Deslocamentos
- Defina, Limpe e Alterne um Bit
- Conte Bits e o Bit Definido Mais Baixo
- Máscaras de Bits como Pequenos Conjuntos