Maski bitowe jako małe zbiory
Reprezentowanie podzbiorów jako liczb całkowitych
Maski bitowe jako małe zbiory to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Liczba całkowita jako zbiór
Pojedyncza liczba całkowita może reprezentować cały zbiór: wartość 1 bitu i oznacza, że element i należy do zbioru. Dzięki temu podzbiory można spakować do jednej małej i szybkiej wartości. 🎒
Zbiór pusty i pełny
Liczba 0 oznacza zbiór pusty, natomiast wartość, w której n najniższych bitów jest włączonych, oznacza obecność każdego elementu.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsDodawanie elementu
Aby dodać element i do zbioru, należy wykonać OR z jego bitem. To dokładnie operacja ustawiania bitu, odczytana teraz jako suma z jednym elementem.
s = 0
s |= (1 << 2) # add element 2Usuwanie elementu
Aby usunąć element i, należy wykonać AND z odwróconym bitem. Element opuszcza zbiór, a wszystkie pozostałe pozostają bez zmian. Jest to różnica zbiorów względem jednego elementu.
s &= ~(1 << 2) # remove element 2Sprawdzanie przynależności
Przynależność elementu i można sprawdzić, wykonując AND z jego bitem. Wynik różny od zera oznacza, że element jest członkiem zbioru.
if s & (1 << 2):
print('2 is in the set')Suma i część wspólna
OR dwóch masek daje ich sumę, a AND — ich część wspólną. Operacje na całych zbiorach stają się po jednej instrukcji maszynowej.
union = a | b
inter = a & bRozmiar zbioru to popcount
Liczba elementów maski bitowej to po prostu liczba jej ustawionych bitów. Aby natychmiast uzyskać rozmiar, należy użyć bit_count.
size = mask.bit_count()Przechodzenie po wszystkich podzbiorach
Dla n elementów liczby całkowite od 0 do 2^n - 1 wyliczają każdy podzbiór. Jedna prosta pętla po zakresie obejmuje je wszystkie.
for mask in range(1 << n):
pass # mask is one subsetSzybkie przechodzenie po podmaskach
Aby odwiedzić tylko podzbiory danej maski, należy użyć klasycznej pętli po podmaskach. Przechodzi ona przez każdy podzbiór w kolejności malejącej.
sub = mask
while sub:
sub = (sub - 1) & maskTutaj działa DP na maskach bitowych
Maski bitowe stanowią stan wielu problemów typu DP, takich jak problem komiwojażera, w którym maska śledzi odwiedzone wierzchołki.
Należy utrzymywać małe n
Przy 2^n podzbiorach ta sztuczka pozostaje praktyczna tylko dla małych wartości n, zazwyczaj do około 20. Powyżej tej granicy liczba gwałtownie rośnie. ⚠️
Szybkie sprawdzenie
Jeszcze jedno pytanie o zbiorze reprezentowanym przez maskę.
Podsumowanie: zbiory jako maski bitowe
Zbiór można przechowywać w jednej liczbie całkowitej, dodawać i usuwać elementy za pomocą masek oraz przechodzić po każdym podzbiorze. Otwiera to drogę do szybkiego DP na maskach bitowych. 🎉
Często zadawane pytania
Czy lekcja „Maski bitowe jako małe zbiory” jest bezpłatna?
Tak — pełny tekst „Maski bitowe jako małe zbiory” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Maski bitowe jako małe zbiory”?
Reprezentowanie podzbiorów jako liczb całkowitych Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Maski bitowe jako małe zbiory”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- AND, OR, XOR i przesunięcia
- Ustawianie, czyszczenie i przełączanie bitu
- Zliczanie bitów i najniższy ustawiony bit
- Maski bitowe jako małe zbiory