Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 6 odcinków 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 i Pair. Najbardziej przydadzą się tablice — vector działa prawie tak samo, tylko wygodniej — oraz napisy, bo napis to w środku nic innego jak vector znaków. Z lekcji o parach przyda się porównywanie par, rozpakowywanie auto [a, b] i polecenie sort.
Po co nam coś nowego? Przypomnij sobie, jak w lekcji o tablicach wczytywałeś n liczb. Pisałeś int t[1005]; — z zapasem, bo nie wiadomo było, ile liczb przyjdzie. A co, jeśli zadanie nie poda n i liczby przychodzą aż do końca danych? Albo jeśli chcesz zebrać do osobnej tablicy tylko liczby parzyste — ile ich będzie? Tablica każe zgadywać z góry. Vector nie każe: rośnie sam, dokładnie tak, jak rósł napis, gdy dopisywałeś do niego litery.
Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw narysuj sobie vector na kartce — rząd pudełek z numerami pod spodem — i odpowiedz w głowie, a dopiero potem sprawdzaj. Po każdej części rób ćwiczenia w sprawdzarce. Ta lekcja jest długa: rób przerwy między częściami i nie przechodź dalej, dopóki ćwiczenia z poprzedniej części nie przestaną sprawiać Ci kłopotu.
Pierwszy vector, rośnie i maleje
Tworzenie, [ ] i size(), a potem push_back, pop_back, back() i wczytywanie do końca danych.
For-each i iteratory
Pętla „dla każdego” z & i bez, vector jako całość, begin() i end(), erase, insert, sort, reverse.
Vector 2D i podtablice
Tabele i grupy, a potem podtablica, prefiks i sufiks — z sumami prefiksowymi i oknem.
Podzbiory, permutacje, palindromy
Wszystkie wybory „bierzemy albo nie”, wszystkie ustawienia, ciągi czytane tak samo w obie strony i dwa wskaźniki.
cout << v[i] << " " jest w porządku. Uważaj natomiast na spacje w środku wiersza i na to, czy każdy element ma być w osobnym wierszu, czy wszystkie w jednym.
Mapa lekcji
Vector: tablica, która zna swoją długość
Zacznijmy od problemu, który vector rozwiązuje. Oto znany Ci z lekcji o tablicach program, który wczytuje n liczb i wypisuje je od końca. Obok — ten sam program z vectorem. Porównaj je linijka po linijce.
int n;
cin >> n;
int t[1005]; // zapas — zgadujemy, że n ≤ 1000
for (int i = 0; i < n; i++) {
cin >> t[i];
}
for (int i = n - 1; i >= 0; i--) {
cout << t[i] << " ";
}
cout << "\n";
int n;
cin >> n;
vector<int> v(n); // dokładnie n pudełek
for (int i = 0; i < v.size(); i++) {
cin >> v[i];
}
for (int i = v.size() - 1; i >= 0; i--) {
cout << v[i] << " ";
}
cout << "\n";
Programy robią to samo, ale po prawej nie musisz niczego zgadywać. vector<int> v(n); tworzy dokładnie n pudełek na liczby — ani jednego za mało, ani za dużo. A v.size() zawsze mówi, ile pudełek ma vector. Tablica tego nie umie: t ma 1005 pudełek, a to, że zajętych jest tylko n, musisz pamiętać sam, w osobnej zmiennej.
Trzy kłopoty zwykłej tablicy
| tablica (lekcja 7) | vector (dzisiaj) | |
|---|---|---|
| rozmiar | stały, ustalony na początku — trzeba zgadywać z zapasem | dokładnie taki, jak trzeba; może rosnąć i maleć |
| ile elementów? | trzeba pamiętać osobno w zmiennej n | mówi sam: v.size() |
| dopisanie na koniec | nie da się | v.push_back(5); (część 2) |
| odczyt i zmiana | t[2], t[2] = 7; | tak samo: v[2], v[2] = 7; |
| indeksy | od 0 do n − 1 | tak samo: od 0 do v.size() - 1 |
wypisanie jednym cout | nie | też nie — pętlą |
Najważniejsza wiadomość: wszystko, co umiesz robić z tablicą, robisz z vectorem tak samo. Nawiasy kwadratowe, indeksy od zera, pętle po indeksach, liczniki, maksimum — nic się nie zmienia. Vector dokłada tylko nowe możliwości.
Szablon programu z vectorem
#include <iostream>
#include <vector> // tu mieszka vector
using namespace std;
int main() {
vector<int> v = {5, 7, -1, 5};
cout << v.size() << "\n";
cout << v[0] << " " << v[3] << "\n";
return 0;
}
Vector mieszka w bibliotece <vector> — dopisujesz ją na górze, obok <iostream>. Jeśli używasz <bits/stdc++.h>, vector już w niej jest.
Na kolejnych przykładach pokazujemy zwykle tylko środek main. Reszta programu jest zawsze taka sama jak tutaj.
Budowa linijki, która tworzy vector
Rozłóżmy linijkę vector<int> v; na kawałki. Słowo vector mówi: „to będzie rząd pudełek”. W nawiasach ostrych piszesz, co leży w pudełkach — tutaj int, czyli liczby całkowite. Dokładnie tak jak przy parze: pair<int, int> albo vector<int> to razem nazwa typu. Potem nazwa zmiennej — wymyślasz ją sam — i średnik.
Taki vector, bez niczego więcej, jest pusty: ma zero pudełek. To nie błąd — w części 2 zobaczysz, że często właśnie od pustego vectora się zaczyna i dokłada elementy po kolei. Są cztery sposoby, żeby vector od razu coś zawierał:
vector<int> a; // pusty: 0 elementów
vector<int> b = {4, 8, 15}; // dokładnie te elementy
vector<int> c(5, 7); // 5 razy liczba 7
vector<int> d(3); // 3 zera
cout << a.size() << " " << b.size() << " ";
cout << c.size() << " " << d.size() << "\n";
cout << b[1] << " " << c[4] << " " << d[2] << "\n";
| zapis | co robi | size() |
|---|---|---|
vector<int> a; | pusty vector | 0 |
= {4, 8, 15} | dokładnie te elementy, po kolei | 3 |
(5, 7) | ile razy, co: pięć siódemek | 5 |
(3) | ile razy — same zera | 3 |
vector<int> a(5, 0); to pięć zer: nawiasy okrągłe znaczą „ile, co”. vector<int> b = {5, 0}; to dwa elementy: 5 i 0, bo klamry wypisują dokładne wartości. Te linijki wyglądają prawie tak samo, a dają vectory o rozmiarach 5 i 2. Zawsze czytaj nawias, zanim przepiszesz linijkę.
vector<int> a(5, 0);
vector<int> b = {5, 0};
cout << a.size() << " " << b.size() << "\n";
cout << b[0] << " " << b[1] << "\n";
Nowy vector ma zera, nie śmieci
Pamiętasz z lekcji o tablicach, że tablica utworzona wewnątrz main jest pełna śmieci, dopóki czegoś do niej nie wpiszesz? Vector tego problemu nie ma. Pudełka utworzone przez vector<int> d(3); zawsze dostają zera — w main czy poza nim. A pusty vector nie ma w ogóle pudełek, więc nie ma w nich czego „śmiecić”.
Druga dobra wiadomość: vector możesz spokojnie tworzyć w środku main, nawet na milion liczb. Duże tablice trzeba było wynosić przed main, bo inaczej program się wysypywał. Vector trzyma swoje pudełka w innej części pamięci, w której miejsca jest dużo, więc ten kłopot znika.
Indeksowanie: v[i] jak w tablicy
W parku stoi rząd 12 ławek. Na niektórych ktoś siedzi — C, L, B i K — a kropka oznacza pustą ławkę. Każda ławka ma swój numer od 0 do 11. Zapiszmy ten park jako vector znaków: vector<char>. Do ławki dostajesz się tak samo jak do pudełka tablicy: nazwa, a za nią numer w nawiasach kwadratowych.
vector<char> lawki = {'C', '.', 'L', '.', '.', '.', 'B', '.', '.', 'K', '.', '.'};
cout << lawki[0] << " " << lawki[6] << "\n";
if (lawki[9] == 'K') {
cout << "na lawce 9 siedzi K\n";
}
lawki[4] = 'Z'; // ktoś siada na ławce 4
lawki[0] = '.'; // a C odchodzi
for (int i = 0; i < lawki.size(); i++) {
cout << lawki[i];
}
cout << "\n";
lawki[9] to znak z ławki numer 9, czyli K. Porównujesz go ze znakiem 'K' zwykłym ==.
lawki[4] = 'Z'; wpisuje nowy znak do ławki 4. Pozostałe ławki się nie zmieniają.
Pętla wypisuje wszystkie ławki po kolei, bez spacji — powstaje coś, co wygląda jak napis. To nie przypadek: napis to w środku też rząd znaków z numerami.
size() i ostatni element
v.size() to metoda vectora — polecenie, które piszesz po kropce, z nawiasami na końcu. Znasz to z napisów: s.length() i s.size(). Vector o rozmiarze 5 ma pudełka od 0 do 4, więc ostatnie pudełko ma numer v.size() - 1.
vector<int> v = {1, 2, 5, 3, -5};
cout << v.size() << "\n";
cout << v[v.size() - 1] << "\n"; // ostatni
cout << v[v.size() / 2] << "\n"; // środkowy
v[v.size() - 1] = 100;
cout << v[4] << "\n";
v[5] to pamięć za vectorem — program wypisze śmieci, coś popsuje albo się wysypie. Kompilator Cię nie ostrzeże. Ostatni element to zawsze v[v.size() - 1].
Wczytywanie n liczb
Najczęstszy początek zadania: w pierwszym wierszu n, w drugim n liczb. Z vectorem wygląda to tak: wczytujesz n, tworzysz vector z n zerami, a pętla nadpisuje każde zero wczytaną liczbą. Kolejność jest ważna — najpierw cin >> n, dopiero potem vector<int> v(n);. Gdybyś stworzył vector przed wczytaniem n, miałby rozmiar z jakiejś przypadkowej wartości n.
int n;
cin >> n;
vector<int> v(n); // n zer
for (int i = 0; i < n; i++) {
cin >> v[i]; // zero → wczytana liczba
}
int suma = 0;
for (int i = 0; i < n; i++) {
suma += v[i];
}
cout << "suma " << suma << ", pierwsza " << v[0] << ", ostatnia " << v[n - 1] << "\n";
Wypisywanie: zawsze pętlą
Vectora nie da się wypisać jednym cout — tak samo jak pary. Każdy element wypisujesz osobno, w pętli. W warunku pętli możesz pisać i < n, jeśli n to liczba elementów, albo i < v.size() — wtedy nie musisz pamiętać n.
vector<int> v = {1, 2, 5};
cout << v << "\n"; // BŁĄD: cout nie umie wypisać vectora
vector<int> v = {1, 2, 5};
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << "\n";
for (int i = 0; i < v.size(); i++) {
cout << i << ": " << v[i] << "\n";
}
Vector dowolnego typu
W nawiasach ostrych możesz wpisać każdy typ, który znasz: vector<char>, vector<string>, vector<double>, vector<long long>, a nawet vector<pair<int, int>> — vector par. Wszystko inne zostaje takie samo: indeksy, size(), pętle.
vector<string> slowa = {"ala", "ma", "kota"};
vector<double> ceny(3, 2.5);
vector<char> znaki(4, '*');
vector<pair<int, int>> pkt = {{0, 0}, {1, 5}};
cout << slowa[2] << " " << slowa.size() << "\n";
cout << ceny[0] + ceny[1] << "\n";
cout << znaki[3] << znaki[0] << "\n";
cout << pkt[1].first << " " << pkt[1].second << "\n";
Vector napisów wczytujesz tak samo jak vector liczb: vector<string> s(n); i w pętli cin >> s[i]; — każde słowo trafia do jednego pudełka. A slowa[2][0] to pierwsza litera trzeciego słowa: najpierw wybierasz słowo, potem literę w nim.
Prześledźmy program z vectorem
Ostatni przykład tej części łączy wszystko: tworzenie, wczytywanie, indeksy i size(). Prześledź tabelkę: fioletowa liczba to pudełko, które właśnie się zmieniło.
vector<int> v(4, 1); // {1, 1, 1, 1}
for (int i = 1; i < v.size(); i++) {
v[i] = v[i - 1] * 3; // każdy 3 razy większy od poprzedniego
}
v[0] = v[3] - v[2];
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << "\n";
| po linijce | v[0] | v[1] | v[2] | v[3] |
|---|---|---|---|---|
v(4, 1) | 1 | 1 | 1 | 1 |
i = 1 | 1 | 3 | 1 | 1 |
i = 2 | 1 | 3 | 9 | 1 |
i = 3 | 1 | 3 | 9 | 27 |
v[0] = v[3] - v[2] | 18 | 3 | 9 | 27 |
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v(3, 4);
cout << v.size() << v[2];
Pokaż odpowiedź
vector<int> v = {3, 4};
cout << v.size() << " " << v[0];
Pokaż odpowiedź
vector<int> v(4);
v[1] = 6;
cout << v[0] + v[1] + v[3];
Pokaż odpowiedź
vector<int> v(4) to cztery zera. Zmieniamy tylko v[1], więc suma to 0 + 6 + 0 = 6.vector<int> v = {9, 8, 7, 6, 5};
cout << v[v.size() - 1] << v[v.size() - 2];
Pokaż odpowiedź
v[4] to 5, a v[3] to 6.vector<string> s = {"kot", "pies", "mysz"};
cout << s[1][0] << s[2].size() << s.size();
Pokaż odpowiedź
s[1][0] to pierwsza litera słowa „pies”, s[2].size() to długość słowa „mysz” (4), a s.size() to liczba słów (3).vector<int> v = {2, 4, 6, 8};
for (int i = 0; i < v.size(); i += 2) {
cout << v[i];
}
Pokaż odpowiedź
i < 4): v[0] = 2, v[2] = 6.vector<char> z(3, 'a');
z[1] = 'b';
for (int i = 0; i < z.size(); i++) {
cout << z[i];
}
Pokaż odpowiedź
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << v[n - 1] - v[0];
3 10 20 30Pokaż 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ę.
push_back, pop_back i back: dokładamy i zabieramy
Do tej pory vector miał od początku tyle pudełek, ile trzeba. Teraz najważniejsza nowość: vector potrafi rosnąć w trakcie programu. Dzięki temu nie musisz wiedzieć z góry, ile elementów będzie — dokładasz je po jednym, a vector sam się wydłuża.
push_back — dołóż na koniec
v.push_back(x); dokłada nowe pudełko z wartością x na sam koniec vectora — z prawej strony. Vector wydłuża się o 1, a stare elementy zostają na swoich miejscach. Nazwa pochodzi z angielskiego: push to „wepchnij”, back to „z tyłu”.
vector<int> v; // pusty
v.push_back(5);
v.push_back(7);
v.push_back(-1);
v.push_back(5);
cout << v.size() << "\n";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << "\n";
| linijka | v po tej linijce | size() |
|---|---|---|
vector<int> v; | { } | 0 |
v.push_back(5); | {5} | 1 |
v.push_back(7); | {5, 7} | 2 |
v.push_back(-1); | {5, 7, -1} | 3 |
v.push_back(5); | {5, 7, -1, 5} | 4 |
push_back w pętli
Prawdziwa siła push_back widać w pętli. Zaczynasz od pustego vectora i w każdym obrocie dokładasz jeden element. Na przykład kwadraty liczb od 1 do 5:
vector<int> kw;
for (int i = 1; i <= 5; i++) {
kw.push_back(i * i);
}
for (int i = 0; i < kw.size(); i++) {
cout << kw[i] << " ";
}
cout << "\n";
int n;
cin >> n;
vector<int> v; // pusty
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x); // wczytaj do x, dołóż na koniec
}
cout << v.size() << " " << v[0] << "\n";
Po prawej masz drugi sposób wczytywania n liczb: pusty vector i push_back. Daje ten sam wynik co vector<int> v(n); z pętlą cin >> v[i] z części 1. Możesz używać obu — ale nie mieszaj ich! Gdybyś napisał vector<int> v(n);, a potem robił push_back, vector miałby 2n elementów: najpierw n zer, a za nimi wczytane liczby.
vector<int> v; v[0] = 5; to błąd — w pustym vectorze nie ma żadnego pudełka, więc nie ma czego zmieniać. Indeks zmienia istniejący element, a push_back tworzy nowy. Jeśli chcesz od razu mieć pudełka 0, 1, 2…, stwórz vector z rozmiarem: vector<int> v(n);.
Zbieranie wybranych elementów
Teraz coś, czego zwykłą tablicą nie zrobisz wygodnie. Wczytujesz liczby i chcesz zebrać osobno tylko parzyste. Ile ich będzie? Nie wiadomo — może wszystkie, może żadna. Z vectorem nie musisz tego wiedzieć: tworzysz pusty vector i dokładasz do niego tylko te liczby, które pasują. Na końcu size() powie, ile ich zebrałeś.
int n;
cin >> n;
vector<int> parzyste, nieparzyste;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) parzyste.push_back(x);
else nieparzyste.push_back(x);
}
cout << "parzystych " << parzyste.size() << ":";
for (int i = 0; i < parzyste.size(); i++) cout << " " << parzyste[i];
cout << "\nnieparzystych " << nieparzyste.size() << ":";
for (int i = 0; i < nieparzyste.size(); i++) cout << " " << nieparzyste[i];
cout << "\n";
W jednej linijce możesz utworzyć kilka vectorów, oddzielając nazwy przecinkami — tak samo jak kilka zmiennych int.
Zwróć uwagę: elementy w zebranych vectorach są w tej samej kolejności, w jakiej przyszły na wejściu. push_back zawsze dokłada na koniec, więc kolejność się nie miesza.
Z lekcji o modulo pamiętasz, że -3 % 2 to −1, a nie 1. Dlatego parzystość sprawdzamy warunkiem x % 2 == 0.
Wczytywanie aż do końca danych
W lekcji o napisach poznałeś pętlę while (cin >> s), która wczytuje słowa, dopóki są. Z liczbami działa to tak samo. A ponieważ nie wiesz, ile liczb przyjdzie, push_back jest tu idealny: vector urośnie dokładnie do tylu elementów, ile było w danych.
vector<int> v;
int x;
while (cin >> x) {
v.push_back(x);
}
cout << "wczytano " << v.size() << " liczb\n";
for (int i = v.size() - 1; i >= 0; i--) {
cout << v[i] << " ";
}
cout << "\n";
Pętla while (cin >> x) kończy się sama, gdy dane się skończą. Nieważne, czy liczby są w jednym wierszu, czy w kilku — cin przeskakuje spacje i końce wierszy.
Kiedy testujesz taki program w konsoli, koniec danych zaznaczasz kombinacją klawiszy: Ctrl+Z i Enter w Windowsie albo Ctrl+D w Linuksie i na Macu. Sprawdzarka robi to sama.
back, front i pop_back — ostatni element
Wyobraź sobie stos talerzy. Nowy talerz kładziesz na górę, a zdejmujesz zawsze ten z góry. Vector świetnie się do tego nadaje, jeśli „górą” nazwiesz jego koniec. push_back kładzie talerz, v.back() mówi, jaki talerz jest na górze, a v.pop_back() go zdejmuje — vector skraca się o 1. Jest też v.front(), czyli pierwszy element.
vector<int> v = {4, 8, 15, 16};
cout << v.front() << " " << v.back() << "\n";
v.pop_back(); // zabiera 16
cout << v.back() << " " << v.size() << "\n";
v.pop_back(); // zabiera 15
v.push_back(42);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << "\n";
| zapis | to samo co |
|---|---|
v.front() | v[0] |
v.back() | v[v.size() - 1] |
v.pop_back(); | usuń ostatni element |
empty() — czy vector jest pusty?
v.empty() zwraca prawdę, gdy vector nie ma żadnego elementu — to samo co v.size() == 0. Sprawdzaj to zawsze, zanim zawołasz back(), front() albo pop_back(): na pustym vectorze te polecenia nie mają czego wziąć i program się wysypie. Klasyczny przykład: edytor z przyciskiem „cofnij”.
vector<string> tekst;
string polecenie;
while (cin >> polecenie) {
if (polecenie == "COFNIJ") {
if (!tekst.empty()) tekst.pop_back(); // jest co cofnąć?
} else {
tekst.push_back(polecenie);
}
}
if (tekst.empty()) cout << "pusto";
for (int i = 0; i < tekst.size(); i++) cout << tekst[i] << " ";
cout << "\n";
Trzy pierwsze COFNIJ zabierają po kolei „psa”, „ma” i „Ala”. Czwarte trafia na pusty vector — warunek !tekst.empty() jest fałszywy, więc nic się nie dzieje. Bez tego warunku program by się wysypał.
Wykrzyknik ! to „nie” z lekcji o if-ach: !tekst.empty() czytaj „tekst nie jest pusty”.
v.size() zwraca liczbę bez znaku — taką, która nie może być ujemna. Gdy vector jest pusty, v.size() - 1 nie daje −1, tylko gigantyczną liczbę (ponad 18 trylionów). Pętla for (int i = 0; i < v.size() - 1; i++) na pustym vectorze kręci się więc bardzo długo i wychodzi poza vector. Bezpiecznie piszesz i + 1 < v.size() albo najpierw zamieniasz rozmiar na int: (int)v.size() - 1.
Cyfry liczby w vectorze
Z lekcji o modulo umiesz wyciągać cyfry liczby od końca: n % 10 to ostatnia cyfra, a n /= 10 ją odcina. Teraz możesz te cyfry gdzieś zebrać. Trafiają do vectora od końca — jedności w pudełku 0 — więc do wypisania liczby „po ludzku” idziesz pętlą od tyłu.
long long n;
cin >> n;
vector<int> c;
while (n > 0) {
c.push_back(n % 10); // ostatnia cyfra
n /= 10; // odcinamy ją
}
cout << "cyfr: " << c.size() << "\n";
for (int i = c.size() - 1; i >= 0; i--) {
cout << c[i] << " ";
}
cout << "\n";
Uwaga na liczbę 0: pętla while (n > 0) nie wykona się ani razu i vector zostanie pusty. Jeśli zadanie może dać zero, obsłuż je osobno.
clear, resize i assign — zmiana rozmiaru naraz
Trzy metody zmieniają vector hurtowo. v.clear() usuwa wszystkie elementy — vector staje się pusty i można go używać od nowa. v.resize(n) zmienia rozmiar na n: gdy n jest większe, na końcu dochodzą zera, a gdy mniejsze — elementy z końca są obcinane. v.assign(n, x) wyrzuca starą zawartość i wpisuje n razy wartość x, tak jak vector<int> v(n, x); przy tworzeniu.
vector<int> v = {13, 8};
v.resize(5); // {13, 8, 0, 0, 0}
v[4] = 1;
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << "\n";
v.resize(2); // {13, 8}
cout << v.size() << " " << v.back() << "\n";
v.assign(3, -2); // {-2, -2, -2}
cout << v[0] + v[1] + v[2] << "\n";
v.clear(); // { }
cout << v.size() << " " << v.empty() << "\n";
resize przydaje się, gdy rozmiar zmienia się po drodze. Na przykład liczysz głosy na kandydatów o numerach, które poznajesz dopiero z danych: gdy przychodzi głos na kandydata 7, a vector liczników ma tylko 5 pudełek, robisz licz.resize(8); i dopiero wtedy licz[7]++.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v;
v.push_back(3);
v.push_back(9);
cout << v.size() << v[1];
Pokaż odpowiedź
push_back, więc rozmiar 2. Drugi element (indeks 1) to 9.vector<int> v(2);
v.push_back(5);
cout << v.size() << v[0] << v[2];
Pokaż odpowiedź
v(2) to już dwa zera. push_back dokłada trzecie pudełko z 5: vector {0, 0, 5}.vector<int> v = {1, 2, 3};
v.pop_back();
v.push_back(7);
cout << v.back() << v.size();
Pokaż odpowiedź
pop_back zabiera 3, push_back dokłada 7: {1, 2, 7}. Ostatni to 7, rozmiar 3.vector<int> v;
for (int i = 10; i >= 1; i -= 3) {
v.push_back(i);
}
cout << v.size() << " " << v.back();
Pokaż odpowiedź
vector<int> v = {5, 6};
v.resize(4);
cout << v.size() << v[3] << v.front();
Pokaż odpowiedź
resize(4) dokłada dwa zera: {5, 6, 0, 0}. Rozmiar 4, v[3] = 0, pierwszy element 5.vector<int> v = {1, 2, 3, 4};
v.clear();
v.push_back(8);
cout << v.size() << v[0] << v.empty();
Pokaż odpowiedź
clear vector jest pusty, potem dostaje 8. Rozmiar 1, element 8, a empty() to fałsz, czyli 0.vector<int> v;
int n = 345;
while (n > 0) {
v.push_back(n % 10);
n /= 10;
}
cout << v[0] << v.back();
Pokaż odpowiedź
vector<int> v;
int x;
while (cin >> x) {
if (x > 3) v.push_back(x / 2);
}
cout << v.size() << v.front() << v.back();
2 4 6 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ę.
Pętla „dla każdego”, referencja & i vector jako całość
Pętla po indeksach for (int i = 0; i < v.size(); i++) działa zawsze, ale bardzo często indeks nie jest Ci do niczego potrzebny — chcesz po prostu przejść po wszystkich elementach. W lekcji o parach widziałeś już pętlę „dla każdego” z rozpakowywaniem: for (auto [a, b] : t). Teraz poznasz ją porządnie, razem z jednym niepozornym znakiem, który zmienia bardzo dużo: &.
for (int x : v) — dla każdego x z v
Zapis for (int x : v) czytaj: „dla każdego elementu x z vectora v”. Pętla sama bierze elementy po kolei, od pierwszego do ostatniego, i w każdym obrocie wkłada kolejny element do zmiennej x. Nie piszesz żadnego i, warunku ani i++. Uwaga: x to wartość elementu, a nie jego numer!
vector<int> v = {1, 2, 5, 3, -5};
for (int x : v) {
cout << x << " ";
}
cout << "\n";
int suma = 0;
for (int x : v) {
suma += x;
}
cout << suma << "\n";
| obrót | x | suma po obrocie |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 5 | 8 |
| 4 | 3 | 11 |
| 5 | -5 | 6 |
Zamiast typu możesz napisać auto — „C++, ustal typ sam”. W pętli for (auto x : v) zmienna x dostaje typ elementów vectora: dla vector<int> to int, dla vector<string> — string, dla vectora par — para. To bardzo wygodne, gdy typ ma długą nazwę.
vector<string> slowa = {"vector", "to", "lista"};
for (auto s : slowa) {
cout << s.size() << " ";
}
cout << "\n";
string napis = "abc";
for (auto c : napis) { // napis też ma „dla każdego”
cout << c << c << "-";
}
cout << "\n";
Pętla „dla każdego” działa też na napisie — bierze litery po kolei. To kolejny dowód, że napis to rząd znaków, tak jak vector<char>.
Kiedy wybrać którą pętlę? Gdy potrzebujesz numeru elementu (wypisać go, porównać sąsiadów v[i] i v[i + 1], iść od końca) — pętla po indeksach. Gdy wystarczą same wartości — „dla każdego” jest krótsza i trudniej w niej o pomyłkę.
x to kopia — zmiana x nie zmienia vectora
Spróbujmy podwoić wszystkie elementy vectora pętlą „dla każdego”. Wynik może Cię zaskoczyć:
vector<int> v = {1, 2, 3};
for (int x : v) {
x = x * 2; // zmienia tylko kopię!
}
for (int x : v) {
cout << x << " ";
}
cout << "\n";
vector<int> v = {1, 2, 3};
for (int &x : v) {
x = x * 2; // zmienia element vectora
}
for (int x : v) {
cout << x << " ";
}
cout << "\n";
Po lewej x jest kopią elementu: osobnym pudełkiem obok vectora, do którego na chwilę przepisano wartość. Podwajasz kopię, a po obrocie kopia znika — vector zostaje taki, jaki był. Po prawej przed x stoi znak &. To referencja: x nie jest już osobnym pudełkiem, tylko drugą nazwą tego samego pudełka w vectorze. Zmieniasz x — zmieniasz vector.
for (int x : v) | for (int &x : v) | |
|---|---|---|
| czym jest x | kopią elementu | tym samym elementem (referencją) |
| zmiana x zmienia vector? | nie | tak |
| kiedy używać | gdy tylko czytasz: liczysz, wypisujesz, szukasz | gdy zmieniasz albo wczytujesz elementy |
Wczytywanie z & — sposób olimpijczyków
Skoro referencja pozwala wpisywać do pudełek vectora, możesz nią wczytywać dane. To najkrótszy i bardzo popularny sposób: tworzysz n zer, a pętla „dla każdego” z & wpisuje wczytaną liczbę prosto do kolejnego pudełka. Zapamiętaj go — będziesz go pisać w prawie każdym zadaniu.
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) {
cin >> x; // wpisuje prosto do vectora
}
int maks = v[0];
for (auto x : v) {
if (x > maks) maks = x; // tylko czytamy — bez &
}
cout << maks << "\n";
for (auto x : v) cin >> x; wczytuje liczby do kopii, które po chwili znikają. Program nie zgłosi żadnego błędu, a vector zostanie pełen zer. Gdy wynik wygląda tak, jakby dane się nie wczytały — sprawdź, czy nie brakuje &.
Referencja w napisach i parach
Ta sama zasada działa dla każdego typu. for (auto &s : slowa) pozwala zmieniać słowa w vectorze napisów, a for (auto &[imie, pkt] : u) — przegródki par w vectorze par. Bez & zmieniałbyś kopie.
vector<string> slowa = {"ala", "ma", "kota"};
for (auto &s : slowa) {
s[0] = toupper(s[0]); // wielka pierwsza litera
s += "!";
}
for (auto s : slowa) {
cout << s << " ";
}
cout << "\n";
vector<pair<string, int>> u = {{"Ola", 90}, {"Jan", 75}, {"Ewa", 82}};
for (auto &[imie, pkt] : u) {
pkt += 5; // premia dla wszystkich
}
for (auto [imie, pkt] : u) {
cout << imie << " " << pkt << "\n";
}
Vector jako całość: kopia, porównanie, zamiana
Ze zwykłą tablicą nie zrobisz b = a ani a == b — kompilator zaprotestuje albo porówna coś zupełnie innego niż elementy. Vector zachowuje się jak napis: znak = robi pełną, osobną kopię całego vectora, == sprawdza, czy vectory mają te same elementy w tej samej kolejności, a swap(a, b) zamienia całe vectory miejscami. Klamrami możesz też w każdej chwili wpisać do vectora nową zawartość: v = {1, 2, 3};.
vector<int> a = {1, 2, 3};
vector<int> b = a; // osobna kopia
b[0] = 100; // zmieniamy tylko b
cout << a[0] << " " << b[0] << "\n";
cout << (a == b) << "\n";
b[0] = 1;
cout << (a == b) << "\n";
b.push_back(4);
swap(a, b);
cout << a.size() << " " << b.size() << "\n";
a = {7, 7};
cout << a.size() << " " << a[1] << "\n";
Po b = a masz dwa niezależne vectory. Zmiana b[0] nie rusza a — tak samo jak przy napisach i parach.
Vectory są równe tylko wtedy, gdy mają ten sam rozmiar i na każdej pozycji ten sam element. {1, 2, 3} i {1, 2, 3, 4} nie są równe, choć zaczynają się tak samo.
Porównywanie vectorów jak słów w słowniku
Vectory porównują się też znakami < i > — dokładnie tak jak napisy i pary. Najpierw porównywane są pierwsze elementy. Jeśli są różne, decydują. Jeśli równe — porównywane są drugie elementy, i tak dalej. Gdy jeden vector jest początkiem drugiego, krótszy jest mniejszy, tak jak „kot” jest przed „kotek” w słowniku.
vector<int> a = {1, 2, 9};
vector<int> b = {1, 3};
vector<int> c = {1, 2};
cout << (a < b) << "\n"; // 2 < 3 na drugiej pozycji
cout << (c < a) << "\n"; // c to początek a
cout << (b < c) << "\n";
| porównanie | co decyduje | wynik |
|---|---|---|
{1, 2, 9} < {1, 3} | pozycja 1: 2 < 3 | prawda |
{1, 2} < {1, 2, 9} | krótszy jest początkiem dłuższego | prawda |
{1, 3} < {1, 2} | pozycja 1: 3 > 2 | fałsz |
Nowa runda na kopii
Kopia vectora przydaje się w symulacjach, w których każdy element zmienia się na podstawie starych wartości sąsiadów. Przykład: w każdej rundzie każda liczba staje się sumą swoich sąsiadów (brzegi mają jednego sąsiada). Jeśli zmieniasz vector w miejscu, to przy liczeniu v[2] masz już nową wartość v[1], a nie starą. Rozwiązanie: liczysz nową rundę w osobnym vectorze, a na koniec rundy przepisujesz go do starego.
vector<int> v = {1, 0, 0, 0, 1};
for (int runda = 1; runda <= 3; runda++) {
vector<int> nowy(v.size());
for (int i = 0; i < v.size(); i++) {
int s = 0;
if (i > 0) s += v[i - 1];
if (i + 1 < v.size()) s += v[i + 1];
nowy[i] = s;
}
v = nowy; // koniec rundy
for (auto x : v) cout << x << " ";
cout << "\n";
}
W każdej rundzie nowy liczony jest wyłącznie ze starego v, więc kolejność liczenia pudełek nie ma znaczenia. Linijka v = nowy; kończy rundę: od teraz to nowe wartości są „stare”.
Warunki i > 0 i i + 1 < v.size() pilnują brzegów — tak samo jak przy sąsiadach na planszy w lekcji o parach.
for (auto x : v) nie rób v.push_back ani v.pop_back. Pętla „dla każdego” ustala na starcie, gdzie vector się kończy — gdy rozmiar zmieni się w trakcie, pętla może czytać nieistniejące pudełka. Jeśli musisz dokładać elementy, użyj pętli po indeksach albo zbieraj je do innego vectora.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {4, 1, 3};
for (int x : v) {
cout << x * 2;
}
Pokaż odpowiedź
vector<int> v = {4, 1, 3};
for (int x : v) {
x = 0;
}
cout << v[0] + v[1] + v[2];
Pokaż odpowiedź
& zerujemy tylko kopie. Vector się nie zmienia: 4 + 1 + 3 = 8.vector<int> v = {4, 1, 3};
for (int &x : v) {
x = x + 10;
}
cout << v[0] << v[2];
Pokaż odpowiedź
& zmieniamy prawdziwe elementy: {14, 11, 13}. Wypisujemy 14 i 13 bez spacji.vector<int> v = {5, 2, 8, 1};
int ile = 0;
for (auto x : v) {
if (x > 3) ile++;
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {1, 2};
vector<int> b = a;
b.push_back(3);
cout << a.size() << b.size();
Pokaż odpowiedź
b to osobna kopia — dokładanie do niej nie zmienia a.vector<int> a = {2, 5}, b = {2, 4, 9};
cout << (a < b) << (a == b) << (b < a);
Pokaż odpowiedź
b jest mniejszy: a < b to 0, a == b to 0, b < a to 1.vector<string> s = {"ab", "c"};
for (auto &w : s) {
w = w + w;
}
cout << s[0] << s[1];
Pokaż odpowiedź
& każde słowo zostaje podwojone w vectorze: „abab” i „cc”.vector<pair<int, int>> v = {{1, 2}, {3, 4}};
int s = 0;
for (auto [a, b] : v) {
s += a * b;
}
cout << s;
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ę.
begin(), end() i polecenia, które działają na kawałku vectora
Do tej pory miejsce w vectorze wskazywałeś numerem: v[2]. Niektóre bardzo przydatne polecenia nie przyjmują jednak numeru, tylko coś innego — iterator. Znasz już jedno takie polecenie: w lekcji o parach pisałeś sort(t, t + n). Dla vectora wygląda to tak: sort(v.begin(), v.end()). W tej części zrozumiesz, czym są begin() i end(), i poznasz polecenia, które z nich korzystają: usuwanie, wstawianie, sortowanie, odwracanie, liczenie i szukanie.
Iterator to strzałka
Iterator to strzałka, która pokazuje jedno pudełko vectora. Pomyśl o zakładce w książce: numer strony to indeks, zakładka to iterator, a tekst wydrukowany na stronie to wartość. Zakładka nie jest tekstem ani numerem — mówi tylko, gdzie patrzysz. I tak jak zakładkę, strzałkę można przesuwać.
begin() i gwiazdka
v.begin() to strzałka na pierwszy element vectora — ten o numerze 0. Strzałkę możesz zapisać w zmiennej. Jej typ ma bardzo długą nazwę, więc piszesz auto. Żeby zobaczyć, co leży pod strzałką, stawiasz przed nią gwiazdkę: *it czytaj „to, co jest pod strzałką it”. Strzałkę przesuwasz w prawo przez it++ (o jedno pudełko) albo it + k (o k pudełek).
vector<int> v = {4, 8, 15, 16, 23};
auto it = v.begin(); // strzałka na v[0]
cout << *it << "\n"; // 4
it++; // o jedno w prawo
cout << *it << "\n"; // 8
it = it + 2; // o dwa w prawo
cout << *it << "\n"; // 16
*it = 100; // zmieniamy to, co pod strzałką
cout << v[3] << "\n";
cout << *(v.begin() + 1) << "\n";
v.begin() + k pokazuje na element o indeksie k. Dlatego *(v.begin() + k) to to samo co v[k]. Ten zapis — v.begin() + k — będziesz pisać za każdym razem, gdy polecenie chce iteratora, a Ty myślisz o numerze pudełka.
vector<int> v = {4, 8, 15};
auto it = v.begin();
cout << it << "\n"; // BŁĄD: to strzałka, nie liczba
Bez gwiazdki program się nie skompiluje: strzałka to nie liczba, więc cout nie wie, co z nią zrobić. Chcesz wartość — pisz *it.
end() — strzałka ZA ostatnim elementem
Tu jest najważniejsza pułapka tej części: v.end() nie pokazuje na ostatni element. Pokazuje na miejsce tuż za nim, w którym nie ma już żadnego pudełka — jak meta za ostatnim zawodnikiem. Ostatni element to *(v.end() - 1), a *v.end() to czytanie spoza vectora, tak samo groźne jak v[v.size()].
Dlaczego tak dziwnie? Bo dokładnie tak samo działa n w zwykłej pętli for (int i = 0; i < n; i++): pudełka n już nie ma, to „pierwszy numer za vectorem”, i pętla kończy się, gdy i do niego dojdzie. end() jest dla strzałek tym, czym n dla indeksów. Dzięki temu:
- od
begin()doend()jest dokładnie tyle kroków, ile elementów:v.end() - v.begin()tov.size(); - w pustym vectorze
begin()iend()stoją w tym samym miejscu — od razu widać, że nic nie ma; - kawałek vectora opisujesz dwiema strzałkami: od pierwszej (wliczamy) do drugiej (nie wliczamy). Matematycy zapisują to jako [od, do).
vector<int> v = {4, 8, 15, 16, 23};
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
cout << "\n";
cout << *(v.end() - 1) << " " << v.end() - v.begin() << "\n";
Ta pętla robi to samo co for (auto x : v). I to nie przypadek: pętla „dla każdego” to w środku właśnie taka pętla ze strzałką — startuje od begin(), w każdym obrocie bierze *it, przesuwa strzałkę i kończy, gdy dojdzie do end(). Pętli ze strzałką na co dzień pisać nie musisz, ale dobrze wiedzieć, co dzieje się pod spodem.
erase — usuń element ze środka
v.erase(v.begin() + k); usuwa element o indeksie k. Wszystkie elementy za nim przesuwają się o jedno pudełko w lewo, a vector skraca się o 1. Gdy podasz dwie strzałki, erase usunie cały kawałek — od pierwszej strzałki (wliczamy) do drugiej (nie wliczamy).
vector<int> v = {1, 2, 3, 4, 5, 6};
v.erase(v.begin() + 2); // usuwa 3
for (auto x : v) cout << x << " ";
cout << "\n";
v.erase(v.begin() + 1, v.begin() + 3); // usuwa indeksy 1 i 2
for (auto x : v) cout << x << " ";
cout << "\n";
v.erase(v.begin()); // usuwa pierwszy
v.erase(v.end() - 1); // usuwa ostatni
for (auto x : v) cout << x << " ";
cout << "\n";
v.begin() + 1, a potem znowu v.begin() + 1, za drugim razem usuwasz element, który na początku miał numer 2. Planując kilka erase naraz, rysuj vector po każdym kroku — albo usuwaj od końca, wtedy numery wcześniejszych elementów się nie zmieniają.
insert — wstaw element w środek
v.insert(v.begin() + k, x); wstawia x przed pudełko, na które pokazuje strzałka — czyli tak, że x dostaje numer k. Elementy od numeru k przesuwają się w prawo, a vector rośnie o 1. Wstawienie przed end() to dopisanie na sam koniec, czyli to samo co push_back.
vector<int> v = {1, 2, 3};
v.insert(v.begin() + 1, 9); // {1, 9, 2, 3}
v.insert(v.begin(), 7); // {7, 1, 9, 2, 3}
v.insert(v.end(), 5); // {7, 1, 9, 2, 3, 5}
for (auto x : v) cout << x << " ";
cout << "\n";
vector<int> b = {0, 0};
v.insert(v.end(), b.begin(), b.end()); // doklej cały vector b
cout << v.size() << "\n";
Słowo ostrzeżenia: erase i insert na początku albo w środku vectora są wolne — muszą przesunąć wszystkie elementy za tym miejscem. Dla vectora z kilkoma tysiącami elementów to bez znaczenia, ale gdy robisz sto tysięcy takich operacji na stu tysiącach liczb, program nie zmieści się w czasie. push_back i pop_back działają na końcu, więc są błyskawiczne.
Gotowe polecenia na zakresie [od, do)
W bibliotece <algorithm> (jest w <bits/stdc++.h>) mieszka mnóstwo gotowych poleceń. Każde dostaje dwie strzałki i działa na kawałku od pierwszej (wliczamy) do drugiej (nie wliczamy). Gdy podasz v.begin() i v.end(), polecenie działa na całym vectorze. Oto najważniejsze:
| polecenie | co robi | przykład dla {5, 2, 9, 2, 7} |
|---|---|---|
sort(v.begin(), v.end()); | układa rosnąco | {2, 2, 5, 7, 9} |
reverse(v.begin(), v.end()); | odwraca kolejność | {7, 2, 9, 2, 5} |
count(v.begin(), v.end(), 2) | ile razy występuje 2 | 2 |
*max_element(v.begin(), v.end()) | największy element | 9 |
*min_element(v.begin(), v.end()) | najmniejszy element | 2 |
max_element(v.begin(), v.end()) - v.begin() | numer pierwszego największego | 2 |
find(v.begin(), v.end(), 9) - v.begin() | numer pierwszego wystąpienia 9 | 2 |
vector<int> v = {5, 2, 9, 2, 7};
cout << count(v.begin(), v.end(), 2) << "\n";
cout << *max_element(v.begin(), v.end()) << " ";
cout << max_element(v.begin(), v.end()) - v.begin() << "\n";
reverse(v.begin(), v.end());
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin(), v.end());
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin(), v.end());
reverse(v.begin(), v.end()); // malejąco
for (auto x : v) cout << x << " ";
cout << "\n";
max_element i min_element zwracają strzałkę na największy (najmniejszy) element. Gwiazdka daje jego wartość, a odjęcie v.begin() — jego numer. Gdy największych jest kilka, strzałka pokazuje pierwszy z nich.
Malejąco sortujesz w dwóch krokach: najpierw sort, potem reverse.
Uwaga: na pustym vectorze *max_element czyta spoza vectora — tak jak v[0].
Kawałek zamiast całości
Najciekawsze jest to, że strzałki nie muszą obejmować całego vectora. sort(v.begin(), v.begin() + 3) sortuje tylko trzy pierwsze elementy, a reverse(v.begin() + a, v.begin() + b + 1) odwraca kawałek od numeru a do numeru b włącznie — zwróć uwagę na + 1, bo druga strzałka pokazuje pudełko, którego już nie bierzemy.
vector<int> v = {5, 2, 9, 1, 7, 3};
sort(v.begin(), v.begin() + 3); // tylko 5, 2, 9
for (auto x : v) cout << x << " ";
cout << "\n";
int a = 2, b = 4;
reverse(v.begin() + a, v.begin() + b + 1); // numery 2..4
for (auto x : v) cout << x << " ";
cout << "\n";
find — gdzie jest x?
find(v.begin(), v.end(), x) szuka x od lewej i zwraca strzałkę na jego pierwsze wystąpienie. A jeśli x w ogóle nie ma? Wtedy zwraca v.end() — strzałkę „za vectorem”, czyli „nie znalazłem”. Dlatego przed odczytem zawsze sprawdzasz, czy wynik jest różny od end().
vector<int> v = {4, 8, 15, 16, 23};
int szukane[3] = {15, 42, 4};
for (int x : szukane) {
auto it = find(v.begin(), v.end(), x);
if (it == v.end()) {
cout << x << ": nie ma\n";
} else {
cout << x << ": numer " << it - v.begin() << "\n";
}
}
Ciekawostka: pętla „dla każdego” działa też na zwykłej tablicy szukane. Nie działa za to szukane.size() — tablica nie ma metod.
find przegląda vector od lewej do prawej, element po elemencie — robi dokładnie to, co Twoja pętla z break z lekcji o tablicach, tylko w jednej linijce.
Usuwanie wszystkich wystąpień — pułapka
Chcesz usunąć z vectora wszystkie dwójki. Pierwszy pomysł: pętla po indeksach i erase, gdy trafisz na 2. Zobacz, co się stanie, gdy dwie dwójki stoją obok siebie:
vector<int> v = {1, 2, 2, 3, 2};
for (int i = 0; i < v.size(); i++) {
if (v[i] == 2) {
v.erase(v.begin() + i);
}
}
for (auto x : v) cout << x << " ";
cout << "\n";
vector<int> v = {1, 2, 2, 3, 2};
vector<int> zostaja;
for (auto x : v) {
if (x != 2) zostaja.push_back(x);
}
v = zostaja;
for (auto x : v) cout << x << " ";
cout << "\n";
Po lewej: przy i = 1 usuwamy dwójkę, a druga dwójka przesuwa się na numer 1. Ale pętla robi i++ i patrzy już na numer 2 — przeskakuje ją. Po prawej: zamiast usuwać, budujemy nowy vector z elementów, które mają zostać, i podmieniamy stary. Taki sposób jest prosty, trudno w nim o pomyłkę i jest szybki nawet dla ogromnych vectorów.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {3, 6, 9, 12};
cout << *(v.begin() + 2) << " " << *(v.end() - 1);
Pokaż odpowiedź
begin() + 2 pokazuje numer 2 (9), a end() - 1 — ostatni element (12).vector<int> v = {3, 6, 9, 12};
cout << v.end() - v.begin();
Pokaż odpowiedź
begin() do end() jest tyle kroków, ile elementów.vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 1);
v.erase(v.begin() + 1);
for (auto x : v) cout << x;
Pokaż odpowiedź
erase usuwa 2: {1, 3, 4, 5}. Teraz pod numerem 1 stoi 3 — drugi erase usuwa właśnie ją.vector<int> v = {1, 2, 3};
v.insert(v.begin() + 2, 8);
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {4, 1, 4, 2, 4};
cout << count(v.begin(), v.end(), 4) << *min_element(v.begin(), v.end());
Pokaż odpowiedź
vector<int> v = {6, 2, 9, 9, 1};
cout << max_element(v.begin(), v.end()) - v.begin();
Pokaż odpowiedź
vector<int> v = {5, 4, 3, 2, 1};
sort(v.begin() + 1, v.begin() + 4);
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {7, 3, 5};
auto it = find(v.begin(), v.end(), 4);
cout << (it == v.end()) << " " << it - v.begin();
Pokaż odpowiedź
find zwraca end(). Odległość od begin() to rozmiar vectora: 3.9 ć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ę.
Vector vectorów: tabele, wiersze różnej długości i grupy
W lekcji o tablicach poznałeś tablice dwuwymiarowe: int t[100][100], wiersze i kolumny, t[w][k]. Vector też ma swoją wersję dwuwymiarową — i jest ona wygodniejsza, bo wymiary bierzesz prosto z wejścia, a każdy wiersz może mieć inną długość. Pomysł jest prosty: skoro w vectorze możesz trzymać dowolny typ, możesz trzymać w nim… vectory.
Każdy wiersz to vector
vector<vector<int>> to vector, którego elementami są vectory liczb. Każdy element dużego vectora to jeden wiersz tabeli. m.size() to liczba wierszy, m[0].size() — długość wiersza 0, czyli liczba kolumn. Do liczby dostajesz się dwoma nawiasami: m[wiersz][kolumna].
vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}};
cout << m.size() << " " << m[0].size() << "\n";
cout << m[1][2] << "\n";
m[0][1] = 20;
for (int w = 0; w < m.size(); w++) {
for (int k = 0; k < m[w].size(); k++) {
cout << m[w][k] << " ";
}
cout << "\n";
}
| zapis | typ | co to jest |
|---|---|---|
m | vector<vector<int>> | cała tabela |
m[1] | vector<int> | wiersz {4, 5, 6} |
m[1][2] | int | liczba 6 |
Tabela n × k wypełniona zerami
Pamiętasz wzór „ile razy, co”: vector<int> v(5, 0); to pięć zer? Tabelę tworzysz dokładnie tak samo, tylko powtarzasz nie liczbę, ale cały wiersz. vector<vector<int>> m(n, vector<int>(k, 0)); czytaj: „n razy wiersz, który składa się z k zer”.
int n, k;
cin >> n >> k;
vector<vector<int>> m(n, vector<int>(k, 0));
for (int w = 0; w < n; w++) {
for (int c = 0; c < k; c++) {
cin >> m[w][c];
}
}
for (int w = 0; w < n; w++) {
int suma = 0;
for (int c = 0; c < k; c++) suma += m[w][c];
cout << "wiersz " << w << ": " << suma << "\n";
}
Pętle są takie same jak przy tablicy dwuwymiarowej: zewnętrzna po wierszach, wewnętrzna po kolumnach. Różnica jest jedna, ale ważna: tablicę musiałeś zrobić z zapasem, na przykład int t[1005][1005], i wynieść przed main. Vector 2D ma dokładnie n wierszy po k kolumn i może spokojnie leżeć w main.
Jeśli zapomnisz o drugim nawiasie i napiszesz vector<vector<int>> m(n);, dostaniesz n pustych wierszy — i m[w][c] będzie czytać poza nimi.
Pętla „dla każdego” w dwóch wymiarach
Pętla „dla każdego” po vectorze 2D bierze kolejne wiersze. Każdy wiersz to vector, więc w środku możesz zrobić drugą pętlę „dla każdego” — po liczbach w wierszu. Do wczytywania potrzebujesz & w obu pętlach; do czytania — w żadnej.
int n, k;
cin >> n >> k;
vector<vector<int>> m(n, vector<int>(k));
for (auto &wiersz : m) {
for (auto &x : wiersz) cin >> x;
}
int maks = m[0][0];
for (auto wiersz : m) {
for (auto x : wiersz) maks = max(maks, x);
}
cout << maks << "\n";
auto &wiersz to referencja do całego wiersza, a auto &x — do liczby w nim. Gdyby zabrakło pierwszego &, wczytywałbyś do kopii wiersza i tabela zostałaby pełna zer.
W drugiej pętli auto wiersz robi kopię każdego wiersza. Przy małych tabelach to nic nie szkodzi; przy dużych możesz pisać auto &wiersz także przy czytaniu, żeby nie kopiować.
Wiersze różnej długości
Tu vector 2D wyprzedza tablicę. Każdy wiersz jest osobnym vectorem, więc może mieć własną długość. Tworzysz n pustych wierszy — vector<vector<int>> t(n); — a potem do każdego dokładasz tyle elementów, ile chcesz. Klasyczny przykład to trójkąt Pascala: wiersz numer i ma i + 1 liczb, na brzegach są jedynki, a każda liczba w środku to suma dwóch liczb nad nią.
int n = 5;
vector<vector<int>> t(n); // n pustych wierszy
for (int i = 0; i < n; i++) {
t[i].push_back(1); // lewy brzeg
for (int j = 1; j < i; j++) {
t[i].push_back(t[i - 1][j - 1] + t[i - 1][j]);
}
if (i > 0) t[i].push_back(1); // prawy brzeg
}
for (auto wiersz : t) {
for (auto x : wiersz) cout << x << " ";
cout << "\n";
}
Przy wypisywaniu nie wpisujesz długości na sztywno — pętla „dla każdego” (albo t[i].size()) sama wie, ile liczb ma dany wiersz.
Grupy: do której szuflady?
Wiersze różnej długości mają jeszcze jedno, bardzo częste zastosowanie: grupowanie. Masz uczniów z różnych klas i chcesz wypisać listę każdej klasy osobno. Robisz osobny vector — „szufladę” — na każdą klasę: vector<vector<string>> klasa(k + 1);. Każdego ucznia wrzucasz do szuflady o numerze jego klasy: klasa[nr].push_back(imie);. Na koniec przechodzisz po szufladach po kolei.
int n, k;
cin >> n >> k;
vector<vector<string>> klasa(k + 1); // szuflady 0..k, używamy 1..k
for (int i = 0; i < n; i++) {
string imie;
int nr;
cin >> imie >> nr;
klasa[nr].push_back(imie);
}
for (int nr = 1; nr <= k; nr++) {
cout << "klasa " << nr << " (" << klasa[nr].size() << "):";
for (auto imie : klasa[nr]) cout << " " << imie;
cout << "\n";
}
Ten sam pomysł — vector szuflad, do których dokładasz przez push_back — wróci do Ciebie w grafach jako lista sąsiedztwa: dla każdej osoby lista jej znajomych, dla każdego miasta lista dróg, które z niego wychodzą.
vector<string> jako plansza
Plansze w zadaniach często przychodzą jako wiersze znaków, na przykład . to wolne pole, a # to ściana. Najwygodniej wczytać je do vector<string>: każdy wiersz planszy to jeden napis. Znak w wierszu w i kolumnie k to p[w][k] — dokładnie tak jak w vectorze 2D, bo napis to rząd znaków.
int n, m;
cin >> n >> m;
vector<string> p(n);
for (auto &wiersz : p) cin >> wiersz;
int sciany = 0;
for (int w = 0; w < n; w++) {
for (int k = 0; k < m; k++) {
if (p[w][k] == '#') sciany++;
}
}
p[0][0] = 'S'; // start
cout << sciany << "\n";
for (auto wiersz : p) cout << wiersz << "\n";
vector<vector<int>> m(3, vector<int>(2)); to 3 wiersze po 2 kolumny, a nie odwrotnie. m[w][k]: pierwszy nawias wybiera wiersz, drugi — kolumnę w tym wierszu. Liczba wierszy to m.size(), a długość wiersza w to m[w].size().
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<vector<int>> m(2, vector<int>(4, 1));
cout << m.size() << m[0].size() << m[1][3];
Pokaż odpowiedź
vector<vector<int>> m = {{5, 6}, {7, 8}, {9, 0}};
cout << m[2][0] + m[0][1];
Pokaż odpowiedź
m[2][0] to 9 (wiersz 2, kolumna 0), a m[0][1] to 6.vector<vector<int>> t(3);
t[1].push_back(4);
t[1].push_back(5);
t[2].push_back(6);
cout << t[0].size() << t[1].size() << t[2].size();
Pokaż odpowiedź
vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}};
int s = 0;
for (auto w : m) s += w[0];
cout << s;
Pokaż odpowiedź
w[0] to pierwsza liczba wiersza: 1 + 4.vector<string> p = {"ab", "cd", "ef"};
cout << p[2][1] << p[0][0] << p.size();
Pokaż odpowiedź
p[2][1] to druga litera trzeciego napisu („f”), p[0][0] to „a”, a napisów są 3.vector<vector<int>> m(2, vector<int>(2));
m[0][1] = 3;
m[1] = m[0];
m[1][0] = 7;
cout << m[0][0] << m[0][1] << m[1][0] << m[1][1];
Pokaż odpowiedź
m[1] = m[0] kopiuje cały wiersz {0, 3}. Potem zmieniamy tylko wiersz 1: {7, 3}. Wiersz 0 zostaje {0, 3}.vector<vector<int>> g(4);
g[1].push_back(2);
g[1].push_back(3);
g[3].push_back(1);
for (auto x : g[1]) cout << x;
cout << g[2].size();
Pokaż odpowiedź
vector<vector<int>> m = {{1, 2}, {3, 4}};
for (auto &w : m) w.push_back(w[0] + w[1]);
cout << m[0][2] << m[1][2] << m[1].size();
Pokaż odpowiedź
& dokładamy do prawdziwych wierszy: {1, 2, 3} i {3, 4, 7}. Każdy ma teraz 3 liczby.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ę.
Podtablica: kawałek bez przerw
Od tej części uczysz się słów, które pojawiają się w treściach prawie wszystkich zadań olimpijskich: podtablica, prefiks, sufiks, a w kolejnych częściach podzbiór, permutacja i palindrom. Jeśli w treści zadania przeczytasz „znajdź podtablicę o największej sumie”, musisz od razu wiedzieć, o jakie kawałki chodzi — bo podtablica i podzbiór to zupełnie co innego, a pomyłka oznacza rozwiązywanie innego zadania. Wszystkie te pojęcia działają tak samo dla tablic, vectorów i napisów.
Definicja
Podtablica (po angielsku subarray) to kawałek tablicy złożony z elementów, które stoją obok siebie, bez przerw. Wybierasz jakiś początek i jakiś koniec, i bierzesz wszystko pomiędzy. Nie wolno niczego pominąć ani zmienić kolejności. W treściach zadań spotkasz też nazwy „spójny fragment” albo „spójny podciąg” — to to samo.
| czy to podtablica a = {1, 5, 4, -6, 15, 9, 2, 1, 1}? | odpowiedź | dlaczego |
|---|---|---|
{5, 4, -6} | TAK | numery 1, 2, 3 stoją obok siebie |
{4, 15} | NIE | pomija −6 — jest przerwa |
{9} | TAK | jeden element też jest podtablicą |
| cała tablica | TAK | od pierwszego do ostatniego |
{-6, 4} | NIE | zła kolejność |
{2, 1, 1} | TAK | numery 6, 7, 8 |
Podtablica to para (I, J)
Żeby opisać podtablicę, wystarczą dwie liczby: numer początku I i numer końca J. Dla tablicy o rozmiarze n zawsze 0 ≤ I ≤ J < n — początek nie może stać za końcem, a gdy I = J, podtablica ma jeden element. Długość podtablicy to J - I + 1. Dwie liczby, które należą do siebie? Z poprzedniej lekcji wiesz, że to idealne miejsce na parę: pair<int, int> p = {1, 3};.
| podtablica {1, 8, 9} | I | J | długość |
|---|---|---|---|
{1} | 0 | 0 | 1 |
{1, 8} | 0 | 1 | 2 |
{1, 8, 9} | 0 | 2 | 3 |
{8} | 1 | 1 | 1 |
{8, 9} | 1 | 2 | 2 |
{9} | 2 | 2 | 1 |
Tablica {1, 8, 9} ma 6 podtablic. Ile ma tablica o rozmiarze n? Policz, ile podtablic zaczyna się na każdym numerze: na numerze 0 jest n możliwych końców, na numerze 1 — o jeden mniej, i tak dalej, aż do jednego końca na ostatnim numerze. Razem n + (n − 1) + … + 1, czyli n · (n + 1) / 2.
Dla n = 3 to 3 · 4 / 2 = 6 — zgadza się. Dla n = 10 to 55, dla n = 1000 już 500 500, a dla n = 100 000 — ponad 5 miliardów. Zapamiętaj: podtablic jest mniej więcej n² / 2.
Wypisz wszystkie podtablice — w trzech krokach
Zadanie: wypisz wszystkie podtablice, każdą w osobnym wierszu. Zróbmy to powoli. Krok 1: dwie pętle — po początku i i po końcu j — dają wszystkie pary (i, j). Krok 2: trzecia pętla po k od i do j wypisuje elementy jednej podtablicy. Krok 3: pary z i > j to nie są podtablice (koniec przed początkiem), więc j zaczynamy od i, a nie od 0.
vector<int> a = {1, 8, 9};
int n = a.size();
for (int i = 0; i < n; i++) { // początek
for (int j = i; j < n; j++) { // koniec — od i!
for (int k = i; k <= j; k++) { // elementy od i do j
cout << a[k] << " ";
}
cout << "\n";
}
}
Zwróć uwagę na int n = a.size(); na początku. Zapisujesz rozmiar do zwykłej zmiennej int i dalej piszesz krótko n — bez kłopotów z liczbami bez znaku z części 2.
Podtablice wychodzą uporządkowane według początku, a przy tym samym początku — według końca. Gdyby zadanie chciało innej kolejności, na przykład od najkrótszych, zewnętrzna pętla szłaby po długości, a wewnętrzna po początku.
Suma każdej podtablicy — bez trzeciej pętli
Teraz chcemy znać sumę każdej podtablicy, na przykład żeby znaleźć największą. Trzecia pętla sumowałaby elementy od nowa dla każdej pary (i, j). Ale zauważ: podtablica (i, j + 1) to podtablica (i, j) plus jeden nowy element a[j + 1]. Wystarczy więc trzymać sumę i dokładać do niej, gdy koniec przesuwa się w prawo.
vector<int> a = {2, -5, 4, 3, -1};
int n = a.size();
int najlepsza = a[0], bi = 0, bj = 0;
for (int i = 0; i < n; i++) {
int suma = 0;
for (int j = i; j < n; j++) {
suma += a[j]; // suma podtablicy (i, j)
if (suma > najlepsza) {
najlepsza = suma;
bi = i;
bj = j;
}
}
}
cout << najlepsza << " od " << bi << " do " << bj << "\n";
Dwie pętle zamiast trzech: dla n = 1000 to około pół miliona kroków zamiast ponad stu milionów. Z lekcji o pętli for pamiętasz, że komputer robi około stu milionów prostych kroków na sekundę — taka różnica decyduje, czy program zmieści się w limicie czasu.
Prefiks — początek tablicy
Prefiks to podtablica, która zaczyna się na samym początku, czyli na numerze 0. Para prefiksu to zawsze (0, J). Tablica o rozmiarze n ma dokładnie n prefiksów — jej koniec J może być równy 0, 1, …, n − 1. Słowo znasz z życia: przedrostek „prze-” w słowie „przedszkole” to prefiks tego słowa.
Sufiks — koniec tablicy
Sufiks to podtablica, która kończy się na samym końcu, czyli na numerze n − 1. Para sufiksu to (I, n − 1). Sufiksów też jest dokładnie n. W słowie „kotek” sufiksem jest „-ek”. Cała tablica jest jednocześnie prefiksem i sufiksem.
| dla a = {5, 4, 9, 1, 3, -5, 2, 1, 1, 7} | co to jest | para (I, J) |
|---|---|---|
{5, 4} | prefiks | (0, 1) |
{1, 7} | sufiks | (8, 9) |
{9, 1, 3} | ani to, ani to — zwykła podtablica | (2, 4) |
| cała tablica | i prefiks, i sufiks | (0, 9) |
{5} | prefiks | (0, 0) |
{7} | sufiks | (9, 9) |
Sumy prefiksów — znowu, ale teraz znasz nazwę
W lekcji o tablicach poznałeś sumy prefiksowe. Teraz rozumiesz, skąd ta nazwa: p[k] to suma prefiksu o długości k, czyli elementów od numeru 0 do k − 1. Każdy kolejny prefiks to poprzedni plus jeden element, więc liczysz je jedną pętlą. A suma dowolnej podtablicy (I, J) to różnica dwóch prefiksów: p[J + 1] - p[I] — od dłuższego prefiksu odejmujesz krótszy, który kończy się tuż przed I.
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<long long> p(n + 1, 0); // p[0] = 0: pusty prefiks
for (int i = 0; i < n; i++) {
p[i + 1] = p[i] + a[i];
}
for (auto x : p) cout << x << " ";
cout << "\n";
int I = 1, J = 3;
cout << "suma od " << I << " do " << J << ": " << p[J + 1] - p[I] << "\n";
Vector sprawdza się tu idealnie: vector<long long> p(n + 1, 0); ma dokładnie tyle pudełek, ile trzeba, a long long chroni przed przepełnieniem, gdy suma wielu dużych liczb nie mieści się w int.
Sufiksy od końca: liderzy
Sufiksy przegląda się pętlą od końca. Przykład: lider to element większy od wszystkich elementów stojących na prawo od niego, czyli większy od całego sufiksu, który zaczyna się zaraz za nim. Idziesz od ostatniego elementu w lewo i pamiętasz maksimum sufiksu, który już przeszedłeś. Element jest liderem, gdy jest większy od tego maksimum.
vector<int> a = {16, 17, 4, 3, 5, 2};
int n = a.size();
vector<int> liderzy;
int maksPrawo = -1000000000; // maksimum sufiksu za i
for (int i = n - 1; i >= 0; i--) {
if (a[i] > maksPrawo) liderzy.push_back(a[i]);
maksPrawo = max(maksPrawo, a[i]);
}
reverse(liderzy.begin(), liderzy.end()); // od lewej do prawej
for (auto x : liderzy) cout << x << " ";
cout << "\n";
Idąc od końca, znajdujemy liderów w kolejności od prawej, więc na koniec odwracamy vector poleceniem reverse z części 4.
Okno: podtablice o stałej długości
Często interesują Cię tylko podtablice o długości k — na przykład „największa suma opadów z k kolejnych dni”. Wyobraź sobie okno o szerokości k, które przesuwasz po tablicy o jedno pudełko w prawo. Przy każdym przesunięciu do okna wchodzi jeden element z prawej, a jeden wychodzi z lewej. Nie trzeba więc liczyć sumy od nowa — wystarczy dodać nowy element i odjąć stary.
vector<int> a = {3, 1, 4, 1, 5, 9, 2};
int n = a.size(), k = 3;
int suma = 0;
for (int i = 0; i < k; i++) suma += a[i]; // pierwsze okno
int najlepsza = suma;
cout << suma << " ";
for (int i = k; i < n; i++) {
suma += a[i] - a[i - k]; // wchodzi a[i], wychodzi a[i - k]
cout << suma << " ";
najlepsza = max(najlepsza, suma);
}
cout << "\nnajwiecej: " << najlepsza << "\n";
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int n = 5, ile = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) ile++;
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {4, 7, 1, 8, 2};
int I = 1, J = 3, s = 0;
for (int k = I; k <= J; k++) s += a[k];
cout << s << " " << J - I + 1;
Pokaż odpowiedź
vector<int> a = {2, 5, 1, 3};
int s = 0;
for (int i = 0; i < a.size(); i++) {
s += a[i];
cout << s << " ";
}
Pokaż odpowiedź
vector<int> a = {2, 5, 1, 3};
int s = 0;
for (int i = a.size() - 1; i >= 0; i--) {
s += a[i];
cout << s << " ";
}
Pokaż odpowiedź
vector<int> p = {0, 3, 8, 8, 10, 16};
cout << p[5] - p[2] << " " << p[3] - p[1];
Pokaż odpowiedź
p[5] − p[2] to suma elementów od numeru 2 do 4, a p[3] − p[1] — od 1 do 2. Z p da się odczytać tablicę: {3, 5, 0, 2, 6}. Sumy: 0 + 2 + 6 = 8 oraz 5 + 0 = 5.vector<int> a = {1, 2, 3, 4, 5, 6};
int k = 4, ile = 0;
for (int i = 0; i + k <= a.size(); i++) ile++;
cout << ile;
Pokaż odpowiedź
vector<int> a = {3, 9, 2, 6, 1};
int m = 0, ile = 0;
for (int i = a.size() - 1; i >= 0; i--) {
if (a[i] > m) ile++;
m = max(m, a[i]);
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {1, -2, 3};
int best = a[0];
for (int i = 0; i < 3; i++) {
int s = 0;
for (int j = i; j < 3; j++) {
s += a[j];
best = max(best, s);
}
}
cout << best;
Pokaż odpowiedź
9 ć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ę.
Podzbiór: bierzemy albo nie. Permutacja: wszystko, ale w innej kolejności
Podtablica to kawałek bez przerw. W tej części poznasz dwa kolejne pojęcia, które opisują, co można „wyciągnąć” z tablicy. Podzbiór pozwala na przerwy — bierzesz dowolne elementy. Permutacja bierze wszystkie elementy, ale ustawia je w innej kolejności. Oba pojęcia pojawiają się w zadaniach typu „sprawdź wszystkie możliwości” — a wtedy trzeba umieć te możliwości po kolei wygenerować.
Podzbiór — dowolne elementy, kolejność zostaje
Podzbiór (po angielsku subset) powstaje tak: przy każdym elemencie tablicy decydujesz — bierzemy albo nie bierzemy. Wybrane elementy nie muszą stać obok siebie. Gdy wypisujemy podzbiór tablicy, elementy zostają w takiej kolejności, w jakiej stały w tablicy — taki ciąg wybranych elementów nazywa się też podciągiem.
| czy to podzbiór a = {1, 5, 4, -6, 15, 9, 2, 1, 1}? | odpowiedź | dlaczego |
|---|---|---|
{1, 15, 1} | TAK | na przykład numery 0, 4 i 7 |
{5, 4} | TAK | i to nawet podtablica |
{1, 1, 1} | TAK | w tablicy są trzy jedynki: 0, 7 i 8 |
{7} | NIE | w tablicy nie ma liczby 7 |
{9, 15} | NIE | 15 stoi przed 9 — kolejność musi zostać |
| cała tablica | TAK | bierzemy wszystko |
Ile jest podzbiorów?
Weźmy tablicę {1, 8, 9}. Przy każdym z trzech elementów mówimy TAK albo NIE. Pierwszy element daje 2 możliwości, drugi — znowu 2 dla każdej z nich, trzeci — znowu 2. Razem 2 · 2 · 2 = 8 podzbiorów, licząc pusty (same NIE). Ogólnie tablica o rozmiarze n ma 2n podzbiorów, czyli 2n − 1 niepustych.
| 1? | 8? | 9? | podzbiór |
|---|---|---|---|
| nie | nie | nie | { } — pusty |
| tak | nie | nie | {1} |
| nie | tak | nie | {8} |
| tak | tak | nie | {1, 8} |
| nie | nie | tak | {9} |
| tak | nie | tak | {1, 9} |
| nie | tak | tak | {8, 9} |
| tak | tak | tak | {1, 8, 9} |
Porównaj z częścią 6: ta sama tablica miała tylko 6 podtablic. Podzbiorów niepustych jest 7 — brakuje wśród podtablic {1, 9}, bo pomija 8.
Każda podtablica jest podzbiorem — to po prostu podzbiór bez przerw. Ale nie każdy podzbiór jest podtablicą.
| n | podtablice: n(n+1)/2 | podzbiory niepuste: 2n − 1 |
|---|---|---|
| 10 | 55 | 1 023 |
| 20 | 210 | 1 048 575 |
| 30 | 465 | ponad miliard |
Podzbiorów robi się bardzo szybko bardzo dużo: każdy nowy element podwaja ich liczbę. Dlatego zadania, w których trzeba sprawdzić wszystkie podzbiory, mają małe n — zwykle najwyżej 20. Gdy w ograniczeniach widzisz n ≤ 20, to często znak, że autor zadania myśli właśnie o przeglądaniu wszystkich podzbiorów.
Czy b jest podzbiorem a? Dwa palce
Zadanie: masz ciąg a i ciąg b. Czy da się otrzymać b, wykreślając niektóre elementy z a? Pomysł: prowadzisz jeden palec po a, a drugi po b. Drugi palec pokazuje element b, którego właśnie szukasz. Idziesz palcem po a od lewej; gdy trafisz na szukany element, przesuwasz drugi palec dalej. Jeśli drugi palec dojdzie do końca b — wszystko znalezione.
vector<int> a = {1, 5, 4, -6, 15, 9, 2, 1, 1};
vector<int> b = {5, -6, 1};
int j = 0; // ile elementów b już znaleziono
for (int i = 0; i < a.size(); i++) {
if (j < b.size() && a[i] == b[j]) j++;
}
if (j == b.size()) cout << "TAK\n";
else cout << "NIE\n";
Czy branie pierwszego pasującego elementu nie może zepsuć sprawy? Nie: im wcześniej znajdziesz element b, tym więcej tablicy zostaje na szukanie następnych. Taki „zachłanny” wybór jest tu zawsze najlepszy.
Wszystkie podzbiory: liczby w systemie dwójkowym
Jak przejrzeć wszystkie podzbiory? Jest piękna sztuczka. Z lekcji o pętli while znasz system dwójkowy: liczba 5 to dwójkowo 101. Zapiszmy liczby od 0 do 7 dwójkowo, każdą na trzech cyfrach: 000, 001, 010, …, 111. To dokładnie wszystkie możliwe ciągi decyzji TAK/NIE dla trzech elementów! Cyfra 1 to TAK, cyfra 0 to NIE. Taką liczbę nazywa się maską.
Która cyfra mówi o którym elemencie? Umówmy się tak, jak wygodnie liczyć: ostatnia cyfra dwójkowa (ta, którą daje m % 2) decyduje o a[0], przedostatnia — o a[1], i tak dalej. Cyfry odczytujesz tak jak w lekcji o while: m % 2 to ostatnia cyfra, a m /= 2 ją odcina.
vector<int> a = {1, 8, 9};
int n = a.size();
int ile = 1;
for (int i = 0; i < n; i++) ile *= 2; // 2 do potęgi n
for (int maska = 0; maska < ile; maska++) {
int m = maska;
int suma = 0;
cout << maska << ": {";
for (int i = 0; i < n; i++) {
if (m % 2 == 1) { // cyfra 1 — bierzemy a[i]
cout << " " << a[i];
suma += a[i];
}
m /= 2; // następna cyfra
}
cout << " } suma " << suma << "\n";
}
| maska | dwójkowo | bierzemy |
|---|---|---|
| 0 | 000 | nic |
| 1 | 001 | a[0] |
| 2 | 010 | a[1] |
| 3 | 011 | a[0], a[1] |
| 4 | 100 | a[2] |
| 5 | 101 | a[0], a[2] |
| 6 | 110 | a[1], a[2] |
| 7 | 111 | wszystko |
Czytaj zapis dwójkowy od prawej: pierwsza cyfra od prawej to a[0]. Na przykład 6 = 110 dwójkowo: a[0] — nie, a[1] — tak, a[2] — tak.
Ten schemat pasuje do mnóstwa zadań: „czy da się wybrać monety o sumie dokładnie S”, „podziel prezenty na dwie kupki tak, by różnica wartości była najmniejsza”, „ile jest wyborów spełniających warunek”. Pętla po maskach robi 2n obrotów, a każdy z nich n kroków — dla n = 20 to około 20 milionów kroków, czyli ułamek sekundy.
Permutacja — te same elementy, inna kolejność
Permutacja to ustawienie wszystkich elementów w jakiejś kolejności. Każdy element występuje dokładnie tyle razy, ile w oryginale — niczego nie dodajemy i niczego nie gubimy, zmienia się tylko kolejność. Permutacjami {1, 2, 3} są: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} i {3, 2, 1}. W zadaniach najczęściej spotkasz permutację liczb od 1 do n: ciąg długości n, w którym każda liczba od 1 do n występuje dokładnie raz.
| czy to permutacja liczb od 1 do n? | odpowiedź |
|---|---|
{3, 1, 2}, n = 3 | TAK |
{1, 2, 2}, n = 3 | NIE — 2 dwa razy, brak 3 |
{4, 1, 2}, n = 3 | NIE — 4 to za dużo |
{2, 1, 4, 3}, n = 4 | TAK |
{1}, n = 1 | TAK |
Ile jest permutacji n różnych elementów? Na pierwsze miejsce możesz wybrać każdy z n elementów, na drugie — każdy z pozostałych n − 1, na trzecie — n − 2… Razem n · (n − 1) · … · 1. Tę liczbę nazywa się silnią i zapisuje n!.
| n | 3 | 5 | 8 | 10 | 13 |
|---|---|---|---|---|---|
| n! | 6 | 120 | 40 320 | 3 628 800 | ponad 6 miliardów |
Czy to permutacja? Liczniki
Sprawdzić, czy ciąg jest permutacją liczb od 1 do n, pomoże tablica liczników z lekcji o tablicach — tym razem jako vector. Każda liczba musi mieścić się między 1 a n i żadna nie może pojawić się drugi raz. Jeśli oba warunki są spełnione dla n liczb, to każda liczba od 1 do n wystąpiła dokładnie raz.
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<int> ile(n + 1, 0); // liczniki dla liczb 1..n
bool ok = true;
for (auto x : a) {
if (x < 1 || x > n) {
ok = false; // spoza zakresu
} else {
ile[x]++;
if (ile[x] > 1) ok = false; // powtórka
}
}
if (ok) cout << "TAK\n";
else cout << "NIE\n";
Najpierw sprawdzamy zakres, a dopiero potem zaglądamy do ile[x]. Odwrotna kolejność to wyjście poza vector, gdy na wejściu trafi się na przykład 100 albo −5.
Drugi sposób: posortować kopię ciągu i sprawdzić, czy wyszło 1, 2, 3, …, n. Też poprawny, tylko trochę wolniejszy.
Czy dwa ciągi to swoje permutacje? Posortuj i porównaj
Dwa ciągi są swoimi permutacjami, gdy mają dokładnie te same elementy, tyle samo razy każdy. Najprostszy test: posortuj oba i porównaj całe vectory przez == (z części 3 wiesz, że vectory się porównują). Po posortowaniu kolejność przestaje mieć znaczenie, więc zostaje tylko pytanie, czy elementy są te same. Z napisami działa to identycznie — tak sprawdza się anagramy, czyli słowa z tych samych liter.
vector<int> a = {3, 1, 2, 3}, b = {2, 3, 3, 1};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << (a == b) << "\n";
string s = "kajak", t = "jakak";
sort(s.begin(), s.end()); // napis też ma begin() i end()
sort(t.begin(), t.end());
cout << s << " " << t << " " << (s == t) << "\n";
Napis ma begin() i end() tak samo jak vector, więc działają na nim wszystkie polecenia z części 4: sort, reverse, count. Posortowany napis to jego litery ułożone alfabetycznie.
next_permutation — wszystkie ustawienia po kolei
Polecenie next_permutation(v.begin(), v.end()) zamienia vector w następną permutację w kolejności słownikowej — tej samej, w której porównują się vectory. Zwraca prawdę, jeśli następna permutacja istnieje, i fałsz, gdy doszliśmy do ostatniej (wtedy vector wraca do ułożenia rosnącego). Żeby przejrzeć wszystkie permutacje, zaczynasz od vectora posortowanego i używasz pętli do … while, którą znasz z lekcji o while: najpierw obsłuż bieżące ustawienie, potem przejdź do następnego.
vector<int> v = {1, 2, 3};
int ile = 0;
do {
for (auto x : v) cout << x << " ";
cout << "\n";
ile++;
} while (next_permutation(v.begin(), v.end()));
cout << "razem " << ile << "\n";
vector<int> v = {2, 1, 1};
sort(v.begin(), v.end()); // najpierw rosnąco!
do {
for (auto x : v) cout << x;
cout << " ";
} while (next_permutation(v.begin(), v.end()));
cout << "\n";
Gdy elementy się powtarzają, next_permutation pokazuje każde różne ustawienie tylko raz: trzy, a nie sześć. Gdybyś zapomniał o sort, pętla zaczęłaby od {2, 1, 1} i pokazała tylko ustawienia „większe” od niego — czyli żadnego więcej.
Dzięki temu możesz rozwiązywać zadania „sprawdź wszystkie kolejności”: w jakiej kolejności odwiedzić miasta, żeby trasa była najkrótsza, ile jest ustawień spełniających jakiś warunek. Pamiętaj tylko o silni: 8! to 40 320, 10! to już ponad 3,6 miliona. Przeglądanie wszystkich permutacji ma sens dla n mniej więcej do 10.
Permutacja jako przepis: kto gdzie stoi
Permutację liczb od 1 do n można czytać jak listę: „na miejscu i stoi osoba p[i]”. Przydaje się wtedy pytanie odwrotne: „na którym miejscu stoi osoba x?”. Odpowiedzi zbierasz w drugim vectorze gdzie: skoro na miejscu i stoi osoba p[i], to gdzie[p[i]] = i. Taki vector to permutacja odwrotna.
int n = 4;
vector<int> p = {0, 3, 1, 4, 2}; // miejsca 1..4, pudełko 0 nieużywane
vector<int> gdzie(n + 1);
for (int i = 1; i <= n; i++) {
gdzie[p[i]] = i; // osoba p[i] stoi na miejscu i
}
for (int x = 1; x <= n; x++) {
cout << "osoba " << x << " na miejscu " << gdzie[x] << "\n";
}
Przy numeracji od 1 robimy vector o jedno pudełko większy i nie używamy pudełka 0. To ten sam trik, co przy tablicy liczników.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int n = 5, ile = 1;
for (int i = 0; i < n; i++) ile *= 2;
cout << ile;
Pokaż odpowiedź
vector<int> a = {4, 7, 2, 5};
int m = 10, s = 0;
for (int i = 0; i < 4; i++) {
if (m % 2 == 1) s += a[i];
m /= 2;
}
cout << s;
Pokaż odpowiedź
a[0] nie, a[1] tak, a[2] nie, a[3] tak. 7 + 5 = 12.vector<int> a = {1, 2, 3, 2, 1}, b = {2, 2, 1};
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (j < b.size() && a[i] == b[j]) j++;
}
cout << j;
Pokaż odpowiedź
vector<int> a = {3, 1, 3}, b = {1, 3, 1};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << (a == b);
Pokaż odpowiedź
vector<int> v = {1, 3, 2};
next_permutation(v.begin(), v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {1, 2, 3, 4};
int ile = 0;
do {
if (v[0] < v[3]) ile++;
} while (next_permutation(v.begin(), v.end()));
cout << ile;
Pokaż odpowiedź
string s = "kot";
int ile = 0;
sort(s.begin(), s.end());
do {
ile++;
} while (next_permutation(s.begin(), s.end()));
cout << ile << s;
Pokaż odpowiedź
next_permutation napis wraca do ułożenia rosnącego: „kot” (k < o < t).vector<int> p = {0, 2, 3, 1};
vector<int> g(4);
for (int i = 1; i <= 3; i++) g[p[i]] = i;
cout << g[1] << g[2] << g[3];
Pokaż odpowiedź
9 ć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ę.
Palindrom: tak samo od przodu i od tyłu
Słowo „kajak” czytane od tyłu to dalej „kajak”. Takie słowa nazywamy palindromami — sprawdzałeś je już w lekcjach o pętlach i napisach. Palindromem może być też ciąg liczb: {1, 2, 3, 2, 1} od tyłu to znowu {1, 2, 3, 2, 1}. W tej części nauczysz się sprawdzać palindromy na vectorach, szukać palindromicznych podtablic, przestawiać elementy w palindrom — a przy okazji poznasz dwa wskaźniki, czyli dwa indeksy, które idą sobie naprzeciw. To jedna z najczęstszych sztuczek olimpijskich.
Lustrzane pary
Vector a o rozmiarze n jest palindromem, gdy pierwszy element jest równy ostatniemu, drugi — przedostatniemu, i tak dalej. Elementowi o numerze i odpowiada w lustrze element o numerze n - 1 - i. Wystarczy sprawdzić pierwszą połowę: i od 0 do n / 2 - 1. Środkowy element przy nieparzystym n nie ma pary — pasuje sam do siebie.
vector<int> a = {1, 2, 3, 2, 1};
int n = a.size();
bool pal = true;
for (int i = 0; i < n / 2; i++) {
if (a[i] != a[n - 1 - i]) pal = false;
}
cout << pal << "\n";
vector<int> r = a;
reverse(r.begin(), r.end()); // drugi sposób
cout << (r == a) << "\n";
| ciąg | palindrom? |
|---|---|
{1, 2, 3, 2, 1} | TAK |
{4, 4} | TAK |
{7} | TAK — jeden element zawsze |
{1, 2, 2, 3} | NIE — 1 i 3 się różnią |
{5, 1, 5, 1} | NIE — od tyłu {1, 5, 1, 5} |
Drugi sposób jest krótszy: kopia, odwrócenie i porównanie całych vectorów. Pierwszy nie potrzebuje kopii i łatwo go przerobić na liczenie różnic — co zaraz zrobimy.
Ile zmian do palindromu?
Ile elementów trzeba zmienić, żeby ciąg stał się palindromem? Każda lustrzana para, w której elementy się różnią, wymaga jednej zmiany — wystarczy jeden z nich przepisać na drugi. Pary, które już się zgadzają, nie kosztują nic. Odpowiedź to więc liczba niezgodnych lustrzanych par.
vector<int> a = {3, 1, 4, 1, 5, 3};
int n = a.size(), zmian = 0;
for (int i = 0; i < n / 2; i++) {
if (a[i] != a[n - 1 - i]) {
zmian++;
a[n - 1 - i] = a[i]; // poprawiamy prawą stronę
}
}
cout << zmian << "\n";
for (auto x : a) cout << x << " ";
cout << "\n";
a[i] z a[n - i] zamiast z a[n - 1 - i]. Dla i = 0 taki program zagląda do a[n], czyli poza vector. Zanim napiszesz pętlę, wypisz pary dla małego przykładu: przy n = 6 to (0, 5), (1, 4), (2, 3), a przy n = 5 — (0, 4), (1, 3), a numer 2 zostaje w środku.
Palindromiczne podtablice: rozszerzanie od środka
Ile podtablic ciągu jest palindromami? Pierwszy pomysł: przejrzyj wszystkie pary (I, J) z części 6 i każdą sprawdź lustrzanymi parami. To trzy pętle — dla n = 300 jeszcze działa, dla n = 5000 już nie. Lepszy pomysł: każdy palindrom ma środek. Stajesz w środku i rozszerzasz palindrom w obie strony, dopóki elementy po obu stronach są równe. Każde udane rozszerzenie to jeden nowy palindrom. Środkiem może być jeden element (palindromy o nieparzystej długości) albo przerwa między dwoma elementami (o parzystej).
vector<int> a = {1, 2, 1, 2, 2};
int n = a.size(), ile = 0;
for (int c = 0; c < n; c++) { // środek w elemencie c
int l = c, r = c;
while (l >= 0 && r < n && a[l] == a[r]) {
ile++;
l--;
r++;
}
}
for (int c = 0; c + 1 < n; c++) { // środek między c i c + 1
int l = c, r = c + 1;
while (l >= 0 && r < n && a[l] == a[r]) {
ile++;
l--;
r++;
}
}
cout << ile << "\n";
Warunek w while najpierw sprawdza, czy l i r są jeszcze w vectorze, a dopiero potem porównuje a[l] z a[r]. Kolejność jest ważna: && przestaje sprawdzać przy pierwszym fałszu, więc nigdy nie zajrzymy poza vector.
Ile dopisać, żeby był palindrom?
Ciąg {1, 2, 3, 2} nie jest palindromem. Ile najmniej elementów trzeba dopisać na końcu, żeby nim był? Pomysł: znajdź najdłuższy sufiks, który już jest palindromem — tutaj {2, 3, 2}. To, co stoi przed nim ({1}), trzeba odbić lustrzanie i dopisać na końcu. Dopisujesz więc n minus długość tego sufiksu elementów.
vector<int> a = {1, 2, 3, 2};
int n = a.size();
int start = 0; // gdzie zaczyna się sufiks-palindrom
for (int I = 0; I < n; I++) { // od najdłuższego sufiksu
bool pal = true;
for (int i = I, j = n - 1; i < j; i++, j--) {
if (a[i] != a[j]) pal = false;
}
if (pal) {
start = I;
break;
}
}
for (int i = start - 1; i >= 0; i--) a.push_back(a[i]);
cout << start << "\n";
for (auto x : a) cout << x << " ";
cout << "\n";
Pętla wewnętrzna ma dwa liczniki naraz: i idzie od lewej, j od prawej, a pętla kręci się, dopóki się nie miną. Przecinek w i++, j-- pozwala zmienić oba w jednym kroku.
Sufiksy sprawdzamy od najdłuższego, więc pierwszy znaleziony palindrom jest najdłuższy — break kończy szukanie. Ostatni sufiks (jeden element) jest palindromem zawsze, więc coś na pewno znajdziemy.
Permutacja, która jest palindromem
Czy elementy ciągu da się przestawić tak, by powstał palindrom? Pomyśl, jak wygląda palindrom: każdy element z lewej połowy ma swoją parę w prawej. Każda wartość musi więc wystąpić parzystą liczbę razy — z jednym wyjątkiem: jedna wartość może wystąpić nieparzyście, bo jej jeden egzemplarz stanie w środku. Wystarczy policzyć, ile wartości występuje nieparzystą liczbę razy.
vector<int> a = {3, 1, 2, 1, 3, 1, 1};
vector<int> ile(101, 0); // liczby od 0 do 100
for (auto x : a) ile[x]++;
int nieparzystych = 0;
for (int w = 0; w <= 100; w++) {
if (ile[w] % 2 == 1) nieparzystych++;
}
if (nieparzystych <= 1) cout << "TAK\n";
else cout << "NIE\n";
Jedynka występuje 4 razy, trójka 2 razy, a dwójka raz — tylko jedna wartość nieparzyście, więc się da, na przykład {1, 1, 3, 2, 3, 1, 1}: dwójka w środku, reszta symetrycznie.
To przykład zadania, w którym spotykają się dwa pojęcia z tej lekcji: szukamy permutacji, która jest palindromem. Zamiast przeglądać wszystkie 7! = 5040 permutacji, wystarczy jedna obserwacja i liczniki.
Dwa wskaźniki: pary o sumie najwyżej S
Lustrzane pary to dwa indeksy, które idą sobie naprzeciw. Ten sam ruch rozwiązuje wiele innych zadań na posortowanym vectorze. Przykład: ile jest par i < j, w których a[i] + a[j] ≤ S? Sprawdzanie wszystkich par to n² / 2 kroków. Szybciej: lewy wskaźnik i startuje z początku, prawy j z końca.
- Jeśli
a[i] + a[j] ≤ S, to a[i] pasuje z a[j] — i z każdym elementem między nimi, bo są mniejsze od a[j]. To j − i par naraz. Przesuń i w prawo. - Jeśli
a[i] + a[j] > S, to a[j] jest za duży nawet dla najmniejszego a[i] — już do niczego się nie przyda. Przesuń j w lewo.
Każdy krok przesuwa jeden ze wskaźników, a spotkają się po najwyżej n krokach.
vector<int> a = {5, 1, 7, 2, 4};
int S = 7;
sort(a.begin(), a.end()); // {1, 2, 4, 5, 7}
int i = 0, j = a.size() - 1;
long long par = 0;
while (i < j) {
if (a[i] + a[j] <= S) {
par += j - i; // a[i] z każdym od i+1 do j
i++;
} else {
j--; // a[j] za duże
}
}
cout << par << "\n";
| i | j | a[i] + a[j] | ruch | par |
|---|---|---|---|---|
| 0 | 4 | 1 + 7 = 8 | j-- | 0 |
| 0 | 3 | 1 + 5 = 6 | +3, i++ | 3 |
| 1 | 3 | 2 + 5 = 7 | +2, i++ | 5 |
| 2 | 3 | 4 + 5 = 9 | j-- | 5 |
| 2 | 2 | wskaźniki się spotkały — koniec | ||
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> a = {4, 1, 1, 4};
int n = a.size();
bool pal = true;
for (int i = 0; i < n / 2; i++) {
if (a[i] != a[n - 1 - i]) pal = false;
}
cout << pal;
Pokaż odpowiedź
vector<int> a = {1, 2, 3, 4, 2, 5};
int n = a.size(), z = 0;
for (int i = 0; i < n / 2; i++) {
if (a[i] != a[n - 1 - i]) z++;
}
cout << z;
Pokaż odpowiedź
vector<int> a = {7, 8, 9};
vector<int> r = a;
reverse(r.begin(), r.end());
cout << r[0] << (r == a);
Pokaż odpowiedź
vector<int> a = {3, 5, 5, 3, 1};
int l = 1, r = 2, ile = 0;
while (l >= 0 && r < 5 && a[l] == a[r]) {
ile++;
l--;
r++;
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {2, 2, 3, 3, 4, 5};
vector<int> ile(10, 0);
for (auto x : a) ile[x]++;
int np = 0;
for (int w = 0; w < 10; w++) {
if (ile[w] % 2 == 1) np++;
}
cout << np;
Pokaż odpowiedź
vector<int> a = {1, 3, 4, 6, 9};
int i = 0, j = 4, S = 10;
while (i < j && a[i] + a[j] != S) {
if (a[i] + a[j] < S) i++;
else j--;
}
cout << a[i] << " " << a[j];
Pokaż odpowiedź
vector<int> a = {1, 3, 4, 6, 9};
int i = 0, j = 4, S = 7;
while (i < j && a[i] + a[j] != S) {
if (a[i] + a[j] < S) i++;
else j--;
}
cout << a[i] << " " << a[j];
Pokaż odpowiedź
string s = "abccba";
string t = s;
reverse(t.begin(), t.end());
cout << (s == t) << t.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ę.
Baza zadań: vector w praktyce
Znasz już wszystko, co potrzebne: tworzenie vectora i size(), push_back, pop_back i back(), pętlę „dla każdego” z & i bez, vector jako całość, iteratory z erase, insert, sort, reverse, count i find, vector 2D i grupy, a do tego pojęcia olimpijskie: podtablicę, prefiks i sufiks, podzbiór, permutację i palindrom. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie, w których łączysz dwa, trzy pomysły, a na końcu trudne — z wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak modulo, napisy czy pary. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:
Ściąga: gotowe schematy z vectorem
Tworzenie i wczytywanie
vector<int> v; // pusty
vector<int> v = {1, 2}; // te elementy
vector<int> v(n, x); // n razy x
vector<int> v(n); // n zer
for (auto &x : v) cin >> x;
Najpierw cin >> n, potem vector. (5, 0) to pięć zer, {5, 0} to dwa elementy.
Rośnie i maleje
v.push_back(x); v.pop_back(); v.back() v.front() v.size() if (!v.empty()) ... while (cin >> x) v.push_back(x);
Przed back() i pop_back() sprawdź, czy vector nie jest pusty.
For-each i całość
for (auto x : v) // kopia — czytasz for (auto &x : v) // oryginał — zmieniasz b = a; a == b; a < b; nowy = v; ... v = nowy;
Vectory kopiują się, porównują i zamieniają (swap) jak napisy.
Iteratory i polecenia
v.begin() + k // pudełko k v.end() // ZA ostatnim v.erase(v.begin() + k); v.insert(v.begin() + k, x); sort / reverse / count / find
Zakres [od, do) — drugiej strzałki nie wliczamy. Kawałek a..b: v.begin() + a, v.begin() + b + 1.
Vector 2D i grupy
vector<vector<int>> m(n, vector<int>(k)); m[w][c] m.size() m[w].size() vector<vector<int>> g(k + 1); g[nr].push_back(x);
Wiersze mogą mieć różną długość. Plansza znaków: vector<string>.
Podtablice, prefiksy, sufiksy
for (i) { s = 0;
for (j = i; j < n; j++) s += a[j]; }
p[i + 1] = p[i] + a[i];
suma(I, J) = p[J + 1] - p[I];
okno: s += a[i] - a[i - k];
Podtablic jest n(n+1)/2. Prefiks to (0, J), sufiks to (I, n − 1).
Podzbiory i permutacje
for (maska = 0; maska < 2^n; maska++)
m % 2 == 1 → bierzemy a[i]; m /= 2;
sort(v.begin(), v.end());
do { ... } while (next_permutation(
v.begin(), v.end()));
Podzbiorów 2n (n ≤ 20), permutacji n! (n ≤ 10). Permutacja 1..n: liczniki.
Palindromy i dwa wskaźniki
a[i] == a[n - 1 - i] // lustro l--, r++ od środka i = 0, j = n - 1; while (i < j) ... i++ albo j--
Przestawić w palindrom: najwyżej jedna wartość nieparzyście wiele razy.
vector<int> v(n), jeśli nie, pusty vector i push_back. 2) Rozpoznaj pojęcie z treści: kawałek bez przerw to podtablica, dowolny wybór to podzbiór, wszystkie ustawienia to permutacje, „tak samo od tyłu” to palindrom. 3) Oszacuj, ile jest możliwości: n(n+1)/2 podtablic, 2n podzbiorów, n! permutacji — i porównaj z ograniczeniami. 4) Gdy zmieniasz elementy w pętli „dla każdego” — pamiętaj o &. 5) Przetestuj skrajności: jeden element, wszystkie elementy równe, pusty wynik, liczby ujemne.
Rozgrzewka · zadania 1–10
Jeden pomysł naraz: parzyste czy nieparzyste, pierwszy i ostatni po obrotach, szczyty i doliny, przesunięcie w kółko, zera na koniec, bez powtórzeń, lista zakupów, bilans konta, następne ustawienie i kolejka do lekarza.
Średnie · zadania 11–20
Kilka sztuczek naraz: wyliczanka, scalanie list, wspólne elementy, wycieczka z budżetem, prawie palindrom, obrót w palindrom, drużyna marzeń, tasowanie kart, sumy prostokątów i najdłuższy palindromiczny podzbiór.
Trudne · zadania 21–28
Sumy podzielne przez k, grupy anagramów, najmniej zamian, k-ta permutacja, najdłuższy rosnący podzbiór, wyspy, sklejane palindromy — a na koniec wielki finał: edytor ciągu.