Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector, Sortowanie, Max / Min, Zaokrąglanie, Silnia, Wartość bezwzględna i Złożoność czasowa.
Z tych lekcji przydadzą się szczególnie trzy rzeczy. Z lekcji o vectorze — iteratory, czyli „strzałki” begin() i end(), gwiazdka *it i pętla for (int x : v). Z lekcji o sortowaniu — porządek rosnący, porządek słownikowy napisów, lower_bound i upper_bound. A z lekcji o złożoności — umiejętność liczenia, ile pracy wykona program, i reguła „około 100 milionów operacji na sekundę”.
Zbiór to pierwsza w kursie struktura danych, która sama pilnuje porządku. Vector trzyma to, co do niego włożysz, dokładnie w tej kolejności i z powtórzeniami — porządek musisz zrobić sam. Zbiór porządkuje wszystko w chwili wkładania. Dzięki temu wiele zadań, które wcześniej wymagały kilkunastu linijek, zamienia się w trzy — a programy, które były za wolne, zaczynają zdążać. Uczymy się tak samo jak dotąd: przepisuj przykłady, rozpisuj zbiory na kartce, zanim klikniesz „Pokaż odpowiedź”, i rób ćwiczenia po każdej części.
Pierwszy zbiór
insert, size, przechodzenie pętlą, a potem count, erase i pytanie „czy to już było?”.
Strzałki i szukanie
Najmniejszy i największy, iteratory, find, lower_bound, upper_bound i najbliższa wartość.
Działania, pary, napisy
Suma, część wspólna i różnica zbiorów, podzbiory, a potem zbiory par, punktów i słów.
multiset i szybkość
Zbiór z powtórzeniami, okna i zachłanne wybory, unordered_set, drzewo w środku i wybór właściwej struktury.
Mapa lekcji
Zbiór — worek bez powtórzeń
Zacznijmy od zadania, które już znasz: ile różnych liczb jest na liście? W lekcji o sortowaniu rozwiązywaliśmy je tak: posortuj, a potem policz miejsca, w których liczba różni się od poprzedniej. Po lewej ten sposób, po prawej — ten sam program ze zbiorem.
int n;
cin >> n;
vector<int> v(n);
for (int &x : v) cin >> x;
sort(v.begin(), v.end());
int ile = 0;
for (int i = 0; i < n; i++)
if (i == 0 || v[i] != v[i - 1]) ile++;
cout << ile << "\n";
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
Lewy program musi pamiętać o sortowaniu, o pierwszym elemencie (i == 0) i o porównywaniu z sąsiadem. Prawy po prostu wrzuca każdą liczbę do zbioru i na końcu pyta, ile w nim jest. Powtórki same odpadają: zbiór nie przyjmuje wartości, którą już ma. Wynik 5 to liczby 1, 2, 5, 8 i 9.
Pierwszy program ze zbiorem
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s; // pusty zbiór liczb całkowitych
s.insert(5);
s.insert(2);
s.insert(8);
s.insert(5); // 5 już jest — nic się nie zmieni
s.insert(2); // 2 też już jest
cout << s.size() << "\n";
for (int x : s) cout << x << " ";
cout << "\n";
return 0;
}
Przeczytajmy go linijka po linijce:
#include <set> — zbiór mieszka w osobnym pliku nagłówkowym, tak jak vector w <vector>. Jeśli piszesz #include <bits/stdc++.h>, zbiór już w nim jest.
set<int> s; — tworzy pusty zbiór o nazwie s. W nawiasach ostrych podajesz typ elementów, dokładnie jak w vector<int>.
s.insert(5); — wkłada 5 do zbioru. Gdy 5 już tam jest, nic się nie dzieje: bez błędu, bez ostrzeżenia.
s.size() — mówi, ile różnych wartości jest w zbiorze. Wstawiliśmy pięć razy, ale różne były tylko trzy.
for (int x : s) — przechodzi zbiór. Elementy wychodzą rosnąco: 2, 5, 8 — chociaż wstawialiśmy je w kolejności 5, 2, 8.
Prześledźmy: co jest w zbiorze po każdej linijce?
| instrukcja | zbiór s po niej | s.size() | co się stało |
|---|---|---|---|
set<int> s; | { } | 0 | pusty zbiór |
s.insert(5); | {5} | 1 | dodany |
s.insert(2); | {2, 5} | 2 | dodany — od razu przed 5 |
s.insert(8); | {2, 5, 8} | 3 | dodany na końcu |
s.insert(5); | {2, 5, 8} | 3 | już był — bez zmian |
s.insert(2); | {2, 5, 8} | 3 | już był — bez zmian |
Pobaw się zbiorem sam. Wpisz liczbę i kliknij insert(x) — albo naciśnij Enter. Wrzuć kilka razy tę samą liczbę i porównaj oba wiersze: w górnym jest wszystko, co wrzuciłeś, po kolei, a w dolnym — to, co naprawdę trzyma zbiór. Przyciski multiset i unordered_set na razie zostaw — poznasz je w częściach 7 i 8.
Dwie zasady zbioru
Zasada 1: każda wartość najwyżej raz. Zbiór pamięta tylko, czy liczba w nim jest, a nie ile razy ją wstawiono. Dlatego size() zawsze mówi, ile jest różnych wartości.
Zasada 2: zawsze rosnąco. Niezależnie od tego, w jakiej kolejności wstawiasz, przechodzenie pętlą for daje elementy od najmniejszego do największego. Nie musisz wywoływać sort — zbiór układa każdą liczbę na właściwym miejscu w chwili wstawiania.
Obie zasady naraz dają coś, co w lekcji o sortowaniu wymagało sort i unique: posortowaną listę bez powtórzeń.
set<int> s;
s.insert(30);
s.insert(-4);
s.insert(17);
s.insert(30);
s.insert(0);
s.insert(-4);
for (int x : s) cout << x << " ";
cout << "\n" << s.size() << "\n";
Wczytywanie liczb do zbioru
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
for (int x : s) cout << x << " ";
cout << "\n";
set<int> s;
int x;
while (cin >> x) {
s.insert(x);
}
cout << s.size() << "\n";
for (int y : s) cout << y << " ";
cout << "\n";
Lewy program zna liczbę danych n z pierwszego wiersza — to schemat, który pojawi się w prawie każdym ćwiczeniu. Do zbioru nie da się wczytać „od razu” jak do vectora przez for (int &x : v) cin >> x; — zbiór nie ma miejsc, w które można by wpisać liczbę. Każdą liczbę najpierw wczytujesz do zwykłej zmiennej, a potem wkładasz przez insert.
Prawy program czyta liczby aż do końca danych (while (cin >> x), znasz to z lekcji o vectorze). Zwróć uwagę na nazwy: x służy do wczytywania, a w pętli wypisującej używamy innej nazwy, y, żeby się nie pomylić.
Zbiór od razu z wartościami — i z vectora
set<int> s = {7, 3, 7, 1, 3};
for (int x : s) cout << x << " ";
cout << "\n" << s.size() << "\n";
vector<int> v = {4, 1, 4, 2, 1};
set<int> s(v.begin(), v.end());
for (int x : s) cout << x << " ";
cout << "\n";
vector<int> w(s.begin(), s.end());
cout << w[0] << " " << w[w.size() - 1] << "\n";
Zbiór można utworzyć od razu z listą wartości w klamrach — tak jak vector. Powtórki znikają już w tej chwili: z pięciu liczb zostają trzy.
Można też utworzyć zbiór z całego vectora: set<int> s(v.begin(), v.end());. W nawiasie podajesz zakres od początku do końca, czyli dwie strzałki, które znasz z lekcji o vectorze. To jedna linijka, która usuwa powtórki i sortuje.
W drugą stronę też działa: vector<int> w(s.begin(), s.end()); przepisuje zbiór do vectora — rosnąco. Po co? Bo vector ma indeksy: w[0] to najmniejsza wartość, a w[w.size() - 1] — największa. Zbiór indeksów nie ma, o czym za chwilę.
Zbiór napisów i zbiór liter
set<string> s;
s.insert("pies");
s.insert("kot");
s.insert("Ala");
s.insert("kot");
s.insert("ala");
cout << s.size() << "\n";
for (string w : s) cout << w << "\n";
Zbiór może trzymać wartości każdego typu, który da się porównywać: liczby, znaki, napisy, pary. set<string> układa słowa w porządku słownikowym — tym samym, którego używa sort na napisach.
Pamiętasz z lekcji o sortowaniu, że wielkie litery są przed małymi? Dlatego „Ala” stoi przed „ala”. Dla zbioru to dwa różne słowa — różnią się jedną literą. Drugi „kot” odpadł, bo jest identyczny z pierwszym.
string slowo = "abrakadabra";
set<char> litery;
for (char c : slowo) litery.insert(c);
cout << litery.size() << "\n";
for (char c : litery) cout << c;
cout << "\n";
set<char> trzyma pojedyncze znaki. Wrzucamy każdą literę słowa „abrakadabra” — jedenaście liter, ale różnych tylko pięć: a, b, d, k, r. Zbiór wypisuje je alfabetycznie, bo litery porównują się kodami ASCII, a kody liter rosną od a do z.
To samo w jednej linijce: set<char> litery(slowo.begin(), slowo.end()); — napis też ma begin() i end(), tak jak vector.
Zbiór nie ma indeksów
set<int> s = {4, 8, 15};
cout << s[0] << "\n"; // BŁĄD: zbiór nie ma indeksów
Najważniejsza różnica między zbiorem a vectorem: w zbiorze nie ma numerów miejsc. Nie napiszesz s[0] ani s[i] — program się nie skompiluje.
Dlaczego? Bo zbiór ciągle się przestawia. Gdy wstawisz 1 do zbioru {4, 8, 15}, wszystkie elementy „przesuną się” o jedno miejsce. Numer miejsca nic by nie znaczył. Zbiór to worek, w którym rzeczy leżą po kolei, ale bez etykiet z numerami.
Zbiór przechodzisz pętlą for (int x : s). Najmniejszy i największy element wyjmiesz bez pętli — nauczysz się tego w części 3. A gdy naprawdę potrzebujesz indeksów, przepisz zbiór do vectora.
vector czy set?
| vector<int> v | set<int> s | |
|---|---|---|
| powtórzenia | zostają | znikają same |
| kolejność | taka, w jakiej wkładasz | zawsze rosnąca |
| dodanie elementu | v.push_back(x) — na koniec | s.insert(x) — na właściwe miejsce |
| liczba elementów | v.size() | s.size() — różnych |
| indeksy | v[i] | nie ma |
| przechodzenie | for (int x : v) | for (int x : s) — rosnąco |
Zasada wyboru jest prosta. Liczy się kolejność z wejścia albo powtórzenia (np. „który był trzeci?”, „ile razy wystąpiło?”) — vector. Liczy się tylko to, jakie wartości wystąpiły (różne, bez powtórzeń, po kolei) — zbiór.
set<int> s; — pusty zbiór. s.insert(x) — wkłada x; gdy x już jest, nic się nie dzieje. s.size() — liczba różnych wartości. for (int x : s) — przechodzi zbiór rosnąco. Zbiór nie ma indeksów: s[0] się nie kompiluje. Napisy układają się słownikowo (wielkie litery przed małymi), znaki — alfabetycznie.
Najpierw rozpisz zbiór na kartce — wstawiaj liczby po kolei i skreślaj powtórki — a dopiero potem kliknij „Pokaż odpowiedź”.
set<int> s;
s.insert(4);
s.insert(1);
s.insert(4);
s.insert(9);
s.insert(1);
cout << s.size();
Pokaż odpowiedź
set<int> s;
s.insert(4);
s.insert(1);
s.insert(4);
s.insert(9);
s.insert(1);
for (int x : s) cout << x << " ";
Pokaż odpowiedź
set<int> s = {5, 5, 5, 5};
cout << s.size();
Pokaż odpowiedź
string t = "mississippi";
set<char> s(t.begin(), t.end());
for (char c : s) cout << c;
Pokaż odpowiedź
set<string> s = {"b", "a", "B", "a"};
for (string w : s) cout << w << " ";
Pokaż odpowiedź
set<int> s;
for (int i = 1; i <= 10; i++) s.insert(i % 3);
cout << s.size();
Pokaż odpowiedź
set<string> s = {"10", "9", "100"};
for (string w : s) cout << w << " ";
Pokaż odpowiedź
set<int>, kolejność byłaby 9 10 100.set<int> s = {-3, 2, -10, 2, 0};
for (int x : s) cout << x << " ";
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
count, erase i empty — czy to już było?
W części 1 zbiór tylko przyjmował liczby. Teraz nauczymy się go pytać i z niego wyjmować. Najczęstsze pytanie w zadaniach brzmi: „czy ta wartość już się pojawiła?”. Ze zbiorem odpowiedź to jedno słowo: count.
count — czy x jest w zbiorze?
set<int> s = {4, 8, 15, 16, 23};
cout << s.count(15) << "\n";
cout << s.count(7) << "\n";
if (s.count(8)) cout << "8 jest\n";
if (!s.count(42)) cout << "42 nie ma\n";
s.count(x) zwraca, ile razy x jest w zbiorze. W zwykłym zbiorze każda wartość jest najwyżej raz, więc wynik to zawsze 1 (jest) albo 0 (nie ma).
Dlatego count świetnie pasuje do if: 1 znaczy prawdę, 0 — fałsz. if (s.count(8)) czytamy „jeśli 8 jest w zbiorze”, a if (!s.count(42)) — „jeśli 42 nie ma w zbiorze”. Wykrzyknik odwraca warunek, znasz go z lekcji o typach.
Nazwa „count” (policz) wydaje się dziwna dla pytania „czy jest?”. Ma sens dopiero w multiset z części 7, gdzie wartość może być kilka razy.
Czy to już było? Najpierw pytaj, potem wkładaj
int n;
cin >> n;
set<int> widziane;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (widziane.count(x)) cout << x << " ZNANY\n";
else cout << x << " NOWY\n";
widziane.insert(x);
}
To jeden z najważniejszych schematów tej lekcji. Zbiór widziane pamięta wszystko, co już przeczytaliśmy. Dla każdej nowej liczby:
1) pytamy, czy już ją widzieliśmy (count),
2) wypisujemy odpowiedź,
3) dopisujemy ją do widzianych (insert).
Kolejność kroków 1 i 3 jest kluczowa. Gdybyśmy najpierw wstawili, a potem zapytali, każda liczba byłaby „znana” — przecież przed chwilą ją wstawiliśmy.
| krok | x | widziane przed krokiem | count(x) | wypisz |
|---|---|---|---|---|
| 1 | 3 | { } | 0 | 3 NOWY |
| 2 | 7 | {3} | 0 | 7 NOWY |
| 3 | 3 | {3, 7} | 1 | 3 ZNANY |
| 4 | 1 | {3, 7} | 0 | 1 NOWY |
| 5 | 7 | {1, 3, 7} | 1 | 7 ZNANY |
| 6 | 7 | {1, 3, 7} | 1 | 7 ZNANY |
int n;
cin >> n;
set<int> widziane;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
widziane.insert(x); // ZA WCZEŚNIE!
if (widziane.count(x)) cout << x << " ZNANY\n";
else cout << x << " NOWY\n";
}
Ten program zawsze odpowiada „ZNANY”. Każda liczba jest wstawiana przed pytaniem, więc count zawsze ją znajduje. Program się kompiluje i działa — tylko liczy co innego, niż chcieliśmy. Takie błędy najtrudniej zauważyć, dlatego warto sprawdzać program na małym przykładzie z treści.
Pierwsza powtórka
int n;
cin >> n;
set<int> widziane;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (widziane.count(x)) {
cout << "powtorka: " << x << " na pozycji " << i << "\n";
return 0;
}
widziane.insert(x);
}
cout << "wszystkie rozne\n";
Szukamy pierwszej liczby, która pojawia się drugi raz. Czytamy po kolei i przy pierwszym trafieniu count od razu kończymy program: return 0; wewnątrz main to natychmiastowy koniec.
Uwaga na słowo „pierwsza”. Liczba 5 też się powtarza, i to wcześniej zaczyna (jest na pozycji 1). Ale jej drugie wystąpienie jest dopiero na pozycji 5, a drugie wystąpienie jedynki — na pozycji 4. Wygrywa ta powtórka, którą spotkamy wcześniej, czytając od lewej.
Jeśli pętla dojdzie do końca bez trafienia, wszystkie liczby były różne.
insert mówi, czy coś dodał
set<int> s;
cout << s.insert(5).second << "\n";
cout << s.insert(5).second << "\n";
cout << s.insert(7).second << "\n";
cout << s.size() << "\n";
Dla ciekawych: insert nie tylko wkłada, ale też odpowiada. Zwraca parę (znasz pary z lekcji Pair). Jej second to true, gdy element był nowy i został dodany, albo false, gdy już był. (first to strzałka na element — przyda się w części 4.)
Dzięki temu „nowy czy znany” można napisać jednym if, bez osobnego count:
else cout << "ZNANY\n";
Oba sposoby są poprawne. Na początek count + insert jest czytelniejsze.
erase — wyjmij x ze zbioru
set<int> s = {1, 2, 3, 4, 5};
s.erase(3);
s.erase(10); // 10 nie ma — nic się nie dzieje
for (int x : s) cout << x << " ";
cout << "\n";
int a = s.erase(1); // 1 był — usunięty
int b = s.erase(1); // już go nie ma
cout << a << " " << b << " " << s.size() << "\n";
s.erase(x) usuwa wartość x ze zbioru. Reszta elementów zostaje w tym samym porządku — „dziura” po trójce sama się zamyka.
Gdy x nie ma w zbiorze, erase nic nie robi — bez błędu, tak samo jak insert powtórki. Nie musisz sprawdzać count przed usunięciem.
erase zwraca też, ile elementów usunął: 1, gdy x był, i 0, gdy go nie było. Czasem to się przydaje, np. żeby policzyć udane usunięcia.
empty i clear
set<int> s = {3, 1};
cout << s.empty() << "\n";
s.clear();
cout << s.empty() << " " << s.size() << "\n";
s.empty() odpowiada na pytanie „czy zbiór jest pusty?”: 1 (prawda), gdy nic w nim nie ma, i 0 (fałsz), gdy coś jest. To to samo co s.size() == 0, tylko krócej.
s.clear() usuwa wszystkie elementy naraz. Po nim zbiór jest pusty, jak świeżo utworzony.
Kilka testów w jednym wejściu: nowy zbiór na każdy test
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
set<int> s; // nowy, pusty zbiór w każdym teście
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
}
int t;
cin >> t;
set<int> s; // jeden zbiór na wszystkie testy!
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
}
Gdy wejście zawiera kilka niezależnych testów, każdy test potrzebuje własnego, pustego zbioru. Lewy program tworzy zbiór wewnątrz pętli while — przy każdym obrocie powstaje nowy. Prawy ma jeden zbiór na zewnątrz i trzeci test widzi jeszcze liczby z drugiego: zamiast 2 wypisuje 6. Jeśli wolisz trzymać zbiór na zewnątrz, wywołaj s.clear(); na początku każdego testu.
Polecenia: wjazd, wyjazd, pytanie
int q;
cin >> q;
set<int> parking;
while (q--) {
string polecenie;
int nr;
cin >> polecenie >> nr;
if (polecenie == "WJAZD") parking.insert(nr);
else if (polecenie == "WYJAZD") parking.erase(nr);
else {
if (parking.count(nr)) cout << "TAK\n";
else cout << "NIE\n";
}
}
cout << "aut: " << parking.size() << "\n";
Zbiór jest idealny do pilnowania, kto teraz jest w środku: auta na parkingu, uczniowie w bibliotece, gracze w pokoju gry. Każde polecenie to jedno słowo i numer. WJAZD wkłada numer do zbioru, WYJAZD go wyjmuje, a CZY pyta o obecność.
Polecenie wczytujemy do string i porównujemy przez ==, jak w lekcji o napisach. Na końcu size() mówi, ile aut zostało. Gdyby numery rejestracyjne były napisami (np. „WA 12345”), wystarczy set<string> — wszystko inne zostaje takie samo.
Lista brakujących
int n, m;
cin >> n >> m;
set<int> mam;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
mam.insert(x);
}
for (int k = 1; k <= n; k++)
if (!mam.count(k)) cout << k << " ";
cout << "\n";
Kolekcja ma naklejki od 1 do n = 10, a my mamy m = 6 naklejek (z powtórkami). Których brakuje? Wrzucamy posiadane do zbioru, a potem przechodzimy wszystkie numery od 1 do n i wypisujemy te, o które count mówi 0.
To odwrócenie pytania: nie „co mam?”, tylko „czego nie mam?”. Odpowiedź wychodzi od razu rosnąco, bo pętla idzie po numerach od 1 w górę.
Jak szybko działa count?
W vectorze, żeby sprawdzić, czy jest w nim x, trzeba przejrzeć wszystkie elementy po kolei (find albo pętla) — w lekcji o złożoności nazwaliśmy to O(n). Zbiór jest zbudowany sprytniej: trzyma elementy jak w drzewie, gdzie każde pytanie odrzuca połowę tego, co zostało (zobaczysz to w części 8). Dlatego count, insert i erase kosztują O(log n) — dla stu tysięcy elementów to około 17 kroków.
| n liczb, dla każdej pytamy „czy już była?” | vector + przeglądanie | set + count |
|---|---|---|
| jedno pytanie | do n kroków | około log₂ n kroków |
| n = 1 000 | ok. 500 000 kroków | ok. 10 000 kroków |
| n = 100 000 | ok. 5 000 000 000 — za wolno | ok. 1 700 000 — błyskawicznie |
s.count(x) — 1, gdy x jest, 0, gdy nie ma (idealne do if). „Czy już było?”: najpierw count, potem insert. s.erase(x) — usuwa x; gdy go nie ma, nic się nie dzieje (zwraca 0). s.empty() — czy pusty, s.clear() — usuń wszystko. Przy kilku testach: nowy zbiór (albo clear) w każdym teście. Wszystkie te operacje są szybkie: O(log n).
Rozpisz zbiór na kartce po każdej linijce. Uważaj na kolejność count i insert.
set<int> s = {2, 4, 6};
cout << s.count(4) + s.count(5);
Pokaż odpowiedź
set<int> s = {1, 2, 3};
s.erase(2);
s.erase(2);
s.insert(2);
s.erase(3);
cout << s.size();
Pokaż odpowiedź
int n;
cin >> n;
set<int> w;
int ile = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!w.count(x)) ile++;
w.insert(x);
}
cout << ile;
5 4 4 2 4 2Pokaż odpowiedź
vector<int> v = {3, 1, 3, 3, 2, 1};
set<int> s;
int nowe = 0;
for (int x : v) nowe += s.insert(x).second;
cout << nowe;
Pokaż odpowiedź
set<int> s = {10, 20};
cout << s.erase(7) << s.erase(10) << s.size();
Pokaż odpowiedź
set<int> s = {5};
s.erase(5);
cout << s.empty() << " ";
s.insert(5);
s.insert(5);
cout << s.empty() << " " << s.size();
Pokaż odpowiedź
int n;
cin >> n;
set<int> w;
int powt = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
w.insert(x);
if (w.count(x)) powt++;
}
cout << powt;
4 9 9 9 9Pokaż odpowiedź
int t;
cin >> t;
set<int> s;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << " ";
}
2 2 7 7 2 7 8Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
begin, rbegin i iteratory — najmniejszy i największy
Zbiór nie ma indeksów, ale za to zawsze jest posortowany. To znaczy, że najmniejszy element stoi na samym początku, a największy — na samym końcu. Żeby je wyjąć, użyjemy strzałek, czyli iteratorów, które znasz z lekcji o vectorze: begin() wskazuje pierwszy element, end() — miejsce za ostatnim, a gwiazdka * mówi „daj to, na co wskazuje strzałka”.
Najmniejszy: *s.begin(), największy: *s.rbegin()
set<int> s = {15, 4, 23, 8, 16};
cout << *s.begin() << "\n"; // najmniejszy
cout << *s.rbegin() << "\n"; // największy
s.begin() to strzałka na pierwszy element zbioru. Zbiór jest posortowany rosnąco, więc pierwszy element to najmniejszy. Gwiazdka przed nią zamienia strzałkę na wartość: *s.begin() = 4.
s.rbegin() to strzałka „od tyłu” — znasz ją z lekcji o sortowaniu (r jak reverse, odwrotnie). Wskazuje ostatni element, czyli największy: *s.rbegin() = 23.
Bez gwiazdki program się nie skompiluje albo wypisze nie to, co trzeba: strzałka to nie liczba.
prev i next — o jeden w lewo, o jeden w prawo
set<int> s = {15, 4, 23, 8, 16};
auto ost = prev(s.end()); // ostatni element
cout << *ost << "\n";
auto drugi = next(s.begin()); // drugi element
cout << *drugi << "\n";
cout << *prev(ost) << "\n"; // przedostatni
next(it) daje strzałkę o jeden element dalej, a prev(it) — o jeden wcześniej. Sama strzałka it się przy tym nie zmienia.
Największy element można więc wyjąć też tak: *prev(s.end()) — „jeden przed miejscem za końcem”, czyli ostatni. To ten sam element co *s.rbegin(), ale strzałka jest „zwykła” — przyda się, gdy będziemy go usuwać.
Słowo auto poznałeś przy iteratorach vectora: prawdziwa nazwa typu strzałki to set<int>::iterator. Za długa — niech kompilator zgadnie.
Uwaga na pusty zbiór
set<int> s;
if (s.empty()) cout << "pusty - nie ma najmniejszego\n";
else cout << *s.begin() << "\n";
s.insert(7);
if (s.empty()) cout << "pusty - nie ma najmniejszego\n";
else cout << *s.begin() << "\n";
W pustym zbiorze begin() i end() to ta sama strzałka — wskazuje miejsce, w którym nic nie ma. *s.begin() na pustym zbiorze to błąd: program może wypisać przypadkową liczbę albo się wysypać. Kompilator Cię nie ostrzeże.
Dlatego zanim sięgniesz po najmniejszy albo największy element, zawsze sprawdź !s.empty(). Szczególnie wtedy, gdy elementy są usuwane — zbiór, który był pełny, w pewnej chwili może się opróżnić.
Strzałka idzie przez zbiór: it++
set<int> s = {30, 10, 20};
for (auto it = s.begin(); it != s.end(); it++)
cout << *it << " ";
cout << "\n";
for (int x : s) cout << x << " ";
cout << "\n";
Obie pętle robią to samo. Pierwsza pokazuje, co dzieje się „pod spodem” pętli for (int x : s): strzałka startuje na begin(), w każdym obrocie przesuwa się o jeden (it++) i kończy, gdy dojdzie do end().
Po co pisać dłużej? Bo strzałka wie, gdzie jesteśmy. Mając it, możemy zajrzeć do sąsiada: *prev(it) albo *next(it). Pętla for (int x : s) daje tylko wartość, bez sąsiadów.
Strzałki w zbiorze nie skaczą
set<int> s = {4, 8, 15};
auto it = s.begin() + 1; // BŁĄD: w zbiorze nie ma skoków
cout << *it << "\n";
W vectorze można było napisać v.begin() + 2 — strzałka skakała od razu o dwa miejsca. W zbiorze nie: strzałka umie iść tylko krok po kroku, it++ albo it--. Elementy zbioru nie leżą w pamięci obok siebie jak w vectorze, więc nie da się „przeskoczyć” policzonej liczby miejsc.
Zamiast + 1 pisz next(it), a zamiast + k — next(it, k). Ale uwaga: next(it, k) po cichu robi k kroków, więc kosztuje O(k), a nie jeden krok.
Od największego: rbegin i rend albo greater
set<int> s = {3, 9, 1, 7};
for (auto it = s.rbegin(); it != s.rend(); it++)
cout << *it << " ";
cout << "\n";
set<int, greater<int>> m = {3, 9, 1, 7};
for (int x : m) cout << x << " ";
cout << "\n";
cout << *m.begin() << "\n";
Dwa sposoby na przechodzenie od największego. Pierwszy: strzałki od tyłu — rbegin() wskazuje ostatni element, a rend() to miejsce „przed pierwszym”. it++ na takiej strzałce idzie w lewo.
Drugi: zbiór, który sam trzyma elementy malejąco. W nawiasach ostrych dopisujemy regułę greater<int> — tę samą, której używaliśmy w sort. Wtedy begin() wskazuje największy element, a pętla for idzie od góry.
Uwaga na >> w set<int, greater<int>>: dwa nawiasy ostre obok siebie są w porządku od C++11.
Wyjmowanie najmniejszego i największego
set<int> s = {5, 1, 9, 3, 7};
s.erase(s.begin()); // usuwa najmniejszy (1)
s.erase(prev(s.end())); // usuwa największy (9)
for (int x : s) cout << x << " ";
cout << "\n";
set<int> s = {40, 10, 30, 20};
while (!s.empty()) {
int x = *s.begin();
s.erase(s.begin());
cout << "biore " << x << ", zostalo " << s.size() << "\n";
}
erase przyjmuje nie tylko wartość, ale też strzałkę: s.erase(s.begin()) usuwa element, na który wskazuje begin(), czyli najmniejszy. Największy usuwamy przez s.erase(prev(s.end())). (Strzałki od tyłu, rbegin(), do erase nie pasują — stąd prev(end()).)
Drugi program to ważny schemat: bierz zawsze najmniejszy. Pętla działa, dopóki zbiór nie jest pusty; w każdym obrocie zapamiętuje najmniejszą wartość, usuwa ją i coś z nią robi. Najpierw zapamiętaj wartość (int x = *s.begin();), potem usuwaj — po erase strzałka wskazuje już nieistniejący element i nie wolno jej używać.
Sąsiedzi w zbiorze: różnice między kolejnymi
set<int> s = {3, 10, 4, 20, 12};
for (auto it = next(s.begin()); it != s.end(); it++)
cout << *prev(it) << "->" << *it << " roznica " << *it - *prev(it) << "\n";
Zbiór jest posortowany, więc sąsiedzi w zbiorze to najbliższe sobie liczby — tak jak sąsiedzi w posortowanym vectorze z lekcji o sortowaniu. Pętla startuje od drugiego elementu (next(s.begin())) i dla każdego zagląda do poprzedniego (*prev(it)).
Z takich różnic łatwo wyciągnąć najmniejszą albo największą przerwę między różnymi liczbami. Uwaga: pętla zakłada, że zbiór ma co najmniej jeden element — next(begin()) w pustym zbiorze to błąd. Gdy element jest jeden, next(begin()) to już end() i pętla po prostu się nie wykona.
k-ty najmniejszy: k − 1 kroków
set<int> s = {50, 20, 40, 10, 30, 20};
int k = 3;
auto it = s.begin();
for (int i = 1; i < k; i++) it++;
cout << *it << "\n";
cout << *next(s.begin(), k - 1) << "\n";
Trzeci najmniejszy różny element to ten, do którego dojdziemy z begin() po dwóch krokach. Dwa sposoby: pętla z it++ albo next(s.begin(), k - 1). Pierwszy element to krok zero — stąd k − 1.
Przed takim chodzeniem sprawdź, czy k <= s.size(). Inaczej strzałka wyjdzie za koniec zbioru. I pamiętaj, że to kosztuje k kroków — dla jednego pytania to nic, ale dla tysięcy pytań o duże k lepiej przepisać zbiór do vectora i używać w[k - 1].
Elementów zbioru nie zmienia się na miejscu
set<int> s = {1, 5, 9};
for (int &x : s) x = x * 10; // BŁĄD
set<int> s = {1, 5, 9};
s.erase(5);
s.insert(50); // „zmiana” 5 na 50 = usuń i wstaw
for (int x : s) cout << x << " ";
cout << "\n";
W vectorze pętla for (int &x : v) zmieniała elementy. W zbiorze to się nie skompiluje: elementy zbioru są stałe (const). Gdyby dało się zmienić 5 na 50 w miejscu, zbiór przestałby być posortowany — a całe jego działanie opiera się na tym, że zawsze jest.
Zmiana wartości w zbiorze to zawsze dwa kroki: usuń starą, wstaw nową. Zbiór sam postawi nową wartość na właściwym miejscu — 50 trafia na koniec.
*s.begin(). Największy: *s.rbegin() albo *prev(s.end()). Zawsze najpierw sprawdź !s.empty(). next(it) i prev(it) — sąsiedzi strzałki. W zbiorze strzałka chodzi tylko krokami (it++, it--), nie ma it + 2. Usuwanie skrajnych: s.erase(s.begin()), s.erase(prev(s.end())). Malejąco: set<int, greater<int>> albo rbegin()…rend(). Zmiana elementu = erase + insert.
Narysuj zbiór na kartce jako rząd kulek i zaznacz, gdzie wskazuje każda strzałka.
set<int> s = {5, 1, 9};
cout << *s.begin() + *s.rbegin();
Pokaż odpowiedź
set<int> s = {30, 10, 20};
cout << *next(s.begin());
Pokaż odpowiedź
set<int> s = {2, 8, 2, 8};
cout << *prev(s.end()) << " " << s.size();
Pokaż odpowiedź
set<int> s = {4, 1, 3, 2};
s.erase(s.begin());
s.erase(s.begin());
for (int x : s) cout << x << " ";
Pokaż odpowiedź
set<int, greater<int>> s = {1, 5, 3};
cout << *s.begin() << " " << *s.rbegin();
Pokaż odpowiedź
set<int> s = {7, 2, 9, 4};
int ile = 0;
for (auto it = s.rbegin(); it != s.rend() && ile < 2; it++) {
cout << *it << " ";
ile++;
}
Pokaż odpowiedź
set<int> s = {10, 20, 30, 40};
auto it = s.begin();
it++;
it++;
cout << *it << " " << *prev(it);
Pokaż odpowiedź
set<int> s = {8, 3, 5, 3, 1};
cout << *next(s.begin(), 2);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
find, lower_bound i upper_bound — szukanie w zbiorze
count odpowiada tylko „jest” albo „nie ma”. Często chcemy więcej: gdzie jest dana wartość, jaka jest najbliższa większa, jaka najbliższa mniejsza. W lekcji o sortowaniu takie pytania zadawaliśmy posortowanemu vectorowi przez lower_bound i upper_bound. Zbiór jest zawsze posortowany, więc ma te same polecenia — i działają one nawet wtedy, gdy elementy ciągle dochodzą i znikają.
find — strzałka na x albo end()
set<int> s = {3, 8, 15, 21, 30};
auto it = s.find(15);
if (it != s.end()) cout << "jest: " << *it << "\n";
if (s.find(16) == s.end()) cout << "16 nie ma\n";
s.erase(s.find(8)); // usuwanie przez strzałkę
for (int x : s) cout << x << " ";
cout << "\n";
s.find(x) szuka x i zwraca strzałkę na niego. Gdy x nie ma, zwraca s.end() — strzałkę „za końcem”, która znaczy „nie znaleziono”. Dlatego wynik find zawsze porównujemy z s.end().
Kiedy find, a kiedy count? Do pytania „czy jest?” wystarczy count. find przydaje się, gdy chcesz potem coś zrobić z tym miejscem: usunąć element strzałką, zajrzeć do jego sąsiadów prev i next.
Uwaga: s.erase(s.find(x)) jest bezpieczne tylko wtedy, gdy x na pewno jest. Gdy go nie ma, to erase(end()) — błąd, który potrafi wysypać program. Do usuwania wartości wystarczy zwykłe s.erase(x).
lower_bound i upper_bound — pierwszy ≥ x i pierwszy > x
set<int> s = {3, 8, 15, 21, 30};
cout << *s.lower_bound(10) << "\n"; // pierwszy >= 10
cout << *s.lower_bound(15) << "\n"; // pierwszy >= 15
cout << *s.upper_bound(15) << "\n"; // pierwszy > 15
if (s.lower_bound(31) == s.end()) cout << "nic >= 31\n";
s.lower_bound(x) zwraca strzałkę na pierwszy element większy lub równy x. Dla x = 10 to 15 — w zbiorze nie ma 10, więc dostajemy najbliższą większą. Dla x = 15 to samo 15, bo „lub równy”.
s.upper_bound(x) zwraca strzałkę na pierwszy element ściśle większy od x. Dla 15 to już 21 — sama piętnastka jest pomijana.
Gdy takiego elementu nie ma, obie zwracają s.end(). Gwiazdka na end() to błąd, więc przed wypisaniem zawsze sprawdź != s.end(). To dokładnie te same pojęcia co w lekcji o sortowaniu — tylko zapisane z kropką, jako polecenie zbioru.
Przesuwaj suwak i obserwuj, jak zmieniają się strzałki. Zwróć uwagę, co się dzieje, gdy x jest w zbiorze (lower i upper rozjeżdżają się o jeden element), a co, gdy go nie ma (wskazują to samo miejsce). Sprawdź też krańce: x mniejsze od wszystkich i większe od wszystkich.
lower_bound(v.begin(), v.end(), x). Na zbiorze też się skompiluje i da dobry wynik — ale będzie wolny. Strzałki zbioru nie umieją skakać (część 3), więc ta wersja przechodzi elementy po kolei: O(n) zamiast O(log n). W zbiorze zawsze pisz z kropką: s.lower_bound(x), s.upper_bound(x), s.find(x).
Ostatni ≤ x i ostatni < x — strzałka o jeden w lewo
set<int> s = {3, 8, 15, 21, 30};
int x;
cin >> x;
auto it = s.upper_bound(x); // pierwszy > x
if (it == s.begin()) cout << "nic <= x\n";
else cout << "ostatni <= x: " << *prev(it) << "\n";
auto jt = s.lower_bound(x); // pierwszy >= x
if (jt == s.begin()) cout << "nic < x\n";
else cout << "ostatni < x: " << *prev(jt) << "\n";
Zbiór nie ma osobnego polecenia „największy element ≤ x”. Ale łatwo go zbudować: weź upper_bound(x) — pierwszy element większy od x — i cofnij strzałkę o jeden. Element tuż przed nim jest ostatnim, który nie jest większy od x, czyli ostatnim ≤ x.
Tak samo z lower_bound(x): cofnięcie daje ostatni element mniejszy od x.
Pułapka: cofać wolno tylko wtedy, gdy strzałka nie stoi na begin(). Jeśli upper_bound(x) == s.begin(), to wszystkie elementy są większe od x i przed strzałką nic nie ma. Dla x = 2 tak właśnie jest.
| pytanie | strzałka | brak odpowiedzi, gdy |
|---|---|---|
| czy x jest? gdzie? | s.find(x) | == s.end() |
| pierwszy ≥ x | s.lower_bound(x) | == s.end() |
| pierwszy > x | s.upper_bound(x) | == s.end() |
| ostatni ≤ x | prev(s.upper_bound(x)) | s.upper_bound(x) == s.begin() |
| ostatni < x | prev(s.lower_bound(x)) | s.lower_bound(x) == s.begin() |
Najbliższa wartość: sprawdź sąsiada z prawej i z lewej
set<int> s = {3, 8, 15, 21, 30};
int x;
cin >> x;
auto it = s.lower_bound(x); // kandydat z prawej (>= x)
int odp;
if (it == s.end()) odp = *prev(it); // wszystkie < x
else if (it == s.begin()) odp = *it; // wszystkie >= x
else {
int prawy = *it, lewy = *prev(it);
if (x - lewy <= prawy - x) odp = lewy; // remis: mniejszy
else odp = prawy;
}
cout << odp << "\n";
Najbliższa x wartość w zbiorze jest albo pierwszą ≥ x, albo ostatnią < x — czyli jednym z dwóch sąsiadów miejsca, w którym x by stał. Nie trzeba przeglądać całego zbioru: wystarczy porównać tych dwóch kandydatów.
Dla x = 11 kandydaci to 15 (odległość 4) i 8 (odległość 3) — wygrywa 8. Dla x = 18 obaj, 15 i 21, są w odległości 3; przy remisie bierzemy mniejszy. Dla x = 100 nie ma kandydata z prawej (it == s.end()), więc odpowiedzią jest ostatni element.
Program zakłada, że zbiór nie jest pusty. Trzy przypadki — koniec, początek i środek — to stały element każdego programu z najbliższą wartością.
Zbiór, który rośnie: pytania przeplatane z dodawaniem
int q;
cin >> q;
set<int> dworce;
while (q--) {
string p;
int x;
cin >> p >> x;
if (p == "BUDUJ") dworce.insert(x);
else {
auto it = dworce.lower_bound(x);
if (it == dworce.end()) cout << "BRAK\n";
else cout << *it << "\n";
}
}
Wzdłuż prostej drogi budowane są dworce (pozycja x). Podróżny, który rusza z punktu x i jedzie w prawo, zatrzyma się na pierwszym dworcu o pozycji ≥ x. Polecenia budowy i pytania przychodzą na przemian.
Tu widać, po co zbiór, skoro mamy posortowany vector i lower_bound. Vector trzeba by sortować po każdym BUDUJ albo wstawiać w środek — a wstawienie w środek vectora przesuwa wszystkie dalsze elementy, czyli kosztuje O(n). Zbiór wstawia w O(log n) i od razu jest gotowy na następne pytanie.
Zasada: dane się nie zmieniają — wystarczy posortowany vector. Dane się zmieniają (dochodzą, znikają) i ciągle pytamy o najbliższe — zbiór.
Sąsiedzi nowego elementu: insert zwraca strzałkę
set<int> s = {10, 40};
auto it = s.insert(25).first; // strzałka na 25
cout << "lewy: " << *prev(it) << ", prawy: " << *next(it) << "\n";
auto jt = s.insert(5).first; // strzałka na 5
if (jt == s.begin()) cout << "5 jest najmniejsze\n";
cout << "prawy: " << *next(jt) << "\n";
W części 2 widzieliśmy, że insert zwraca parę, a jej second mówi, czy element był nowy. Teraz przyda się first: to strzałka na wstawiony element (albo na ten, który już był).
Mając strzałkę, od razu sięgamy do sąsiadów: prev(it) to największy element mniejszy od nowego, next(it) — najmniejszy większy. Jak zawsze pilnujemy brzegów: przed prev sprawdzamy it != s.begin(), a przed użyciem next(it) — czy nie jest równe s.end().
A ile elementów jest w przedziale?
Pytanie „ile elementów zbioru leży w przedziale [a, b]?” wydaje się podobne, ale zbiór nie odpowiada na nie szybko. Strzałki lower_bound(a) i upper_bound(b) znajdziesz od razu, tylko że policzenie elementów między nimi wymaga przejścia ich krok po kroku (strzałek w zbiorze nie da się odjąć jak w vectorze). Gdy dane się nie zmieniają, użyj posortowanego vectora i odejmowania z lekcji o sortowaniu: upper_bound(…, b) - lower_bound(…, a).
s.find(x) — strzałka na x albo s.end(). s.lower_bound(x) — pierwszy ≥ x, s.upper_bound(x) — pierwszy > x (obie: s.end(), gdy brak). Ostatni ≤ x: prev(s.upper_bound(x)), ostatni < x: prev(s.lower_bound(x)) — tylko gdy strzałka nie stoi na begin(). Najbliższa wartość: porównaj dwóch kandydatów. Zawsze z kropką: s.lower_bound(x), bo wersja z s.begin(), s.end() działa wolno.
Narysuj zbiór jako rząd kulek z pustym miejscem end() na końcu i zaznacz strzałki.
set<int> s = {2, 4, 9, 12};
cout << *s.lower_bound(9) << " " << *s.lower_bound(5);
Pokaż odpowiedź
set<int> s = {2, 4, 9, 12};
cout << *s.upper_bound(9) << " " << *s.upper_bound(1);
Pokaż odpowiedź
set<int> s = {2, 4, 9, 12};
cout << (s.lower_bound(13) == s.end());
Pokaż odpowiedź
set<int> s = {2, 4, 9, 12};
cout << *prev(s.lower_bound(9)) << " " << *prev(s.upper_bound(9));
Pokaż odpowiedź
set<int> s = {1, 5, 9};
if (s.find(7) != s.end()) cout << "jest";
else cout << "brak";
Pokaż odpowiedź
set<int> s = {1, 3, 5, 7, 9};
int ile = 0;
for (auto it = s.lower_bound(4); it != s.end(); it++) ile++;
cout << ile;
Pokaż odpowiedź
set<int> s = {1, 4, 9};
int x;
cin >> x;
auto it = s.lower_bound(x);
int prawy = *it, lewy = *prev(it);
if (x - lewy <= prawy - x) cout << lewy;
else cout << prawy;
6Pokaż odpowiedź
set<int> s = {10, 20, 30};
auto it = s.insert(15).first;
cout << *prev(it) << " " << *next(it);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Działania na zbiorach — suma, część wspólna, różnica
Zbiory znasz też z matematyki. Tam na dwóch zbiorach A i B wykonuje się działania: łączy się je, szuka wspólnych elementów, odejmuje. Zadania programistyczne pełne są takich pytań: które gry mają oboje?, kto był na obu wycieczkach?, czego brakuje w drugiej liście?. Ze zbiorami w C++ każde z tych działań to jedna krótka pętla.
Na rysunku poniżej A = {1, 2, 3, 5, 8} i B = {2, 3, 4, 8, 9}. Środek, gdzie koła na siebie zachodzą, to elementy obu zbiorów naraz. Kliknij każde działanie i zobacz, które obszary trafiają do wyniku.
| działanie | znak | co zawiera | dla A i B z rysunku |
|---|---|---|---|
| suma | A ∪ B | to, co jest w A lub w B | {1, 2, 3, 4, 5, 8, 9} |
| część wspólna (iloczyn) | A ∩ B | to, co jest w A i w B | {2, 3, 8} |
| różnica | A \ B | to, co jest w A, ale nie w B | {1, 5} |
| różnica | B \ A | to, co jest w B, ale nie w A | {4, 9} |
| różnica symetryczna | A △ B | to, co jest dokładnie w jednym | {1, 4, 5, 9} |
Część wspólna: przejdź A, pytaj B
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> C;
for (int x : A)
if (B.count(x)) C.insert(x);
for (int x : C) cout << x << " ";
cout << "\n";
Pomysł: weź po kolei każdy element A i zapytaj zbiór B, czy też go ma. Jeśli tak — element jest wspólny. Wynik zbieramy do nowego zbioru C.
Ponieważ przechodzimy A rosnąco, elementy wspólne też wychodzą rosnąco. Moglibyśmy je od razu wypisywać, bez zbioru C — ale C przyda się, gdy z wynikiem trzeba coś dalej robić.
Ile to kosztuje? Dla każdego z |A| elementów jedno count w B, czyli O(|A| · log |B|). Opłaca się przechodzić mniejszy zbiór, a pytać większy.
Suma: wrzuć wszystko do jednego worka
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> S = A; // kopia zbioru A
for (int x : B) S.insert(x);
for (int x : S) cout << x << " ";
cout << "\n";
cout << S.size() << " = " << A.size() << " + " << B.size() << " - 3\n";
Suma to najprostsze działanie: zaczynamy od kopii A (set<int> S = A; kopiuje cały zbiór, tak jak przy vectorze) i dorzucamy wszystko z B. Elementy wspólne zbiór przyjmie tylko raz — o powtórki nie musimy dbać.
Zauważ wzór z drugiego wiersza. Gdy dodajemy rozmiary A i B, elementy wspólne liczymy dwa razy, więc trzeba je raz odjąć: |A ∪ B| = |A| + |B| − |A ∩ B|. To ta sama zasada włączania i wyłączania, której używałeś w lekcji o złożoności przy liczbach podzielnych przez 3 lub 5.
Różnica: tylko w jednym, nie w drugim
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
for (int x : A)
if (!B.count(x)) cout << x << " ";
cout << "\n";
for (int x : B)
if (!A.count(x)) cout << x << " ";
cout << "\n";
Różnica A \ B to elementy A, których B nie ma. Ta sama pętla co przy części wspólnej, tylko z wykrzyknikiem w warunku.
W odróżnieniu od sumy i części wspólnej kolejność ma znaczenie: A \ B to {1, 5}, a B \ A to {4, 9}. „Czego Ala nie dała Oli” to co innego niż „czego Ola nie dała Ali”. Zawsze czytaj w treści, który zbiór jest „pierwszy”.
Różnica symetryczna: dokładnie w jednym
set<int> A = {1, 2, 3, 5, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> W;
for (int x : A) if (!B.count(x)) W.insert(x);
for (int x : B) if (!A.count(x)) W.insert(x);
for (int x : W) cout << x << " ";
cout << "\n" << W.size() << "\n";
Różnica symetryczna to obie różnice razem: elementy, które ma tylko jeden z dwóch zbiorów. Na rysunku to dwa „księżyce” bez środka. Zbieramy je do zbioru W, który sam ułoży je rosnąco.
Można też policzyć jej rozmiar bez budowania: |A △ B| = |A| + |B| − 2 · |A ∩ B|. Tym razem część wspólną odejmujemy dwa razy, bo jej w ogóle nie chcemy.
Podzbiór, równość, rozłączność
set<int> A = {2, 8};
set<int> B = {2, 3, 4, 8, 9};
set<int> C = {1, 5};
bool podzbior = true;
for (int x : A)
if (!B.count(x)) podzbior = false;
bool rozlaczne = true;
for (int x : C)
if (B.count(x)) rozlaczne = false;
cout << podzbior << " " << rozlaczne << " " << (A == B) << "\n";
set<int> D = {8, 2, 8};
cout << (A == D) << "\n";
A jest podzbiorem B (A ⊆ B), gdy każdy element A jest też w B. Zakładamy, że tak jest, i szukamy kontrprzykładu: jeden element A, którego B nie ma, wystarczy, żeby odpowiedź brzmiała „nie”. Ten sam schemat „zakładam prawdę, szukam wyjątku” znasz z lekcji o pętlach.
Zbiory rozłączne nie mają ani jednego wspólnego elementu — część wspólna jest pusta.
Równość sprawdza operator ==: dwa zbiory są równe, gdy mają dokładnie te same elementy. Kolejność wstawiania ani powtórki nie mają znaczenia — {2, 8} i zbiór zbudowany z 8, 2, 8 są równe.
Dwa zbiory z wejścia
int n, m;
cin >> n >> m;
set<int> A, B;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
A.insert(x);
}
for (int i = 0; i < m; i++) {
int x;
cin >> x;
B.insert(x);
}
int wspolne = 0;
for (int x : A)
if (B.count(x)) wspolne++;
int suma = A.size() + B.size() - wspolne;
cout << wspolne << " " << suma << "\n";
Typowe wejście zadania: dwie liczby n i m, potem n liczb pierwszej listy i m liczb drugiej. Listy mogą mieć powtórki — zbiory je usuną. Tu A = {1, 2, 3, 4}, B = {3, 4, 5}.
Program liczy, ile jest wartości wspólnych (3 i 4), a rozmiar sumy wylicza wzorem, bez budowania trzeciego zbioru: 4 + 3 − 2 = 5.
Dwa zbiory tworzymy w jednej linijce: set<int> A, B; — tak samo jak dwie zmienne int.
Wspólne litery dwóch słów
string a, b;
cin >> a >> b;
set<char> A(a.begin(), a.end());
set<char> B(b.begin(), b.end());
for (char c : A)
if (B.count(c)) cout << c;
cout << "\n";
Działania na zbiorach działają tak samo dla liter. Zbiór liter słowa „programowanie” to {a, e, g, i, m, n, o, p, r, w}, a słowa „olimpiada” — {a, d, i, l, m, o, p}. Wspólne litery to a, i, m, o, p.
Zbiór liter tworzymy jedną linijką z całego napisu — begin() i end() napisu, jak w części 1.
Część wspólna wielu zbiorów
int n;
cin >> n;
set<int> wspolne;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
set<int> teraz;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
teraz.insert(x);
}
if (i == 0) wspolne = teraz;
else {
set<int> nowe;
for (int x : wspolne)
if (teraz.count(x)) nowe.insert(x);
wspolne = nowe;
}
}
for (int x : wspolne) cout << x << " ";
cout << "\n";
Co mają wspólnego wszystkie z n list? Część wspólną buduje się krok po kroku. Po pierwszej liście „wspólne” to cała pierwsza lista. Każda kolejna lista może tylko zmniejszyć ten zbiór: zostawiamy z niego tylko te elementy, które ma też nowa lista.
Po liście 1: {1, 2, 3, 4}. Po liście 2: {2, 4} — 1 i 3 odpadają. Po liście 3: dalej {2, 4}.
Przypisanie wspolne = nowe; kopiuje cały zbiór, a nowy zbiór teraz powstaje w każdym obrocie pętli od zera.
if (B.count(x)). Różnica A \ B: if (!B.count(x)) — kolejność zbiorów ma znaczenie. Suma: kopia A (set<int> S = A;) i insert wszystkiego z B. Różnica symetryczna: obie różnice razem. Podzbiór: zakładaj „tak”, szukaj elementu A, którego B nie ma. Równość: A == B. Wzór: |A ∪ B| = |A| + |B| − |A ∩ B|.
Narysuj sobie dwa koła i wpisz liczby w obszary — wtedy każde działanie widać od razu.
set<int> A = {1, 2, 3}, B = {2, 3, 4};
int ile = 0;
for (int x : A) if (B.count(x)) ile++;
cout << ile;
Pokaż odpowiedź
set<int> A = {1, 2}, B = {2, 3, 4};
set<int> S = A;
for (int x : B) S.insert(x);
cout << S.size();
Pokaż odpowiedź
set<int> A = {5, 6, 7}, B = {6, 10};
for (int x : A) if (!B.count(x)) cout << x << " ";
Pokaż odpowiedź
set<int> A = {1, 2, 3}, B = {3, 4};
set<int> W;
for (int x : A) if (!B.count(x)) W.insert(x);
for (int x : B) if (!A.count(x)) W.insert(x);
for (int x : W) cout << x << " ";
Pokaż odpowiedź
set<int> A;
set<int> B = {1, 2};
bool podzbior = true;
for (int x : A) if (!B.count(x)) podzbior = false;
cout << podzbior;
Pokaż odpowiedź
set<int> A = {3, 1, 2};
set<int> B = {1, 2, 3, 3};
cout << (A == B);
Pokaż odpowiedź
set<int> A, B;
for (int i = 1; i <= 5; i++) A.insert(i);
for (int i = 3; i <= 9; i++) B.insert(i);
int w = 0;
for (int x : A) if (B.count(x)) w++;
cout << A.size() + B.size() - w;
Pokaż odpowiedź
string a = "kot", b = "pies";
set<char> A(a.begin(), a.end()), B(b.begin(), b.end());
int w = 0;
for (char c : A) if (B.count(c)) w++;
cout << w;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Zbiór par i napisów
Zbiór umie trzymać wszystko, co da się porównać. Pary porównują się same — najpierw first, a przy remisie second (lekcja Pair). Dlatego set<pair<int, int>> działa od razu: trzyma różne pary, ułożone tak, jak ułożyłby je sort. To otwiera mnóstwo zadań: różne punkty na planszy, odwiedzone pola, znajomości, rankingi.
Różne punkty: set<pair<int, int>>
set<pair<int, int>> punkty;
punkty.insert({2, 5});
punkty.insert({1, 7});
punkty.insert({2, 3});
punkty.insert({1, 7}); // ten sam punkt — odpada
cout << punkty.size() << "\n";
for (auto p : punkty)
cout << "(" << p.first << ", " << p.second << ") ";
cout << "\n";
Parę wstawiamy w klamrach: punkty.insert({2, 5}); — tak samo jak tworzyliśmy pary w lekcji Pair. Dwa punkty są tym samym punktem, gdy mają oba pola równe — dlatego drugie (1, 7) odpadło, a (2, 3) i (2, 5) zostały jako różne.
Kolejność: najpierw według first (1 przed 2), a przy remisie według second (3 przed 5). Zbiór par to więc „posortowana lista różnych par” — bez wywoływania sort i unique.
W pętli używamy auto p, bo pełna nazwa typu to pair<int, int>.
count i rozpakowywanie
set<pair<int, int>> pola = {{0, 0}, {0, 1}, {1, 1}};
cout << pola.count({0, 1}) << pola.count({1, 0}) << "\n";
for (auto [x, y] : pola) cout << x << "," << y << " ";
cout << "\n";
count, insert, erase, find przyjmują całą parę. Uwaga na kolejność w parze: (0, 1) to inne pole niż (1, 0). Pierwsze jest w zbiorze, drugiego nie ma.
Zapis for (auto [x, y] : pola) rozpakowuje każdą parę na dwie zmienne o wygodnych nazwach — znasz go z lekcji Pair. Zamiast p.first i p.second piszesz po prostu x i y.
Para bez kolejności: najpierw mniejszy
int m;
cin >> m;
set<pair<int, int>> mecze;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
mecze.insert({min(a, b), max(a, b)});
}
cout << mecze.size() << "\n";
for (auto [a, b] : mecze) cout << a << "-" << b << " ";
cout << "\n";
Drużyny 1 i 2 grały mecz. Zapis „1 2” i „2 1” oznacza ten sam mecz — tu kolejność w parze nie ma znaczenia. Ale dla zbioru (1, 2) i (2, 1) to różne pary!
Rozwiązanie: zanim wstawisz parę, ustaw ją w jednej, ustalonej kolejności — mniejszy pierwszy: {min(a, b), max(a, b)}. Wtedy „2 1” zamienia się w (1, 2) i trafia na tę samą parę co „1 2”. Ten sam pomysł działa przy znajomościach, drogach między miastami i krawędziach figur.
Robot i odwiedzone pola
string ruchy;
cin >> ruchy;
int x = 0, y = 0;
set<pair<int, int>> odwiedzone;
odwiedzone.insert({x, y});
for (char c : ruchy) {
if (c == 'G') y++;
else if (c == 'D') y--;
else if (c == 'L') x--;
else if (c == 'P') x++;
odwiedzone.insert({x, y});
}
cout << odwiedzone.size() << "\n";
Robot zaczyna w punkcie (0, 0) i wykonuje ruchy: G (góra), D (dół), L (lewo), P (prawo). Na ilu różnych polach stanął? Każde pole, na które wejdzie, wrzucamy do zbioru par — powtórki odpadną same.
Trasa: (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) → (1, 0) → (0, 0). Siedem postojów, ale ostatni to powrót na start — różnych pól jest 6.
Pamiętaj o polu startowym: wstawiamy je przed pętlą. Bez tego wynik byłby za mały o jeden, gdyby robot na start już nie wrócił.
Ranking: para (−punkty, numer)
vector<int> pkt(4, 0); // pkt[1..3]
set<pair<int, int>> ranking; // (-punkty, numer)
for (int i = 1; i <= 3; i++) ranking.insert({0, i});
// gracz 2 dostaje 5 punktów
ranking.erase({-pkt[2], 2});
pkt[2] += 5;
ranking.insert({-pkt[2], 2});
// gracz 3 dostaje 5 punktów
ranking.erase({-pkt[3], 3});
pkt[3] += 5;
ranking.insert({-pkt[3], 3});
auto [minusPkt, lider] = *ranking.begin();
cout << "lider: " << lider << " (" << -minusPkt << " pkt)\n";
for (auto [m, nr] : ranking) cout << nr << ":" << -m << " ";
cout << "\n";
Chcemy w każdej chwili znać lidera: najwięcej punktów, a przy remisie — mniejszy numer. Zbiór par zrobi to sam, jeśli dobrze ułożymy parę: (−punkty, numer). Zbiór sortuje rosnąco, więc minus odwraca kolejność punktów (więcej punktów = mniejsza liczba = wcześniej), a przy remisie wygrywa mniejszy numer. To „sztuczka z minusem” z lekcji o sortowaniu i parach.
Lider to zawsze *ranking.begin().
Najważniejsze: elementu zbioru nie da się zmienić na miejscu (część 3). Zmiana punktów to usuń starą parę, wstaw nową. Żeby usunąć starą, trzeba znać stare punkty — dlatego trzymamy je osobno w vectorze pkt.
lower_bound na parach: pierwszy w wierszu
set<pair<int, int>> kamienie = {{1, 5}, {1, 9}, {2, 3}, {4, 4}};
// pierwszy kamień w wierszu 1, w kolumnie >= 6
auto it = kamienie.lower_bound({1, 6});
if (it != kamienie.end() && it->first == 1) cout << it->second << "\n";
else cout << "BRAK\n";
// pierwszy kamień w wierszu 3, w dowolnej kolumnie
auto jt = kamienie.lower_bound({3, INT_MIN});
if (jt != kamienie.end() && jt->first == 3) cout << jt->second << "\n";
else cout << "BRAK\n";
Kamienie leżą na planszy w polach (wiersz, kolumna). Pytanie: idąc wierszem 1 w prawo od kolumny 6, na który kamień trafię? lower_bound({1, 6}) szuka pierwszej pary ≥ (1, 6) — w kolejności par to właśnie pierwszy kamień w wierszu 1 o kolumnie ≥ 6, czyli (1, 9).
Pułapka: jeśli w wierszu nie ma już kamieni, lower_bound przeskoczy do następnego wiersza. Dla wiersza 3 zwraca (4, 4) — kamień z innego wiersza. Dlatego zawsze sprawdzamy, czy first się zgadza.
it->first to skrót od (*it).first — „pole first elementu, na który wskazuje strzałka”. A INT_MIN (najmniejszy int, z lekcji Max / Min) jako drugie pole daje pierwszą parę w wierszu, niezależnie od kolumny.
Zbiór słów: wielkie i małe litery
int n;
cin >> n;
set<string> slowa;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
for (char &c : w) c = tolower(c);
slowa.insert(w);
}
cout << slowa.size() << "\n";
for (string w : slowa) cout << w << " ";
cout << "\n";
Dla zbioru „Kot”, „kot” i „KOT” to trzy różne napisy. Często jednak chcemy je traktować jak jedno słowo. Wtedy przed wstawieniem zamieniamy słowo na małe litery: pętla z referencją char &c zmienia każdą literę przez tolower (lekcja String).
Ogólna zasada, którą widzieliśmy już przy meczach: zanim wstawisz, sprowadź do jednej postaci. Wszystko, co ma się liczyć jako „to samo”, musi w zbiorze wyglądać identycznie.
Klucz zamiast słowa: anagramy
int n;
cin >> n;
set<string> klucze;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
sort(w.begin(), w.end()); // klucz: litery po kolei
klucze.insert(w);
}
cout << klucze.size() << "\n";
for (string k : klucze) cout << k << " ";
cout << "\n";
Anagramy to słowa z tych samych liter: „kot”, „tok”, „okt”. Ile jest różnych grup anagramów? Każde słowo zamieniamy na klucz: jego litery posortowane. Wszystkie anagramy mają ten sam klucz („kot” → „kot”, „tok” → „kot”), a słowa z innych liter — inny.
Zbiór kluczy ma tyle elementów, ile jest grup. To kolejny przykład „sprowadzania do jednej postaci” — tylko postać jest sprytniejsza niż małe litery.
set<pair<int, int>> trzyma różne pary, ułożone według first, a przy remisie second. Wstawianie i pytanie: s.insert({a, b}), s.count({a, b}). Para bez kolejności: {min(a, b), max(a, b)}. Ranking: para (-punkty, numer), zmiana = erase starej + insert nowej. lower_bound({w, k}) na parach — sprawdź, czy it->first to wciąż ten sam wiersz. Zanim wstawisz, sprowadź do jednej postaci (małe litery, posortowany klucz).
Pary porównuj jak w lekcji Pair: najpierw pierwsze pole, przy remisie drugie.
set<pair<int, int>> s = {{2, 1}, {1, 2}, {1, 1}};
for (auto [a, b] : s) cout << a << b << " ";
Pokaż odpowiedź
set<pair<int, int>> s;
s.insert({1, 2});
s.insert({2, 1});
s.insert({1, 2});
cout << s.size();
Pokaż odpowiedź
set<pair<int, int>> s = {{3, 4}};
cout << s.count({3, 4}) << s.count({4, 3});
Pokaż odpowiedź
set<pair<int, int>> s;
int a = 3, b = 1;
s.insert({min(a, b), max(a, b)});
s.insert({min(b, a), max(b, a)});
s.insert({1, 3});
cout << s.size();
Pokaż odpowiedź
set<pair<int, int>> r = {{-5, 2}, {-7, 1}, {-7, 3}};
cout << r.begin()->second;
Pokaż odpowiedź
set<pair<int, int>> s = {{1, 5}, {2, 3}, {2, 8}};
auto it = s.lower_bound({1, 6});
cout << it->first << " " << it->second;
Pokaż odpowiedź
set<string> s;
vector<string> w = {"Ala", "ALA", "ala", "As"};
for (string x : w) {
for (char &c : x) c = tolower(c);
s.insert(x);
}
cout << s.size();
Pokaż odpowiedź
set<string> k;
vector<string> w = {"abc", "cab", "bca", "abd"};
for (string x : w) {
sort(x.begin(), x.end());
k.insert(x);
}
cout << k.size();
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
multiset — gdy powtórzenia się liczą
Zwykły zbiór gubi informację, ile razy coś wystąpiło. Czasem to dokładnie to, czego chcemy („ile różnych?”), ale czasem przeszkadza: na półce mogą leżeć dwa produkty za 10 zł, w klasie może być trzech uczniów o wzroście 150 cm. Wtedy używamy multiset — zbioru, który trzyma powtórzenia, a poza tym działa prawie tak samo jak set: wszystko jest zawsze posortowane i szybkie.
Pierwszy multiset
multiset<int> m;
m.insert(5);
m.insert(2);
m.insert(5);
m.insert(8);
m.insert(2);
m.insert(5);
cout << m.size() << " " << m.count(5) << " " << m.count(7) << "\n";
for (int x : m) cout << x << " ";
cout << "\n";
multiset<int> m; tworzy pusty multizbiór. Mieszka w tym samym nagłówku <set>.
Każdy insert naprawdę coś dodaje — także powtórkę. Dlatego size() to 6, czyli wszystkie wstawione liczby, a nie liczba różnych.
count(x) wreszcie robi to, co sugeruje nazwa: mówi, ile kopii x jest w środku. Piątek jest 3.
Przechodzenie pętlą daje wszystkie elementy rosnąco, z powtórzeniami obok siebie. Multiset to więc „vector, który sam się sortuje przy każdym wstawieniu”.
Ta sama ramka co w części 1, tym razem w trybie multiset. Wrzuć kilka razy tę samą liczbę, a potem porównaj erase(x) z erase(find(x)) — to najważniejsza różnica w tej części.
Pułapka: erase(x) usuwa wszystkie kopie
multiset<int> m = {1, 3, 3, 3, 7};
m.erase(3);
for (int x : m) cout << x << " ";
cout << "\n";
multiset<int> m = {1, 3, 3, 3, 7};
auto it = m.find(3);
if (it != m.end()) m.erase(it); // usuwa JEDNĄ trójkę
for (int x : m) cout << x << " ";
cout << "\n";
To najczęstszy błąd z multisetem. m.erase(3) usuwa wszystkie trójki naraz — wszystkie elementy równe 3. Jeśli sprzedajesz jeden produkt za 3 zł, a na półce były trzy takie, nagle znikają wszystkie.
Żeby usunąć jedną kopię, trzeba wskazać ją strzałką: m.find(3) zwraca strzałkę na jedną z trójek, a m.erase(it) usuwa dokładnie ten jeden element.
Pamiętaj o sprawdzeniu it != m.end(): gdy wartości nie ma, find zwraca end(), a erase(end()) to błąd.
m.erase(x) usuwa wszystkie elementy równe x. Jedną kopię usuwa m.erase(m.find(x)) — po sprawdzeniu, że m.find(x) != m.end(). Tak samo działa m.erase(m.begin()): strzałka wskazuje jeden element, więc znika jedna najmniejsza wartość, nawet jeśli było ich kilka.
Najmniejszy i największy z powtórzeniami
multiset<int> ceny = {30, 10, 20, 10};
cout << *ceny.begin() << " " << *ceny.rbegin() << "\n";
ceny.erase(ceny.begin()); // sprzedajemy JEDEN najtańszy
cout << *ceny.begin() << " " << ceny.size() << "\n";
ceny.erase(ceny.begin());
cout << *ceny.begin() << " " << ceny.size() << "\n";
Wszystko z części 3 działa bez zmian: *begin() to najmniejszy element, *rbegin() — największy, erase(begin()) usuwa jeden najmniejszy.
Na półce leżą dwa produkty za 10 zł. Po sprzedaży jednego najtańszym produktem dalej jest 10 zł — bo była druga dziesiątka. Dopiero po drugiej sprzedaży najtańszy kosztuje 20. W zwykłym set druga dziesiątka by zginęła już przy wstawianiu i wynik byłby zły.
Sortowanie multisetem i count, który bywa wolny
multiset<int> m;
int x;
while (cin >> x) m.insert(x);
for (int y : m) cout << y << " ";
cout << "\n";
multiset<int> m;
for (int i = 0; i < 5; i++) m.insert(7);
cout << m.count(7) << " " << (m.find(7) != m.end()) << "\n";
Wrzucenie wszystkich liczb do multisetu i przejście go pętlą daje to samo co sort — z powtórzeniami. Też O(n log n). Gdy wszystkie dane masz od razu, sort na vectorze jest prostszy i szybszy. Multiset wygrywa, gdy liczby dochodzą i znikają, a po drodze ciągle trzeba znać najmniejszą czy największą.
Uwaga na count w multisecie: żeby policzyć kopie, musi przejść je wszystkie. Gdy x występuje 100 000 razy, jedno count(x) robi 100 000 kroków. Jeśli pytasz tylko „czy jest?”, użyj m.find(x) != m.end() — to zawsze O(log n).
Największy w każdym oknie
int n, k;
cin >> n >> k;
vector<int> t(n);
for (int &x : t) cin >> x;
multiset<int> okno;
for (int i = 0; i < n; i++) {
okno.insert(t[i]); // wchodzi nowy
if (i >= k) okno.erase(okno.find(t[i - k])); // wychodzi stary
if (i >= k - 1) cout << *okno.rbegin() << " ";
}
cout << "\n";
Okno to k kolejnych elementów tablicy (znasz je z lekcji o vectorze i o złożoności). Okno przesuwa się o jeden: z prawej wchodzi nowy element, z lewej wychodzi ten sprzed k kroków. W każdym położeniu chcemy znać największy element okna.
Multiset trzyma dokładnie elementy bieżącego okna. Wejście to insert, wyjście to usunięcie jednej kopii, a największy to *rbegin(). Każdy krok kosztuje O(log k), całość O(n log k) — zamiast O(n · k), gdybyśmy za każdym razem przeglądali całe okno.
int n, k;
cin >> n >> k;
vector<int> t(n);
for (int &x : t) cin >> x;
multiset<int> okno;
for (int i = 0; i < n; i++) {
okno.insert(t[i]);
if (i >= k) okno.erase(t[i - k]); // usuwa WSZYSTKIE kopie!
if (i >= k - 1) cout << *okno.rbegin() << " ";
}
cout << "\n";
Ten sam program z jedną zmianą: okno.erase(t[i - k]) zamiast okno.erase(okno.find(t[i - k])). Dopóki w oknie nie ma powtórzeń, oba działają tak samo. Ale gdy z okna [3, 7, 2] ma wyjść siódemka sprzed trzech kroków, erase(7) usuwa obie siódemki — także tę, która wciąż jest w oknie. Od tej chwili wyniki są złe.
Na małym teście bez powtórek tego błędu nie zobaczysz. Dlatego przy multisecie zawsze zadawaj sobie pytanie: usuwam jedną kopię czy wszystkie?
Weź największy, który się mieści
multiset<int> bilety = {50, 30, 80, 30};
vector<int> klienci = {60, 20, 30, 100};
for (int budzet : klienci) {
auto it = bilety.upper_bound(budzet); // pierwszy > budżet
if (it == bilety.begin()) cout << "-1\n";
else {
it--; // ostatni <= budżet
cout << *it << "\n";
bilety.erase(it); // ten bilet sprzedany
}
}
Kasa ma bilety w różnych cenach (ceny mogą się powtarzać). Każdy klient kupuje najdroższy bilet, na który go stać — czyli największy ≤ jego budżet. Sprzedany bilet znika.
To połączenie wszystkiego, co znamy: upper_bound(budżet) to pierwszy bilet za drogi, cofnięcie strzałki daje ostatni, który się mieści (część 4), a erase(it) usuwa dokładnie ten jeden bilet.
Bilety: {30, 30, 50, 80}. Klient z 60 kupuje 50. Klient z 20 nie kupi nic — upper_bound(20) to już pierwszy bilet. Klient z 30 kupuje jedną z trzydziestek. Klient ze 100 kupuje 80.
Dwa największe naraz: gra w kamienie
multiset<int> k = {2, 7, 4, 1, 8, 1};
while (k.size() >= 2) {
int a = *k.rbegin();
k.erase(prev(k.end()));
int b = *k.rbegin();
k.erase(prev(k.end()));
if (a != b) k.insert(a - b);
}
if (k.empty()) cout << 0 << "\n";
else cout << *k.begin() << "\n";
W każdej rundzie bierzemy dwa najcięższe kamienie i zderzamy je. Jeśli ważą tyle samo — oba znikają. Jeśli nie — zostaje kamień o wadze równej różnicy. Jaki kamień zostanie na końcu?
{1, 1, 2, 4, 7, 8}: zderzamy 8 i 7, zostaje 1 → {1, 1, 1, 2, 4}. Potem 4 i 2 → 2. Potem 2 i 1 → 1. Potem 1 i 1 — znikają oba. Zostaje {1}.
Multiset jest tu konieczny: kamienie o tej samej wadze to różne kamienie. Każde wyjęcie to erase(prev(end())) — strzałka na jeden, największy element.
multiset<int> trzyma powtórzenia, zawsze rosnąco. size() — wszystkie elementy, count(x) — liczba kopii (dla wielu kopii wolne; „czy jest?” sprawdzaj przez find). erase(x) usuwa wszystkie kopie, erase(find(x)) i erase(it) — jedną. Najmniejszy *begin(), największy *rbegin(), lower_bound i upper_bound — jak w set. Multiset wybieraj, gdy elementy dochodzą i znikają, a powtórzenia są różnymi rzeczami.
Zapisuj multiset jako rosnący rząd liczb — z powtórzeniami — i skreślaj tyle kopii, ile naprawdę znika.
multiset<int> m = {4, 4, 1, 4};
cout << m.size() << " " << m.count(4);
Pokaż odpowiedź
multiset<int> m = {2, 2, 2, 5};
m.erase(2);
cout << m.size();
Pokaż odpowiedź
multiset<int> m = {2, 2, 2, 5};
m.erase(m.find(2));
cout << m.size() << " " << m.count(2);
Pokaż odpowiedź
multiset<int> m = {9, 3, 3, 6};
m.erase(m.begin());
cout << *m.begin();
Pokaż odpowiedź
vector<int> v = {3, 1, 3, 2, 1};
multiset<int> m(v.begin(), v.end());
for (int x : m) cout << x;
Pokaż odpowiedź
multiset<int> m = {1, 3, 3, 5};
cout << *m.lower_bound(3) << " " << *m.upper_bound(3);
Pokaż odpowiedź
multiset<int, greater<int>> m = {3, 5, 1, 5};
for (int x : m) cout << x << " ";
Pokaż odpowiedź
multiset<int> m;
for (int i = 1; i <= 9; i++) m.insert(i % 2);
m.erase(m.find(1));
cout << m.count(0) << " " << m.count(1);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
unordered_set i szybkość — który zbiór wybrać?
Przez całą lekcję powtarzaliśmy, że operacje na zbiorze są szybkie: O(log n). Czas zobaczyć, skąd ta szybkość się bierze, poznać jeszcze szybszego kuzyna — unordered_set — i nauczyć się wybierać właściwą strukturę do zadania. W ćwiczeniach z tej części dane są duże: pomysł „pętla w pętli” nie zdąży, a zbiór — tak.
Jak set szuka tak szybko? Drzewo
W środku set trzyma elementy w drzewie poszukiwań. Na górze stoi jeden element. Na lewo od niego są tylko mniejsze, na prawo — tylko większe. I tak samo w każdym miejscu drzewa. Żeby sprawdzić, czy x jest w zbiorze, zaczynamy od góry: jeśli x jest mniejszy — schodzimy w lewo, jeśli większy — w prawo. Każdy krok w dół odrzuca połowę tego, co zostało — dokładnie jak zgadywanie liczby z lekcji o złożoności.
Wybierz liczbę i przejdź szukanie krok po kroku. Spróbuj też liczb, których w zbiorze nie ma — zobaczysz, gdzie zatrzyma się szukanie i gdzie insert dołożyłby nowy element.
Drzewo z 15 elementów ma 4 poziomy, więc każde szukanie kończy się po najwyżej 4 porównaniach. Zbiór dba o to, żeby drzewo było zawsze wyważone — po każdym insert i erase sam je poprawia. Dzięki temu poziomów jest około log₂ n: dla tysiąca elementów 10, dla miliona 20, dla miliarda 30. Stąd O(log n) dla insert, count, erase, find, lower_bound i upper_bound.
Ile kosztuje każda operacja?
| operacja | vector | posortowany vector | set | unordered_set |
|---|---|---|---|---|
| dodaj x | O(1) — push_back | O(n) — wstaw w środek | O(log n) | O(1) średnio |
| czy x jest? | O(n) | O(log n) | O(log n) | O(1) średnio |
| usuń x | O(n) | O(n) | O(log n) | O(1) średnio |
| najmniejszy, największy | O(n) | O(1) | O(1) | O(n) |
| pierwszy ≥ x | O(n) | O(log n) | O(log n) | brak |
| przechodzenie | kolejność dodawania | rosnąco | rosnąco | dowolna kolejność |
unordered_set — bez kolejności, za to szybciej
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> u;
u.insert(5);
u.insert(2);
u.insert(8);
u.insert(5);
cout << u.size() << " " << u.count(2) << " " << u.count(7) << "\n";
u.erase(2);
cout << u.size() << "\n";
return 0;
}
unordered_set<int> u = {9, 4, 15, 20, 6};
for (int x : u) cout << x << " ";
cout << "\n";
unordered_set (nagłówek <unordered_set>) ma te same podstawowe polecenia: insert, count, erase, size, empty, clear, find. Też nie trzyma powtórzeń.
Różnica: nie trzyma kolejności. Przechodzenie pętlą daje elementy w kolejności, która zależy od wnętrza struktury — może być inna na innym komputerze i zmieniać się po dodaniu elementów. Nie ma też lower_bound ani „najmniejszego na początku”.
W zamian insert, count i erase działają średnio w O(1). Liczba trafia do „kubełka” wybranego przez obliczenie z jej wartości (coś jak reszta z dzielenia przez liczbę kubełków), a count zagląda tylko do jednego kubełka. Zobacz to w ramce poniżej.
Ramka to uproszczony model: ma 7 kubełków i wybiera kubełek resztą z dzielenia przez 7. Prawdziwy unordered_set sam dobiera liczbę kubełków (i zmienia ją, gdy elementów przybywa), dlatego program wyżej wypisał te same liczby w innej kolejności. Ważne jest jedno: ta kolejność nie jest rosnąca i nie wolno na niej polegać.
„Średnio” jest ważne: gdy wiele liczb trafi do jednego kubełka, count musi przejrzeć je wszystkie. Na zwykłych danych zdarza się to rzadko, ale autorzy zadań olimpijskich potrafią przygotować dane, które celowo zapychają jeden kubełek. Dlatego set z gwarantowanym O(log n) jest bezpieczniejszym wyborem, a unordered_set — szybszym, gdy liczy się każda milisekunda i kolejność jest niepotrzebna.
Gdy liczby są małe: zwykła tablica
int n;
cin >> n;
vector<bool> byla(1000001, false);
int rozne = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!byla[x]) {
byla[x] = true;
rozne++;
}
}
cout << rozne << "\n";
Gdy wszystkie wartości są małymi liczbami nieujemnymi — powiedzmy od 0 do miliona — zbiór można zastąpić tablicą: byla[x] mówi, czy x już się pojawił. To tablica zliczeń z lekcji o tablicach. Sprawdzenie i zaznaczenie to jeden krok, O(1) — szybciej niż jakikolwiek zbiór.
Ale tablica ma granice: nie zmieści wartości do 10¹⁸, nie przyjmie liczb ujemnych ani napisów, a tablica na miliard pól nie zmieści się w pamięci. Zbiór działa z dowolnymi wartościami — płaci za to logarytmem.
Który wybrać?
| w zadaniu potrzebujesz… | wybierz |
|---|---|
| tylko „czy było?” i „ile różnych?”, wartości małe (do ok. 10⁷) | tablica bool / zliczeń |
| tylko „czy było?” i „ile różnych?”, wartości dowolne | set albo unordered_set |
kolejności, najmniejszego, największego, najbliższego (lower_bound) | set |
| tego samego, ale powtórzenia to różne rzeczy | multiset |
| wszystkie dane od razu, potem tylko pytania | posortowany vector (sort, lower_bound) |
| kolejności z wejścia, indeksów, „który był trzeci?” | vector |
Ten sam problem: pętla w pętli kontra zbiór
int n;
long long k;
cin >> n >> k;
vector<long long> t(n);
for (long long &x : t) cin >> x;
bool jest = false;
for (int i = 0; i < n; i++) // O(n²)
for (int j = i + 1; j < n; j++)
if (t[i] + t[j] == k) jest = true;
cout << (jest ? "TAK" : "NIE") << "\n";
int n;
long long k;
cin >> n >> k;
set<long long> widziane;
bool jest = false;
for (int i = 0; i < n; i++) { // O(n log n)
long long x;
cin >> x;
if (widziane.count(k - x)) jest = true;
widziane.insert(x);
}
cout << (jest ? "TAK" : "NIE") << "\n";
Czy jakieś dwie liczby z listy dają w sumie k? Lewy program sprawdza każdą parę — dla n = 200 000 to 20 miliardów par, kilka minut liczenia. Prawy czyta liczby po kolei i dla każdej pyta: czy widziałem już jej „dopełnienie” k − x? Dla x = 7 dopełnieniem jest 3, a trójkę widzieliśmy wcześniej. Jedno count na liczbę — razem O(n log n), ułamek sekundy.
Kolejność „najpierw pytaj, potem wstaw” znów jest ważna: gwarantuje, że parę tworzą dwie różne pozycje. Dla k = 10 i listy z jedną piątką odpowiedź brzmi NIE — sama piątka nie może być parą sama ze sobą.
Dwa wskaźniki ze zbiorem: najdłuższy fragment bez powtórzeń
int n;
cin >> n;
vector<int> t(n);
for (int &x : t) cin >> x;
set<int> okno;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
while (okno.count(t[r])) { // t[r] już jest — zwijamy z lewej
okno.erase(t[l]);
l++;
}
okno.insert(t[r]);
best = max(best, r - l + 1);
}
cout << best << "\n";
Szukamy najdłuższego fragmentu (kawałka bez przerw), w którym wszystkie liczby są różne. Okno [l, r] trzyma zbiór swoich elementów. Prawy koniec idzie po kolei. Gdy nowa liczba t[r] już jest w oknie, przesuwamy lewy koniec i wyrzucamy elementy, aż powtórka zniknie.
Pętla while w środku for wygląda groźnie, ale — jak w dwóch wskaźnikach z lekcji o złożoności — lewy koniec tylko rośnie, więc łącznie wykona najwyżej n kroków. Całość: O(n log n).
Tu wynik 5 daje fragment 2, 3, 1, 4, 5 (albo 1, 4, 5, 3, 2).
Zbiór sum prefiksowych: fragment o sumie 0
int n;
cin >> n;
set<long long> sumy = {0}; // suma pustego początku
long long s = 0;
bool jest = false;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
s += x;
if (sumy.count(s)) jest = true;
sumy.insert(s);
}
cout << (jest ? "TAK" : "NIE") << "\n";
Czy jest fragment o sumie dokładnie 0? Pomysł z sum prefiksowych: suma fragmentu od l do r to P[r] − P[l − 1]. Równa się zero wtedy, gdy dwie sumy prefiksowe są równe. Zbieramy więc kolejne sumy prefiksowe do zbioru i pytamy, czy nowa już była.
Sumy dla pierwszego wejścia: 0, 3, 2, 6, 3 — trójka powtórzyła się, więc fragment między nimi (−1, 4, −3) sumuje się do zera. Zero na starcie oznacza pusty początek — dzięki niemu złapiemy też fragment zaczynający się od pierwszej liczby.
Wielkie dane z generatora
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
unordered_set<long long> u;
long long x = s;
for (long long i = 0; i < n; i++) {
u.insert(x);
x = (x * a + b) % m;
}
cout << u.size() << "\n";
W kilku ćwiczeniach z tej części liczby nie są podane wprost — za dużo by ich było. Zamiast tego dostajesz pięć liczb n, s, a, b, m i generator z lekcji o złożoności: x₁ = s, a każda następna to xᵢ = (xᵢ₋₁ · a + b) mod m. Licz w long long — iloczyn może sięgać 10¹⁸.
Dla wejścia z przykładu: 1, 5, 6, 1, 5, 6, … — ciąg się zapętla i różne są tylko trzy liczby. Zbiór sam to wyłapał.
lower_bound(s.begin(), s.end(), x) na zbiorze — O(n), pisz s.lower_bound(x). count(x) w multisecie z wieloma kopiami — O(liczba kopii), do „czy jest?” użyj find. next(it, k) — k kroków. Kopia zbioru (set<int> t = s;) albo wypisanie całego zbioru w każdym obrocie pętli — O(n) za każdym razem, czyli O(n²) razem.
set to wyważone drzewo poszukiwań: insert, count, erase, find, lower_bound — O(log n). unordered_set — bez kolejności i bez lower_bound, za to średnio O(1). Małe wartości — tablica bool. „Czy jest para o sumie k?” — pytaj o k - x przed wstawieniem x. Fragment bez powtórzeń — okno ze zbiorem. Fragment o sumie 0 — powtórzona suma prefiksowa.
Licz w głowie albo na kartce — tak jak w lekcji o złożoności.
int n = 1000000, kroki = 0;
while (n > 1) {
n /= 2;
kroki++;
}
cout << kroki;
Pokaż odpowiedź
unordered_set<int> u = {3, 3, 1, 2, 1};
cout << u.size() << u.count(3) << u.count(4);
Pokaż odpowiedź
int n;
cin >> n;
vector<bool> byla(10, false);
int ile = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!byla[x]) { byla[x] = true; ile++; }
}
cout << ile;
5 2 7 2 7 9Pokaż odpowiedź
int n, k;
cin >> n >> k;
set<int> w;
bool jest = false;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (w.count(k - x)) jest = true;
w.insert(x);
}
cout << (jest ? "TAK" : "NIE");
4 12 6 2 5 7Pokaż odpowiedź
int n;
cin >> n;
set<long long> sumy = {0};
long long s = 0;
bool jest = false;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
s += x;
if (sumy.count(s)) jest = true;
sumy.insert(s);
}
cout << (jest ? "TAK" : "NIE");
4 2 -2 5 1Pokaż odpowiedź
int n;
cin >> n;
vector<int> t(n);
for (int &x : t) cin >> x;
set<int> okno;
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
while (okno.count(t[r])) { okno.erase(t[l]); l++; }
okno.insert(t[r]);
best = max(best, r - l + 1);
}
cout << best;
6 5 5 5 5 5 5Pokaż odpowiedź
set<int> s;
for (int i = 0; i < 1000; i++) s.insert(i % 10);
cout << s.size();
Pokaż odpowiedź
long long n, s, a, b, m;
cin >> n >> s >> a >> b >> m;
set<long long> u;
long long x = s;
for (int i = 0; i < n; i++) {
u.insert(x);
x = (x * a + b) % m;
}
cout << u.size();
6 0 1 2 6Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: zbiory w praktyce
Znasz już cały zestaw: insert, size i przechodzenie zbioru, count i erase z pytaniem „czy to już było?”, najmniejszy i największy z begin i rbegin, iteratory, find, lower_bound i upper_bound z najbliższą wartością, działania na zbiorach, zbiory par i napisów, multiset z oknami i zachłannymi wyborami, a na koniec unordered_set i wybór właściwej struktury. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka, potem zadania średnie, a na końcu trudne — z wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — jeśli coś brzmi obco, wróć do odpowiedniej części, mapa lekcji jest na górze strony. A tu masz najważniejsze schematy w jednym miejscu:
Ściąga: gotowe schematy
Podstawy
set<int> s; s.insert(x); // powtórka: nic s.size(); // ile różnych for (int x : s) // rosnąco s.count(x); // 1 albo 0 s.erase(x); // brak: nic s.empty(); s.clear();
Zbiór nie ma indeksów: zamiast s[i] — pętla albo kopia do vectora.
Czy to już było?
set<int> widziane;
for (…) {
cin >> x;
if (widziane.count(x)) …
widziane.insert(x);
}
Najpierw pytaj, potem wstaw. Przy kilku testach — nowy zbiór w każdym.
Skrajne i strzałki
*s.begin() // najmniejszy *s.rbegin() // największy s.erase(s.begin()); s.erase(prev(s.end())); next(it), prev(it)
Zawsze najpierw !s.empty(). Zmiana elementu = erase + insert.
Szukanie
s.find(x) // albo end() s.lower_bound(x) // pierwszy >= x s.upper_bound(x) // pierwszy > x prev(s.upper_bound(x)) // ost. <= x prev(s.lower_bound(x)) // ost. < x
Przed prev sprawdź != begin(), przed gwiazdką — != end().
Działania
A ∩ B: x z A, B.count(x) A \ B: x z A, !B.count(x) A ∪ B: S = A; S.insert(B…) |A∪B| = |A| + |B| - |A∩B| A == B // te same elementy
Przechodź mniejszy zbiór, pytaj większy.
Pary i klucze
set<pair<int,int>> p;
p.insert({min(a,b), max(a,b)});
ranking: {-punkty, numer}
p.lower_bound({w, INT_MIN})
sort(w.begin(), w.end()); // klucz
Zanim wstawisz, sprowadź do jednej postaci.
multiset
multiset<int> m; m.erase(m.find(x)); // JEDNA kopia m.erase(x); // WSZYSTKIE okno: insert(t[i]), erase(find(t[i-k])), *m.rbegin()
„Czy jest?” w multisecie — przez find, nie count.
Który wybrać?
małe wartości → bool[]
czy było, ile różnych → set /
unordered_set
kolejność, najbliższy → set
powtórzenia → multiset
dane się nie zmieniają →
sort + lower_bound
Każda operacja na zbiorze: O(log n).
begin() przed prev, end() przed gwiazdką. 5) Duże liczby i sumy — long long. 6) Sprawdź program na przykładzie z treści, a potem pomyśl o największym teście.
Rozgrzewka · zadania 1–10
Rozgrzewka ze zbiorem: lotto, słowa użyte tylko raz, różne kawałki napisu, liczby o różnych cyfrach, spotkanie ciągów Collatza, reszty z potęg, pomalowany płot, najbardziej różnorodne słowo, szyfr z kluczem i sprawdzanie sudoku.
Średnie · zadania 11–20
Wspólni znajomi (vector zbiorów), ciąg Recamána, odważniki na jednej i na dwóch szalkach, izba przyjęć, fragment podzielny przez k, rezerwacje sali, najdłuższy ciąg kolejnych liczb, pierwsza niepowtórzona litera i k-ta dozwolona liczba.
Trudne · zadania 21–28
Najmniejsza wolna liczba na żywo, drzewa w alei, łączenie odcinków, przydział pokoi, sala egzaminacyjna, bliskie wartości w pobliżu, najdłuższy rosnący podciąg w O(n log n) — a na koniec wielki finał: giełda.