C++ · Etap 2 · Lekcja 10

Vector — tablica, która sama rośnie

Zwykła tablica ma stały rozmiar: musisz z góry zgadnąć, ile pudełek zrobić, i osobno pamiętać, ile z nich zająłeś. Vector to tablica bez tych kłopotów — sam pamięta swoją długość, rośnie, gdy dokładasz elementy, i maleje, gdy je zabierasz. Poznasz tworzenie vectora, metody push_back i pop_back, pętlę for-each z referencją &, iteratory begin() i end(), gotowe polecenia sort, reverse, erase i insert oraz vector 2D. Potem nauczysz się pojęć, bez których nie ma olimpiady: podtablica, prefiks, sufiks, podzbiór, permutacja i palindrom. Po każdej części czekają ćwiczenia ze sprawdzarką.

67 ćwiczeń w trakcie lekcji28 zadań w bazie na koniec95 ze sprawdzarką C++
Filmy z OKI

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ć.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

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.

CZĘŚĆ 01–02

Pierwszy vector, rośnie i maleje

Tworzenie, [ ] i size(), a potem push_back, pop_back, back() i wczytywanie do końca danych.

CZĘŚĆ 03–04

For-each i iteratory

Pętla „dla każdego” z & i bez, vector jako całość, begin() i end(), erase, insert, sort, reverse.

CZĘŚĆ 05–06

Vector 2D i podtablice

Tabele i grupy, a potem podtablica, prefiks i sufiks — z sumami prefiksowymi i oknem.

CZĘŚĆ 07–08

Podzbiory, permutacje, palindromy

Wszystkie wybory „bierzemy albo nie”, wszystkie ustawienia, ciągi czytane tak samo w obie strony i dwa wskaźniki.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczby:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc wypisywanie vectora pętlą z 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.

tablica.cpp
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";
▶ Wejście
4 3 8 -1 5
▶ Wyjście
5 -1 8 3
vector.cpp
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";
▶ Wejście
4 3 8 -1 5
▶ Wyjście
5 -1 8 3

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)
rozmiarstały, ustalony na początku — trzeba zgadywać z zapasemdokładnie taki, jak trzeba; może rosnąć i maleć
ile elementów?trzeba pamiętać osobno w zmiennej nmówi sam: v.size()
dopisanie na koniecnie da sięv.push_back(5); (część 2)
odczyt i zmianat[2], t[2] = 7;tak samo: v[2], v[2] = 7;
indeksyod 0 do n − 1tak samo: od 0 do v.size() - 1
wypisanie jednym coutnieteż 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

szablon.cpp
#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;
}
▶ Wyjście
4 5 5

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.

vector<int> v = {5, 7, -1, 5}; — cztery pudełka z numerami od 0 do 3. v.size() to 4, v[0] to 5, a v[3] to też 5.

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ł:

cztery_sposoby.cpp
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";
▶ Wyjście
0 3 5 3 8 7 0
zapisco robisize()
vector<int> a;pusty vector0
= {4, 8, 15}dokładnie te elementy, po kolei3
(5, 7)ile razy, co: pięć siódemek5
(3)ile razy — same zera3
vector<int> c(5, 7); — w nawiasach okrągłych najpierw ILE, potem CO. vector<int> d(3); — samo ILE, a w pudełkach zera.
Nawiasy okrągłe a klamry — dwa zupełnie różne vectory 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ę.
nawiasy.cpp
vector<int> a(5, 0);
vector<int> b = {5, 0};
cout << a.size() << " " << b.size() << "\n";
cout << b[0] << " " << b[1] << "\n";
▶ Wyjście
5 2 5 0

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.

lawki.cpp
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";
▶ Wyjście
C B na lawce 9 siedzi K ..L.Z.B..K..

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.

ostatni.cpp
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";
▶ Wyjście
5 -5 5 100
v.size() = 5, więc ostatni element to v[5 - 1] = v[4] = -5 (niebieski), a środkowy to v[5 / 2] = v[2] = 5 (pomarańczowy).
Poza vectorem jest tak samo groźnie jak poza tablicą Vector o 5 elementach ma indeksy 0, 1, 2, 3, 4. 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].
v[5] nie istnieje — vector kończy się na pudełku 4.

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.

wczytaj.cpp
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";
▶ Wejście
5 1 3 -2 7 0
▶ Wyjście
suma 9, pierwsza 1, ostatnia 0
vector<int> v(5); daje pięć zer. Pętla wpisuje do każdego pudełka liczbę z wejścia.

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.

cout_vector.cpp
vector<int> v = {1, 2, 5};
cout << v << "\n";      // BŁĄD: cout nie umie wypisać vectora
▶ Kompilator
error: no match for 'operator<<' (operand types are 'std::ostream' and 'std::vector<int>')
wypisz.cpp
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";
}
▶ Wyjście
1 2 5 0: 1 1: 2 2: 5

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.

typy.cpp
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";
▶ Wyjście
kota 3 5 ** 1 5
vector<pair<int, int>> pkt — każde pudełko to cała para; pkt[1].second to 5.

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.

slad.cpp
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";
▶ Wyjście
18 3 9 27
po linijcev[0]v[1]v[2]v[3]
v(4, 1)1111
i = 11311
i = 21391
i = 313927
v[0] = v[3] - v[2]183927
Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
vector<int> v(3, 4);
cout << v.size() << v[2];
Pokaż odpowiedź
34Nawiasy okrągłe: 3 razy liczba 4. Rozmiar 3, a w pudełku 2 leży 4 — bez spacji wychodzi „34”.
Co wypisze ten fragment?
vector<int> v = {3, 4};
cout << v.size() << " " << v[0];
Pokaż odpowiedź
2 3Klamry: dokładnie dwa elementy, 3 i 4. Rozmiar 2, pierwszy element 3.
Co wypisze ten fragment?
vector<int> v(4);
v[1] = 6;
cout << v[0] + v[1] + v[3];
Pokaż odpowiedź
6vector<int> v(4) to cztery zera. Zmieniamy tylko v[1], więc suma to 0 + 6 + 0 = 6.
Ostatni element. Co wypisze ten fragment?
vector<int> v = {9, 8, 7, 6, 5};
cout << v[v.size() - 1] << v[v.size() - 2];
Pokaż odpowiedź
56Rozmiar to 5, więc v[4] to 5, a v[3] to 6.
Co wypisze ten fragment?
vector<string> s = {"kot", "pies", "mysz"};
cout << s[1][0] << s[2].size() << s.size();
Pokaż odpowiedź
p43s[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).
Co wypisze ten fragment?
vector<int> v = {2, 4, 6, 8};
for (int i = 0; i < v.size(); i += 2) {
    cout << v[i];
}
Pokaż odpowiedź
26Pętla bierze indeksy 0 i 2 (potem i = 4 nie spełnia warunku i < 4): v[0] = 2, v[2] = 6.
Co wypisze ten fragment?
vector<char> z(3, 'a');
z[1] = 'b';
for (int i = 0; i < z.size(); i++) {
    cout << z[i];
}
Pokaż odpowiedź
abaTrzy litery a, potem środkowa zmienia się na b.
Co wypisze program dla wejścia z trzema liczbami 10, 20, 30?
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
    cin >> v[i];
}
cout << v[n - 1] - v[0];
Wejście: 3 10 20 30
Pokaż odpowiedź
20Ostatni element to 30, pierwszy to 10: 30 − 10 = 20.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

1.1 Od końcałatwe✓ zaliczone Wczytaj n liczb do vectora i wypisz je w odwrotnej kolejności. vector<int> v(n)cin >> v[i]pętla od końca Rozwiąż 1.2 Pierwszy, środkowy, ostatniłatwe✓ zaliczone Vector ma nieparzystą liczbę elementów. Wypisz pierwszy, środkowy i ostatni z nich. v[0]v[v.size() / 2]v[v.size() - 1] Rozwiąż 1.3 Pytania o miejscałatwe✓ zaliczone W kolejce stoi n osób z numerkami. Odpowiedz na pytania: jaki numerek ma osoba na miejscu p? indeks od 1 → od 0v[p - 1]zapytania Rozwiąż 1.4 Poprawki w liściełatwe✓ zaliczone Lista liczb dostaje kolejne poprawki „na miejscu p wpisz x”. Wypisz listę po wszystkich poprawkach. v[p - 1] = xzmiana elementuwypisywanie pętlą Rozwiąż 1.5 Cieplej czy zimniej?łatwe✓ zaliczone Temperatury z kolejnych dni: ile razy było cieplej niż dzień wcześniej, ile zimniej, a ile tak samo? v[i] i v[i - 1]porównanie sąsiadówtrzy liczniki Rozwiąż 1.6 Najdłuższe słowołatwe✓ zaliczone vector napisów: znajdź najdłuższe słowo, a potem wypisz wszystkie słowa od końca. vector<string>s[i].size()od końca Rozwiąż 1.7 Ławki w parkułatwe✓ zaliczone Rząd n pustych ławek i k osób, które na nich siadają. Narysuj park i policz wolne ławki. vector<char> v(n, '.')v[p] = literawypisz jak napis Rozwiąż 1.8 Powyżej średniejśrednie✓ zaliczone Policz średnią z n liczb i wypisz te liczby, które są od niej większe. dwa przejścia po vectorzefixed i setprecisiondouble Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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”.

push_back.cpp
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";
▶ Wyjście
4 5 7 -1 5
linijkav po tej linijcesize()
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
Każdy push_back dokłada jedno pudełko na sam koniec (zielone). Pudełka, które już były, nie ruszają się z miejsca.

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:

kwadraty.cpp
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";
▶ Wyjście
1 4 9 16 25
wczytaj_push.cpp
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";
▶ Wejście
3 4 1 9
▶ Wyjście
3 4

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.

Pusty vector nie ma pudełka numer 0 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ś.

parzyste.cpp
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";
▶ Wejście
7 4 7 10 -3 0 5 8
▶ Wyjście
parzystych 4: 4 10 0 8 nieparzystych 3: 7 -3 5

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.

do_konca.cpp
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";
▶ Wejście
3 1 4 1 5 9
▶ Wyjście
wczytano 6 liczb 9 5 1 4 1 3

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.

pop_back.cpp
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";
▶ Wyjście
4 16 15 3 4 8 42
zapisto samo co
v.front()v[0]
v.back()v[v.size() - 1]
v.pop_back();usuń ostatni element
pop_back zabiera ostatnie pudełko. Nowym ostatnim (back) staje się 15.

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”.

cofnij.cpp
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";
▶ Wejście
Ala ma psa COFNIJ COFNIJ COFNIJ COFNIJ ma kota
▶ Wyjście
ma kota

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”.

Pułapka: size() - 1 w pustym vectorze 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.

cyfry.cpp
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";
▶ Wejście
90417
▶ Wyjście
cyfr: 5 9 0 4 1 7
Cyfry liczby 90417 w kolejności wyciągania: c[0] to jedności (7), c[4] to dziesiątki tysięcy (9).

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.

resize.cpp
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";
▶ Wyjście
13 8 0 0 1 2 8 -6 0 1
resize dokłada zera na końcu albo obcina koniec. assign zaczyna od nowa. clear zostawia pusty vector.

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]++.

Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
vector<int> v;
v.push_back(3);
v.push_back(9);
cout << v.size() << v[1];
Pokaż odpowiedź
29Dwa push_back, więc rozmiar 2. Drugi element (indeks 1) to 9.
Co wypisze ten fragment?
vector<int> v(2);
v.push_back(5);
cout << v.size() << v[0] << v[2];
Pokaż odpowiedź
305v(2) to już dwa zera. push_back dokłada trzecie pudełko z 5: vector {0, 0, 5}.
Co wypisze ten fragment?
vector<int> v = {1, 2, 3};
v.pop_back();
v.push_back(7);
cout << v.back() << v.size();
Pokaż odpowiedź
73pop_back zabiera 3, push_back dokłada 7: {1, 2, 7}. Ostatni to 7, rozmiar 3.
Co wypisze ten fragment?
vector<int> v;
for (int i = 10; i >= 1; i -= 3) {
    v.push_back(i);
}
cout << v.size() << " " << v.back();
Pokaż odpowiedź
4 1Pętla dokłada 10, 7, 4 i 1 — cztery liczby. Ostatnia to 1.
Co wypisze ten fragment?
vector<int> v = {5, 6};
v.resize(4);
cout << v.size() << v[3] << v.front();
Pokaż odpowiedź
405resize(4) dokłada dwa zera: {5, 6, 0, 0}. Rozmiar 4, v[3] = 0, pierwszy element 5.
Co wypisze ten fragment?
vector<int> v = {1, 2, 3, 4};
v.clear();
v.push_back(8);
cout << v.size() << v[0] << v.empty();
Pokaż odpowiedź
180Po clear vector jest pusty, potem dostaje 8. Rozmiar 1, element 8, a empty() to fałsz, czyli 0.
Co wypisze ten fragment?
vector<int> v;
int n = 345;
while (n > 0) {
    v.push_back(n % 10);
    n /= 10;
}
cout << v[0] << v.back();
Pokaż odpowiedź
53Cyfry trafiają od końca: {5, 4, 3}. Pierwsze pudełko to 5, ostatnie to 3.
Co wypisze program dla wejścia 2 4 6 8?
vector<int> v;
int x;
while (cin >> x) {
    if (x > 3) v.push_back(x / 2);
}
cout << v.size() << v.front() << v.back();
Wejście: 2 4 6 8
Pokaż odpowiedź
324Liczby większe od 3 to 4, 6 i 8 — trafiają połówki: {2, 3, 4}. Rozmiar 3, pierwszy 2, ostatni 4.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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!

for_each.cpp
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";
▶ Wyjście
1 2 5 3 -5 6
obrótxsuma po obrocie
111
223
358
4311
5-56

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ę.

auto.cpp
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";
▶ Wyjście
6 2 5 aa-bb-cc-

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ć:

bez_ampersandu.cpp
vector<int> v = {1, 2, 3};
for (int x : v) {
    x = x * 2;                 // zmienia tylko kopię!
}
for (int x : v) {
    cout << x << " ";
}
cout << "\n";
▶ Wyjście — nic się nie zmieniło
1 2 3
z_ampersandem.cpp
vector<int> v = {1, 2, 3};
for (int &x : v) {
    x = x * 2;                 // zmienia element vectora
}
for (int x : v) {
    cout << x << " ";
}
cout << "\n";
▶ Wyjście
2 4 6

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.

Bez & pętla dostaje kopię wartości (zmiana nie wraca do vectora). Z & pętla dostaje samo pudełko — tu właśnie podwaja v[1] z 2 na 4.
for (int x : v)for (int &x : v)
czym jest xkopią elementutym samym elementem (referencją)
zmiana x zmienia vector?nietak
kiedy używaćgdy tylko czytasz: liczysz, wypisujesz, szukaszgdy 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.

wczytaj_ampersand.cpp
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";
▶ Wejście
5 1 3 -2 7 0
▶ Wyjście
7
Bez & vector zostaje pełen zer 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.

slowa_ampersand.cpp
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";
▶ Wyjście
Ala! Ma! Kota!
pary_ampersand.cpp
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";
}
▶ Wyjście
Ola 95 Jan 80 Ewa 87

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};.

kopia.cpp
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";
▶ Wyjście
1 100 0 1 4 3 2 7

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.

porownanie.cpp
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";
▶ Wyjście
1 1 0
porównanieco decydujewynik
{1, 2, 9} < {1, 3}pozycja 1: 2 < 3prawda
{1, 2} < {1, 2, 9}krótszy jest początkiem dłuższegoprawda
{1, 3} < {1, 2}pozycja 1: 3 > 2fał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.

runda.cpp
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";
}
▶ Wyjście
0 1 0 1 0 1 0 2 0 1 0 3 0 3 0

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.

Nie zmieniaj rozmiaru w pętli „dla każdego” W pętli 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.
Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
vector<int> v = {4, 1, 3};
for (int x : v) {
    cout << x * 2;
}
Pokaż odpowiedź
826Pętla bierze kolejne wartości 4, 1, 3 i wypisuje ich podwojenia bez spacji.
Co wypisze ten fragment?
vector<int> v = {4, 1, 3};
for (int x : v) {
    x = 0;
}
cout << v[0] + v[1] + v[2];
Pokaż odpowiedź
8Bez & zerujemy tylko kopie. Vector się nie zmienia: 4 + 1 + 3 = 8.
Co wypisze ten fragment?
vector<int> v = {4, 1, 3};
for (int &x : v) {
    x = x + 10;
}
cout << v[0] << v[2];
Pokaż odpowiedź
1413Z & zmieniamy prawdziwe elementy: {14, 11, 13}. Wypisujemy 14 i 13 bez spacji.
Co wypisze ten fragment?
vector<int> v = {5, 2, 8, 1};
int ile = 0;
for (auto x : v) {
    if (x > 3) ile++;
}
cout << ile;
Pokaż odpowiedź
2Większe od 3 są tylko 5 i 8.
Kopia. Co wypisze ten fragment?
vector<int> a = {1, 2};
vector<int> b = a;
b.push_back(3);
cout << a.size() << b.size();
Pokaż odpowiedź
23b to osobna kopia — dokładanie do niej nie zmienia a.
Co wypisze ten fragment?
vector<int> a = {2, 5}, b = {2, 4, 9};
cout << (a < b) << (a == b) << (b < a);
Pokaż odpowiedź
001Pierwsze elementy równe (2), drugie: 5 > 4. Więc b jest mniejszy: a < b to 0, a == b to 0, b < a to 1.
Co wypisze ten fragment?
vector<string> s = {"ab", "c"};
for (auto &w : s) {
    w = w + w;
}
cout << s[0] << s[1];
Pokaż odpowiedź
ababccZ & każde słowo zostaje podwojone w vectorze: „abab” i „cc”.
Co wypisze ten fragment?
vector<pair<int, int>> v = {{1, 2}, {3, 4}};
int s = 0;
for (auto [a, b] : v) {
    s += a * b;
}
cout << s;
Pokaż odpowiedź
141 · 2 + 3 · 4 = 2 + 12 = 14.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

3.1 Pomnóż wszystkołatwe✓ zaliczone Wczytaj vector pętlą for-each z &, pomnóż każdy element przez k i wypisz. for (auto &x : v) cin >> xx *= kfor (auto x : v) Rozwiąż 3.2 Przytnij do przedziałułatwe✓ zaliczone Każdą liczbę spoza przedziału [lo, hi] przesuń na najbliższy koniec. Ile liczb się zmieniło? for (auto &x : v)zmiana przez referencjęlicznik Rozwiąż 3.3 Suma, minimum, maksimumłatwe✓ zaliczone Jedna pętla „dla każdego”: suma, najmniejsza i największa liczba oraz ile razy wystąpiło maksimum. for (auto x : v)long longmin i max Rozwiąż 3.4 Wielka litera na początkułatwe✓ zaliczone vector napisów i pętla for (auto &s : slowa): każde słowo zaczyna się od wielkiej litery. vector<string>for (auto &s : v)toupper Rozwiąż 3.5 Punkty w ćwiartkachłatwe✓ zaliczone vector par (x, y) i rozpakowywanie w pętli: ile punktów leży w każdej ćwiartce układu? vector<pair<int, int>>for (auto [x, y] : p)pięć liczników Rozwiąż 3.6 Który ciąg pierwszy?średnie✓ zaliczone Porównaj dwa ciągi liczb jak słowa w słowniku. vectory porównują się same: a < b. a < b na vectoracha == bkolejność słownikowa Rozwiąż 3.7 Wygładzanieśrednie✓ zaliczone k rund: każda liczba staje się średnią swoją i sąsiadów. Nową rundę licz na kopii! vector nowy = vv = nowybrzegi Rozwiąż 3.8 Powrót do początkuśrednie✓ zaliczone Obracaj vector w lewo o k miejsc, aż znowu będzie taki jak na początku. Ile obrotów? kopia start = vporównanie v == startobrót przez nowy vector Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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ć.

Trzy różne rzeczy: indeks to 2 (numer pudełka), iterator to strzałka pokazująca to pudełko, a wartość to 15 (to, co leży w pudełku).

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).

begin.cpp
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";
▶ Wyjście
4 8 16 100 8
*it = 100 zmienia pudełko, na które pokazuje strzałka — tak jak referencja & z części 3.
Strzałka na pudełko numer k 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.
cout_iterator.cpp
vector<int> v = {4, 8, 15};
auto it = v.begin();
cout << it << "\n";            // BŁĄD: to strzałka, nie liczba
▶ Kompilator
error: no match for 'operator<<'

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()].

end() stoi za ostatnim pudełkiem, na miejscu numer 5, gdzie nic nie ma. Ostatni element (23) to end() - 1.

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() do end() jest dokładnie tyle kroków, ile elementów: v.end() - v.begin() to v.size();
  • w pustym vectorze begin() i end() 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).
petla_iterator.cpp
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";
▶ Wyjście
4 8 15 16 23 23 5

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).

erase.cpp
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";
▶ Wyjście
1 2 4 5 6 1 5 6 5
erase(v.begin() + 1, v.begin() + 3) usuwa pomarańczowe pudełka 1 i 2. Pudełko 3, na które pokazuje druga strzałka, zostaje.
Po erase numery się przesuwają Po usunięciu elementu wszystko za nim dostaje numer o 1 mniejszy. Jeśli usuwasz po kolei 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.

insert.cpp
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";
▶ Wyjście
7 1 9 2 3 5 8
Zielone pudełko to element właśnie wstawiony. Ostatnia linijka programu dokleja na koniec cały vector b — insert może też dostać dwie strzałki na kawałek innego vectora.

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:

polecenieco robiprzykł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 22
*max_element(v.begin(), v.end())największy element9
*min_element(v.begin(), v.end())najmniejszy element2
max_element(v.begin(), v.end()) - v.begin()numer pierwszego największego2
find(v.begin(), v.end(), 9) - v.begin()numer pierwszego wystąpienia 92
algorytmy.cpp
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";
▶ Wyjście
2 9 2 7 2 9 2 5 2 2 5 7 9 9 7 5 2 2

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.

kawalek.cpp
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";
▶ Wyjście
2 5 9 1 7 3 2 5 7 1 9 3
Niebieskie: posortowane trzy pierwsze. Pomarańczowe: odwrócony kawałek od numeru 2 do 4 — druga strzałka stoi na numerze 5, którego nie bierzemy.

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().

find.cpp
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";
    }
}
▶ Wyjście
15: numer 2 42: nie ma 4: numer 0

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:

erase_petla_zle.cpp
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";
▶ Wyjście — jedna dwójka została
1 2 3
nowy_vector.cpp
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";
▶ Wyjście
1 3

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.

Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
vector<int> v = {3, 6, 9, 12};
cout << *(v.begin() + 2) << " " << *(v.end() - 1);
Pokaż odpowiedź
9 12begin() + 2 pokazuje numer 2 (9), a end() - 1 — ostatni element (12).
Co wypisze ten fragment?
vector<int> v = {3, 6, 9, 12};
cout << v.end() - v.begin();
Pokaż odpowiedź
4Od begin() do end() jest tyle kroków, ile elementów.
Co wypisze ten fragment?
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ź
145Pierwszy erase usuwa 2: {1, 3, 4, 5}. Teraz pod numerem 1 stoi 3 — drugi erase usuwa właśnie ją.
Co wypisze ten fragment?
vector<int> v = {1, 2, 3};
v.insert(v.begin() + 2, 8);
for (auto x : v) cout << x;
Pokaż odpowiedź
12838 staje się elementem numer 2, a 3 przesuwa się w prawo.
Co wypisze ten fragment?
vector<int> v = {4, 1, 4, 2, 4};
cout << count(v.begin(), v.end(), 4) << *min_element(v.begin(), v.end());
Pokaż odpowiedź
31Czwórki są trzy, a najmniejszy element to 1.
Co wypisze ten fragment?
vector<int> v = {6, 2, 9, 9, 1};
cout << max_element(v.begin(), v.end()) - v.begin();
Pokaż odpowiedź
2Największe są dwie dziewiątki; strzałka pokazuje pierwszą z nich — numer 2.
Co wypisze ten fragment?
vector<int> v = {5, 4, 3, 2, 1};
sort(v.begin() + 1, v.begin() + 4);
for (auto x : v) cout << x;
Pokaż odpowiedź
52341Sortujemy tylko numery 1, 2, 3 (elementy 4, 3, 2). Pudełka 0 i 4 zostają na miejscu.
Co wypisze ten fragment?
vector<int> v = {7, 3, 5};
auto it = find(v.begin(), v.end(), 4);
cout << (it == v.end()) << " " << it - v.begin();
Pokaż odpowiedź
1 34 nie ma w vectorze, więc find zwraca end(). Odległość od begin() to rozmiar vectora: 3.
Ćwiczenia · teraz Ty

9 ćwiczeń do tej części

0 / 9 zaliczonych

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ę.

4.1 Usuń jeden elementłatwe✓ zaliczone Usuń z vectora element stojący na miejscu p. Przyda się v.erase(v.begin() + …). erasev.begin() + kmiejsca od 1 Rozwiąż 4.2 Wstaw elementłatwe✓ zaliczone Wstaw liczbę x tak, żeby stała na miejscu p. Przyda się v.insert(v.begin() + …, x). insertv.begin() + kv.end() to koniec Rozwiąż 4.3 Najmniejsza, środkowa, największałatwe✓ zaliczone Posortuj vector przez sort(v.begin(), v.end()) i odczytaj minimum, medianę i maksimum. sort(v.begin(), v.end())medianav.front() i v.back() Rozwiąż 4.4 Gdzie jest maksimum?łatwe✓ zaliczone max_element, min_element i count: wartość, pierwsze miejsce i liczba wystąpień. *max_elementmax_element(…) - v.begin()count Rozwiąż 4.5 Szukaniełatwe✓ zaliczone Dla każdego zapytania: na którym miejscu pierwszy raz stoi x i ile razy występuje? find i count. findit == v.end()count Rozwiąż 4.6 Podiumłatwe✓ zaliczone Wypisz k największych wyników od najlepszego. sort, a potem reverse — albo pętla od końca. sortreversek pierwszych Rozwiąż 4.7 Odwracanie kawałkówśrednie✓ zaliczone q razy odwróć kawałek ciągu od miejsca a do miejsca b. Uważaj na drugą strzałkę: + 1! reverse na kawałkuv.begin() + a - 1[od, do) Rozwiąż 4.8 Usuń wszystkie xśrednie✓ zaliczone Usuń z ciągu wszystkie wystąpienia liczby x. Pułapka: erase w pętli przeskakuje sąsiada! nowy vector z elementów, które zostająerase w pętli — pułapkacount Rozwiąż 4.9 Edytor ciąguśrednie✓ zaliczone Polecenia WSTAW p x, USUN p i WYPISZ na żywym vectorze. insert i erase w praktyce. inserterasepolecenia tekstowe Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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].

dwa_wymiary.cpp
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";
}
▶ Wyjście
2 3 6 1 20 3 4 5 6
zapistypco to jest
mvector<vector<int>>cała tabela
m[1]vector<int>wiersz {4, 5, 6}
m[1][2]intliczba 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”.

vector<vector<int>> m(3, vector<int>(2, 0)); — 3 wiersze, w każdym 2 zera. Najpierw wiersze, potem kolumny.
tabela.cpp
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";
}
▶ Wejście
2 3 1 2 3 10 20 30
▶ Wyjście
wiersz 0: 6 wiersz 1: 60

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.

for_each_2d.cpp
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";
▶ Wejście
3 2 4 -1 7 2 0 5
▶ Wyjście
7

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ą.

pascal.cpp
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";
}
▶ Wyjście
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Wiersz 4 ma 5 liczb, a wiersz 0 tylko jedną. t[4][2] = t[3][1] + t[3][2] = 3 + 3 = 6.

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.

grupy.cpp
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";
}
▶ Wejście
5 3 Ola 2 Jan 1 Ewa 2 Igor 2 Ida 1
▶ Wyjście
klasa 1 (2): Jan Ida klasa 2 (3): Ola Ewa Igor klasa 3 (0):
Szuflada 0 nie jest używana, szuflada 3 jest pusta. W każdej szufladzie imiona są w kolejności z wejścia, bo push_back dokłada na koniec.

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.

plansza.cpp
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";
▶ Wejście
3 4 ..#. .##. ....
▶ Wyjście
3 S.#. .##. ....
p[1][2] to znak w wierszu 1 i kolumnie 2: '#'. Wiersz planszy wypisujesz w całości jednym cout, bo to zwykły napis.
Najpierw wiersz, potem kolumna 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().
Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
vector<vector<int>> m(2, vector<int>(4, 1));
cout << m.size() << m[0].size() << m[1][3];
Pokaż odpowiedź
2412 wiersze, w każdym 4 jedynki.
Co wypisze ten fragment?
vector<vector<int>> m = {{5, 6}, {7, 8}, {9, 0}};
cout << m[2][0] + m[0][1];
Pokaż odpowiedź
15m[2][0] to 9 (wiersz 2, kolumna 0), a m[0][1] to 6.
Co wypisze ten fragment?
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ź
021Trzy puste wiersze; do wiersza 1 trafiają dwie liczby, do wiersza 2 jedna.
Co wypisze ten fragment?
vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}};
int s = 0;
for (auto w : m) s += w[0];
cout << s;
Pokaż odpowiedź
5Pętla bierze całe wiersze; w[0] to pierwsza liczba wiersza: 1 + 4.
Co wypisze ten fragment?
vector<string> p = {"ab", "cd", "ef"};
cout << p[2][1] << p[0][0] << p.size();
Pokaż odpowiedź
fa3p[2][1] to druga litera trzeciego napisu („f”), p[0][0] to „a”, a napisów są 3.
Co wypisze ten fragment?
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ź
0373m[1] = m[0] kopiuje cały wiersz {0, 3}. Potem zmieniamy tylko wiersz 1: {7, 3}. Wiersz 0 zostaje {0, 3}.
Co wypisze ten fragment?
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ź
230W szufladzie 1 są 2 i 3, szuflada 2 jest pusta.
Co wypisze ten fragment?
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ź
373Z & dokładamy do prawdziwych wierszy: {1, 2, 3} i {3, 4, 7}. Każdy ma teraz 3 liczby.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

5.1 Wiersze na kolumnyłatwe✓ zaliczone Tabela n × m zamienia się w tabelę m × n: pierwszy wiersz staje się pierwszą kolumną. vector<vector<int>>m[w][k]pętla w pętli Rozwiąż 5.2 Sumy wierszy i kolumnłatwe✓ zaliczone Policz sumę każdego wiersza i każdej kolumny tabeli. vector 2Dsumy wierszysumy kolumn Rozwiąż 5.3 Trójkąt Pascalałatwe✓ zaliczone Zbuduj n wierszy trójkąta Pascala — każdy wiersz o jeden dłuższy od poprzedniego. wiersze różnej długościt[i].push_backt[i - 1][j - 1] + t[i - 1][j] Rozwiąż 5.4 Paragonyłatwe✓ zaliczone Każdy klient kupił inną liczbę rzeczy. Zapamiętaj paragony i wypisz je od ostatniego klienta, ceny od najdroższej. wiersze różnej długościsort na wierszupusty wiersz Rozwiąż 5.5 Listy klasśrednie✓ zaliczone Rozdziel uczniów do szuflad według numeru klasy i wypisz listę każdej klasy. vector<vector<string>> g(k + 1)g[nr].push_backgrupy Rozwiąż 5.6 Saperśrednie✓ zaliczone Plansza z minami jako vector napisów. W każde wolne pole wpisz, ile min jest dookoła. vector<string>osiem sąsiadówbrzegi planszy Rozwiąż 5.7 Obrót o 90 stopniśrednie✓ zaliczone Obróć tabelę n × m o 90 stopni w prawo. Wynik ma m wierszy i n kolumn. vector 2D o nowych wymiarachr[k][n - 1 - w] = t[w][k]rysunek na kartce Rozwiąż 5.8 Kto kogo obserwujeśrednie✓ zaliczone Lista „kogo obserwuje” dla każdej osoby i najpopularniejsza osoba. Pierwsza lista sąsiedztwa! vector<vector<int>> g(n + 1)lista sąsiedztwalicznik obserwujących Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

Podtablica {5, 4, -6}: elementy o numerach 1, 2 i 3 — stoją obok siebie, bez przerwy.
Podtablica {9, 2, 1, 1}: numery od 5 do 8. Też bez przerw.
czy to podtablica a = {1, 5, 4, -6, 15, 9, 2, 1, 1}?odpowiedźdlaczego
{5, 4, -6}TAKnumery 1, 2, 3 stoją obok siebie
{4, 15}NIEpomija −6 — jest przerwa
{9}TAKjeden element też jest podtablicą
cała tablicaTAKod pierwszego do ostatniego
{-6, 4}NIEzła kolejność
{2, 1, 1}TAKnumery 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};.

Początek I = 1, koniec J = 3, długość 3 − 1 + 1 = 3.
podtablica {1, 8, 9}IJdługość
{1}001
{1, 8}012
{1, 8, 9}023
{8}111
{8, 9}122
{9}221

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.

wszystkie_podtablice.cpp
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";
    }
}
▶ Wyjście
1 1 8 1 8 9 8 8 9 9

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.

sumy_podtablic.cpp
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";
▶ Wyjście
7 od 2 do 3
Podtablica o największej sumie to {4, 3} — numery od 2 do 3, suma 7.

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.

Prefiks (0, 2) = {1, 3, 0}. Wszystkie prefiksy tej tablicy: {1}, {1, 3}, {1, 3, 0}, {1, 3, 0, -1} i cała tablica.

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.

Sufiks (2, 4) = {0, -1, 2}. Wszystkie sufiksy: {2}, {-1, 2}, {0, -1, 2}, {3, 0, -1, 2} i cała tablica.
dla a = {5, 4, 9, 1, 3, -5, 2, 1, 1, 7}co to jestpara (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 tablicai 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.

sumy_prefiksowe.cpp
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";
▶ Wejście
5 1 3 0 -1 2
▶ Wyjście
0 1 4 4 3 5 suma od 1 do 3: 2
Suma a[1..3] = 3 + 0 + (−1) = 2 = p[4] − p[1] = 3 − 1. Vector p ma o jedno pudełko więcej niż a: p[0] to suma pustego prefiksu.

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.

liderzy.cpp
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";
▶ Wyjście
17 5 2
Liderzy (zielone): 17 jest większe od całego sufiksu {4, 3, 5, 2}, 5 od {2}, a ostatni element zawsze jest liderem, bo na prawo od niego nic nie ma.

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.

okno.cpp
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";
▶ Wyjście
8 6 10 15 16 najwiecej: 16
Przesunięcie okna z (0, 2) na (1, 3): wychodzi 3 (pomarańczowe), a przy następnym kroku wchodzi 5 (zielone). Suma zmienia się o nowy element minus stary.
Sprawdź się w głowie

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ź”.

Ile podtablic ma tablica o rozmiarze 5? Co wypisze ten fragment?
int n = 5, ile = 0;
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) ile++;
}
cout << ile;
Pokaż odpowiedź
155 + 4 + 3 + 2 + 1 = 15 = 5 · 6 / 2.
Co wypisze ten fragment?
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ź
16 3Podtablica (1, 3) to {7, 1, 8}: suma 16, długość 3.
Co wypisze ten fragment?
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ź
2 7 8 11To sumy kolejnych prefiksów: {2}, {2, 5}, {2, 5, 1} i całej tablicy.
Co wypisze ten fragment?
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ź
3 4 9 11Tym razem sumy sufiksów: {3}, {1, 3}, {5, 1, 3} i cała tablica.
Sumy prefiksowe. Co wypisze ten fragment?
vector<int> p = {0, 3, 8, 8, 10, 16};
cout << p[5] - p[2] << " " << p[3] - p[1];
Pokaż odpowiedź
8 5p[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.
Co wypisze ten fragment?
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ź
3Okna długości 4 zaczynają się na numerach 0, 1 i 2. Ogólnie jest ich n − k + 1.
Co wypisze ten fragment?
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ź
3Liderzy to 9, 6 i 1 — każdy jest większy od wszystkiego na prawo od siebie.
Co wypisze ten fragment?
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ź
3Sumy podtablic: 1, −1, 2, −2, 1, 3. Największa to 3 — sama trójka.
Ćwiczenia · teraz Ty

9 ćwiczeń do tej części

0 / 9 zaliczonych

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ę.

6.1 Wszystkie podtablicełatwe✓ zaliczone Wypisz każdą podtablicę ciągu w osobnym wierszu — według początku, a potem według końca. podtablica (I, J)trzy pętlej zaczyna się od i Rozwiąż 6.2 Prefiksy i sufiksyłatwe✓ zaliczone Wypisz wszystkie prefiksy ciągu, a potem wszystkie sufiksy — za każdym razem od najkrótszego. prefiks (0, J)sufiks (I, n − 1)n prefiksów i n sufiksów Rozwiąż 6.3 Najlepsze k dniłatwe✓ zaliczone Opady z n dni. W których k kolejnych dniach spadło najwięcej deszczu? Okno przesuwane o jeden. okno długości ksuma += a[i] - a[i - k]pierwsze najlepsze Rozwiąż 6.4 Sumy na przedziałachłatwe✓ zaliczone Wiele pytań „ile wynosi suma od a do b?”. Sumy prefiksów odpowiadają na każde jednym odejmowaniem. vector<long long> p(n + 1)p[b] - p[a - 1]prefiksy Rozwiąż 6.5 Liderzyśrednie✓ zaliczone Lider jest większy od wszystkiego na prawo od siebie. Idź od końca i pamiętaj maksimum sufiksu. sufikspętla od końcamaksimum sufiksu Rozwiąż 6.6 Najdłuższy rosnący kawałekśrednie✓ zaliczone Znajdź najdłuższą podtablicę, w której każdy element jest większy od poprzedniego. podtablicabieżąca długośćpoczątek najlepszej Rozwiąż 6.7 Równy podziałśrednie✓ zaliczone Gdzie przeciąć ciąg na prefiks i sufiks o równych sumach? Wypisz wszystkie miejsca cięcia. prefiks i sufikssuma prefiksu = całość − prefikslong long Rozwiąż 6.8 Podtablice o sumie kśrednie✓ zaliczone Ile podtablic ma sumę dokładnie k? Dwie pętle i suma, która rośnie razem z końcem. wszystkie podtablicesuma bez trzeciej pętlin(n+1)/2 Rozwiąż 6.9 Najlepszy kawałekśrednie✓ zaliczone Podtablica o największej sumie — i gdzie się zaczyna oraz kończy. wszystkie podtablicelong longremis: najmniejszy początek Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

Podzbiór {5, -6, 9, 2, 1}: niebieskie elementy bierzemy, szare pomijamy. Są przerwy, ale kolejność zostaje taka jak w tablicy.
czy to podzbiór a = {1, 5, 4, -6, 15, 9, 2, 1, 1}?odpowiedźdlaczego
{1, 15, 1}TAKna przykład numery 0, 4 i 7
{5, 4}TAKi to nawet podtablica
{1, 1, 1}TAKw tablicy są trzy jedynki: 0, 7 i 8
{7}NIEw tablicy nie ma liczby 7
{9, 15}NIE15 stoi przed 9 — kolejność musi zostać
cała tablicaTAKbierzemy 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
nienienie{ } — pusty
taknienie{1}
nietaknie{8}
taktaknie{1, 8}
nienietak{9}
taknietak{1, 9}
nietaktak{8, 9}
taktaktak{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ą.

npodtablice: n(n+1)/2podzbiory niepuste: 2n − 1
10551 023
202101 048 575
30465ponad 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.

czy_podzbior.cpp
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";
▶ Wyjście
TAK
Palec po a zatrzymuje się na 5 (numer 1), −6 (numer 3) i pierwszej jedynce za nimi (numer 7). Dla b = {9, 15} drugi palec utknąłby na 9: po niej nie ma już 15.

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.

maski.cpp
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";
}
▶ Wyjście
0: { } suma 0 1: { 1 } suma 1 2: { 8 } suma 8 3: { 1 8 } suma 9 4: { 9 } suma 9 5: { 1 9 } suma 10 6: { 8 9 } suma 17 7: { 1 8 9 } suma 18
maskadwójkowobierzemy
0000nic
1001a[0]
2010a[1]
3011a[0], a[1]
4100a[2]
5101a[0], a[2]
6110a[1], a[2]
7111wszystko

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 = 3TAK
{1, 2, 2}, n = 3NIE — 2 dwa razy, brak 3
{4, 1, 2}, n = 3NIE — 4 to za dużo
{2, 1, 4, 3}, n = 4TAK
{1}, n = 1TAK

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!.

n3581013
n!612040 3203 628 800ponad 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.

czy_permutacja.cpp
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";
▶ Wejście
4 2 4 1 3
▶ Wyjście
TAK

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.

anagramy.cpp
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";
▶ Wyjście
1 aajkk aajkk 1

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.

next_permutation.cpp
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";
▶ Wyjście
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 razem 6
powtorki.cpp
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";
▶ Wyjście
112 121 211

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.

odwrotna.cpp
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";
}
▶ Wyjście
osoba 1 na miejscu 2 osoba 2 na miejscu 4 osoba 3 na miejscu 1 osoba 4 na miejscu 3
p: na miejscu 1 stoi osoba 3, na miejscu 2 — osoba 1… gdzie: osoba 1 stoi na miejscu 2, osoba 2 — na miejscu 4… Numery pod pudełkami liczymy tu od 1.

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.

Sprawdź się w głowie

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ź”.

Ile podzbiorów (razem z pustym) ma tablica o 5 elementach? Co wypisze ten fragment?
int n = 5, ile = 1;
for (int i = 0; i < n; i++) ile *= 2;
cout << ile;
Pokaż odpowiedź
322 · 2 · 2 · 2 · 2 = 32. Niepustych jest o jeden mniej: 31.
Która maska? Co wypisze ten fragment?
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ź
1210 dwójkowo to 1010: od prawej — a[0] nie, a[1] tak, a[2] nie, a[3] tak. 7 + 5 = 12.
Co wypisze ten fragment?
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ź
3Palec znajduje 2 (numer 1), 2 (numer 3) i 1 (numer 4) — całe b jest podzbiorem a.
Co wypisze ten fragment?
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ź
0Po sortowaniu {1, 3, 3} i {1, 1, 3} — różne. To nie są swoje permutacje: a ma dwie trójki, b dwie jedynki.
Co wypisze ten fragment?
vector<int> v = {1, 3, 2};
next_permutation(v.begin(), v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
213Kolejność słownikowa: 123, 132, 213, … Po 132 następna jest 213.
Ile permutacji? Co wypisze ten fragment?
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ź
12Wszystkich permutacji jest 4! = 24. W połowie z nich pierwszy element jest mniejszy od ostatniego.
Co wypisze ten fragment?
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ź
6kotTrzy różne litery dają 3! = 6 ustawień. Po ostatnim next_permutation napis wraca do ułożenia rosnącego: „kot” (k < o < t).
Permutacja odwrotna. Co wypisze ten fragment?
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ź
312Osoba 1 stoi na miejscu 3, osoba 2 na miejscu 1, osoba 3 na miejscu 2.
Ćwiczenia · teraz Ty

9 ćwiczeń do tej części

0 / 9 zaliczonych

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ę.

7.1 Wykreślankałatwe✓ zaliczone Czy da się otrzymać ciąg b, wykreślając niektóre elementy z ciągu a? Dwa palce. podzbiór z zachowaniem kolejnościdwa palceTAK / NIE Rozwiąż 7.2 Czy to permutacja?łatwe✓ zaliczone Czy każda liczba od 1 do n występuje dokładnie raz? Jeśli nie — której najmniejszej brakuje? permutacja 1..nvector licznikówzakres przed indeksem Rozwiąż 7.3 Te same liczby?łatwe✓ zaliczone Czy dwa ciągi są swoimi permutacjami? Posortuj oba i porównaj całe vectory. sorta == bpermutacja Rozwiąż 7.4 Kto gdzie stoiłatwe✓ zaliczone Wiesz, kto stoi na każdym miejscu. Odwróć to: na którym miejscu stoi każda osoba? permutacja odwrotnagdzie[p[i]] = inumeracja od 1 Rozwiąż 7.5 Wszystkie podzbioryśrednie✓ zaliczone Wypisz wszystkie 2ⁿ podzbiorów w kolejności masek 0, 1, 2, … Cyfry dwójkowe mówią: bierzemy albo nie. maska od 0 do 2ⁿ − 1m % 2 i m /= 2podzbiór pusty Rozwiąż 7.6 Monetyśrednie✓ zaliczone Ile jest sposobów wybrania monet o sumie dokładnie S? Przejrzyj wszystkie podzbiory. wszystkie podzbiorymaskin ≤ 20 Rozwiąż 7.7 Podział na drużynyśrednie✓ zaliczone Podziel zawodników na dwie niepuste drużyny tak, by różnica sił była najmniejsza. maskireszta to druga drużynaabs Rozwiąż 7.8 Wszystkie ustawieniaśrednie✓ zaliczone Wypisz wszystkie różne permutacje ciągu w kolejności słownikowej. sort + next_permutation. next_permutationnajpierw sortdo … while Rozwiąż 7.9 Nikt na swoim miejscuśrednie✓ zaliczone Ile jest permutacji liczb 1..n, w których żadna liczba nie stoi na swoim miejscu? Sprawdź wszystkie. wszystkie permutacjewarunek p[i] ≠ in! ≤ 362 880 Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

Lustrzane pary: a[0] z a[4] (niebieskie), a[1] z a[3] (pomarańczowe). Środkowy a[2] (zielony) nie ma pary.
czy_palindrom.cpp
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";
▶ Wyjście
1 1
ciągpalindrom?
{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.

zmiany.cpp
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";
▶ Wyjście
2 3 1 4 4 1 3
Lustrzane pary to (a[0], a[5]) = (3, 3), (a[1], a[4]) = (1, 5) i (a[2], a[3]) = (4, 1). Pierwsza się zgadza (zielona), dwie pozostałe nie (pomarańczowe) — dwie zmiany. Program przepisuje prawy element każdej niezgodnej pary (niebieskie).
Lustrzane pary wypisz na kartce Najczęstsza pomyłka w zadaniach z palindromami to źle dobrana para — na przykład porównanie 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).

od_srodka.cpp
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";
▶ Wyjście
8
Ze środka w a[2] rozszerzamy: {1}, potem {2, 1, 2} (niebieskie), potem a[0] = 1 i a[4] = 2 się różnią — koniec. Palindromy: 5 jednoelementowych, {1, 2, 1}, {2, 1, 2} i {2, 2} — razem 8.

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.

dopisz.cpp
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";
▶ Wyjście
1 1 2 3 2 1
Najdłuższy sufiks-palindrom to {2, 3, 2} (zielony), zaczyna się na numerze 1. Element przed nim (1) dopisujemy na końcu (pomarańczowy).

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.

przestaw.cpp
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";
▶ Wyjście
TAK

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.

dwa_wskazniki.cpp
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";
▶ Wyjście
5
ija[i] + a[j]ruchpar
041 + 7 = 8j--0
031 + 5 = 6+3, i++3
132 + 5 = 7+2, i++5
234 + 5 = 9j--5
22wskaźniki się spotkały — koniec
Sprawdź się w głowie

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ź”.

Co wypisze ten fragment?
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ź
1Pary (4, 4) i (1, 1) się zgadzają — to palindrom.
Ile niezgodnych par? Co wypisze ten fragment?
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ź
2Pary: (1, 5) — różne, (2, 2) — równe, (3, 4) — różne.
Co wypisze ten fragment?
vector<int> a = {7, 8, 9};
vector<int> r = a;
reverse(r.begin(), r.end());
cout << r[0] << (r == a);
Pokaż odpowiedź
90Odwrócony vector to {9, 8, 7} — pierwszy element 9, a vectory są różne.
Rozszerzanie od środka. Co wypisze ten fragment?
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ź
2Środek między a[1] i a[2]: {5, 5} — tak, {3, 5, 5, 3} — tak, dalej l = −1, więc koniec.
Czy da się przestawić w palindrom? Co wypisze ten fragment?
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ź
24 i 5 występują po razie — dwie wartości nieparzyście, więc palindromu z tych liczb ułożyć się nie da.
Dwa wskaźniki. Co wypisze ten fragment?
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ź
1 9Już pierwsza para: 1 + 9 = 10 — pętla nie wykona ani jednego obrotu.
A teraz S = 7. Co wypisze ten fragment?
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ź
1 61 + 9 = 10 > 7, więc j--. 1 + 6 = 7 — znaleziona para.
Co wypisze ten fragment?
string s = "abccba";
string t = s;
reverse(t.begin(), t.end());
cout << (s == t) << t.size();
Pokaż odpowiedź
16„abccba” od tyłu to dalej „abccba” — palindrom o 6 literach.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

8.1 Czy palindrom?łatwe✓ zaliczone Czy ciąg liczb czyta się tak samo od przodu i od tyłu? Porównaj lustrzane pary. a[i] i a[n - 1 - i]pierwsza połowaTAK / NIE Rozwiąż 8.2 Liczby-palindromyłatwe✓ zaliczone Które liczby czytane od tyłu się nie zmieniają? Cyfry każdej liczby zbierz w vectorze i sprawdź. cyfry w vectorzepalindromliczba 0 Rozwiąż 8.3 Poprawki do palindromułatwe✓ zaliczone Ile elementów trzeba zmienić, by ciąg stał się palindromem? Popraw prawy element każdej złej pary. lustrzane parya[n - 1 - i] = a[i]licznik zmian Rozwiąż 8.4 Palindromiczne kawałkiśrednie✓ zaliczone Ile podtablic ciągu jest palindromami? Rozszerzaj od każdego środka w obie strony. podtablicarozszerzanie od środkaśrodek parzysty i nieparzysty Rozwiąż 8.5 Najdłuższy palindromiczny kawałekśrednie✓ zaliczone Znajdź najdłuższą podtablicę, która jest palindromem — jej długość, początek i koniec. rozszerzanie od środkanajdłuższyremis: najwcześniejszy początek Rozwiąż 8.6 Dopisz do palindromuśrednie✓ zaliczone Ile najmniej liczb trzeba dopisać na końcu ciągu, żeby był palindromem? Najdłuższy sufiks-palindrom. sufikspalindrompush_back od lustra Rozwiąż 8.7 Przestaw w palindromśrednie✓ zaliczone Czy da się ustawić liczby w palindrom? Jeśli tak — wypisz najmniejszy w kolejności słownikowej. permutacja i palindromlicznikinajwyżej jedna nieparzysta Rozwiąż 8.8 Pary w limicieśrednie✓ zaliczone Ile par liczb ma sumę najwyżej S? Posortuj i poprowadź dwa wskaźniki naprzeciw siebie. sortdwa wskaźnikij - i par naraz Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

Jak rozwiązywać zadania z vectorem 1) Przeczytaj ograniczenia i zdecyduj, czy wiesz z góry, ile będzie elementów — jeśli tak, 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.
łatwe

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.

1 Parzyste czy nieparzyste?łatwe✓ zaliczone Policz liczby parzyste i nieparzyste. Których jest więcej? vectorx % 2trzy możliwe odpowiedzi Rozwiąż 2 Pierwszy i ostatniłatwe✓ zaliczone Ciąg można obracać w kółko. Jaka jest największa możliwa suma pierwszego i ostatniego elementu? sąsiedzi w kółkua[n - 1] + a[0]long long Rozwiąż 3 Szczyty i dolinyłatwe✓ zaliczone Wysokości na szlaku: znajdź szczyty (wyżej od obu sąsiadów) i doliny (niżej od obu). a[i - 1], a[i], a[i + 1]dwa vectory wynikówBRAK Rozwiąż 4 Przesunięcie w kółkołatwe✓ zaliczone Przesuń ciąg o k miejsc w prawo w kółko. k może być gigantyczne — modulo ratuje sprawę. k % nnowy vectorw[(i + k) % n] = a[i] Rozwiąż 5 Zera na koniecłatwe✓ zaliczone Przenieś wszystkie zera na koniec ciągu, nie zmieniając kolejności pozostałych liczb. push_backresize albo pętlakolejność zostaje Rozwiąż 6 Bez powtórzeńłatwe✓ zaliczone Wypisz każdą różną liczbę raz, w kolejności pierwszego wystąpienia, razem z liczbą jej wystąpień. finddwa vectory: wartości i licznikikolejność pierwszego wystąpienia Rozwiąż 7 Lista zakupówłatwe✓ zaliczone DODAJ i USUN na liście zakupów — bez powtórzeń. vector napisów, find i erase. vector<string>finderase Rozwiąż 8 Bilans kontałatwe✓ zaliczone Wpłaty i wypłaty dzień po dniu. Saldo na koniec, najniższe saldo i pierwszy dzień na minusie. sumy prefiksówlong longpierwszy raz < 0 Rozwiąż 9 Następne ustawieniełatwe✓ zaliczone Wypisz następną permutację ciągu w kolejności słownikowej — albo OSTATNIE, jeśli to już koniec. next_permutationwartość zwracanakolejność słownikowa Rozwiąż 10 Kolejka do lekarzałatwe✓ zaliczone PRZYCHODZI dołącza na koniec, PILNY wchodzi na początek, WCHODZI zabiera pierwszego. insert i erase. push_backinsert(v.begin(), …)erase(v.begin()) Rozwiąż
średnie

Ś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.

11 Wyliczankaśrednie✓ zaliczone Dzieci w kółku, co k-te odpada. W jakiej kolejności odpadają? vector i erase z modulo. erasepozycja % size()kółko Rozwiąż 12 Scalanie dwóch listśrednie✓ zaliczone Dwie posortowane listy złącz w jedną posortowaną — dwoma wskaźnikami, bez sortowania od nowa. dwa wskaźnikiposortowanepush_back Rozwiąż 13 Wspólne elementyśrednie✓ zaliczone Liczby, które są na obu posortowanych listach — z powtórzeniami. Znowu dwa palce. dwa wskaźnikiposortowaneBRAK Rozwiąż 14 Wycieczka z budżetemśrednie✓ zaliczone Najdłuższy ciąg kolejnych dni, na który wystarczy budżetu. Okno, które rośnie i kurczy się. podtablicadwa wskaźnikiokno zmiennej długości Rozwiąż 15 Prawie palindromśrednie✓ zaliczone Czy usuwając najwyżej jeden element, zrobisz z ciągu palindrom? Którego elementu się pozbyć? palindromerase albo pominięcienajmniejszy numer Rozwiąż 16 Obrót w palindromśrednie✓ zaliczone Czy któryś obrót ciągu w kółko jest palindromem? Znajdź najmniejszy taki obrót. obrót przez modulopalindromn obrotów Rozwiąż 17 Drużyna marzeńśrednie✓ zaliczone Każdy zawodnik ma cenę i siłę. Kup najsilniejszą drużynę w budżecie — sprawdź wszystkie podzbiory. wszystkie podzbiorymaskidwa kryteria Rozwiąż 18 Tasowanie kartśrednie✓ zaliczone Idealne tasowanie: połówki na przemian. Po ilu tasowaniach talia wróci do porządku? nowy vector w każdej rundziev == startpermutacja Rozwiąż 19 Sumy prostokątówśrednie✓ zaliczone Tabela liczb i pytania o sumy prostokątów. Sumy prefiksowe w dwóch wymiarach w vectorze 2D. vector 2Dsumy prefiksowe 2Dlong long Rozwiąż 20 Najdłuższy palindromiczny podzbiórśrednie✓ zaliczone Wybierz elementy (kolejność zostaje) tak, by tworzyły jak najdłuższy palindrom. Podzbiory + palindromy. wszystkie podzbiorypalindrommaski Rozwiąż
trudne

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.

21 Sumy podzielne przez ktrudne✓ zaliczone Ile podtablic ma sumę podzielną przez k? Reszty z sum prefiksów i liczniki — uwaga na liczby ujemne! sumy prefiksówmodulo z ujemnymiliczniki reszt Rozwiąż 22 Grupy anagramówtrudne✓ zaliczone Pogrupuj słowa, które są swoimi anagramami. Posortowane litery to klucz grupy. sort na napisievector<vector<string>>grupy w kolejności pojawienia się Rozwiąż 23 Najmniej zamiantrudne✓ zaliczone Ile najmniej zamian dwóch elementów trzeba, by posortować permutację? Policz cykle. permutacjacyklevector odwiedzonych Rozwiąż 24 K-ta permutacjatrudne✓ zaliczone Która permutacja jest k-ta w kolejności słownikowej? Dla n = 12 next_permutation nie zdąży — licz z silni. permutacjesilniaerase z vectora dostępnych Rozwiąż 25 Najdłuższy rosnący podzbiórtrudne✓ zaliczone Wybierz jak najwięcej elementów, które (w kolejności z ciągu) rosną. Dla każdego elementu: najdłuższy kończący się na nim. podzbiór z zachowaniem kolejnościvector ddwie pętle Rozwiąż 26 Wyspytrudne✓ zaliczone Ile jest wysp na mapie i jak duża jest największa? vector par jako stos do zalewania wyspy. vector<string> jako mapastos: push_back i pop_backkierunki jako pary Rozwiąż 27 Sklejane palindromytrudne✓ zaliczone Ile jest par słów, które sklejone tworzą palindrom? vector napisów, pętla w pętli i lustrzane pary. vector<string>pary (i, j)palindrom Rozwiąż 28 Wielki finał: edytor ciągutrudne✓ zaliczone Osiem poleceń na jednym vectorze: dopisywanie, wstawianie, usuwanie, odwracanie, sumy, palindromy i permutacje. insert i erasereverse na kawałkupalindrom i permutacja Rozwiąż

Częste błędy i dobre praktyki

📦
Indeks w pustym vectorze
vector<int> v; v[0] = 5; — pudełka 0 nie ma. Indeks zmienia istniejący element, a push_back tworzy nowy. Chcesz od razu n pudełek — vector<int> v(n);.
🔣
Okrągłe czy klamry?
vector<int> a(5, 0); to pięć zer, a vector<int> a = {5, 0}; — dwa elementy: 5 i 0. Nawiasy okrągłe znaczą „ile, co”, klamry — „dokładnie te wartości”.
➕
v(n) i push_back naraz
Jeśli stworzysz vector<int> v(n);, a potem wczytasz liczby przez push_back, vector będzie miał 2n elementów: n zer, a za nimi dane. Wybierz jeden sposób.
🖨️
cout << v nie działa
Vectora nie wypiszesz jednym cout — tylko pętlą, element po elemencie. Iteratora też nie: cout << it to błąd, wartość pod strzałką to *it.
🔗
Brak & przy wczytywaniu
for (auto x : v) cin >> x; wczytuje do kopii — vector zostaje pełen zer, a kompilator milczy. Do wczytywania i zmieniania: for (auto &x : v).
🚧
Za vectorem
Ostatni element to v[v.size() - 1], v.back() albo *(v.end() - 1). v[v.size()] i *v.end() czytają spoza vectora.
0️⃣
size() - 1 w pustym vectorze
v.size() jest bez znaku: w pustym vectorze v.size() - 1 to gigantyczna liczba. Pisz i + 1 < v.size() albo zapisz rozmiar do int n = v.size();. Ostrzeżenie „comparison of integer expressions of different signedness” przy i < v.size() to tylko ostrzeżenie.
✂️
erase w pętli
Po erase elementy przesuwają się w lewo i pętla z i++ przeskakuje następny. Zamiast usuwać, zbuduj nowy vector z elementów, które mają zostać — prościej i szybciej.
📐
[od, do) — bez drugiej strzałki
sort, reverse, erase na kawałku nie biorą elementu pod drugą strzałką. Kawałek od a do b włącznie to v.begin() + a, v.begin() + b + 1.
🧭
Najpierw wiersz, potem kolumna
vector<vector<int>> m(n, vector<int>(k)); to n wierszy po k kolumn. Samo m(n) daje n pustych wierszy — wtedy m[w][c] czyta poza nimi.
🧩
Podtablica ≠ podzbiór
Podtablica to kawałek bez przerw (n(n+1)/2 możliwości), podzbiór — dowolny wybór (2n). Prefiks zaczyna się na 0, sufiks kończy na n − 1. Przeczytaj treść dwa razy, zanim zaczniesz pisać.
🔁
next_permutation od posortowanego
Żeby zobaczyć wszystkie permutacje, najpierw sort, potem do { … } while (next_permutation(…)). Bez sortowania pętla zacznie od środka listy i część ustawień pominie.

Co dalej?

Od teraz vector będzie Twoim podstawowym narzędziem — w prawie każdym kolejnym zadaniu zamiast tablicy z zapasem napiszesz vector<int> a(n);. Następna lekcja to sortowanie: zobaczysz, jak sort(v.begin(), v.end()) działa w środku i jak sortować według własnych zasad. Pojęcia z tej lekcji — podtablice, prefiksy, podzbiory, permutacje i palindromy — wrócą w każdym dziale olimpiady. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.