Всю жизнь придётся оценивать, сколько работают алгоритмы. Точное время никто не считает — оно зависит от процессора, ядер и массы других вещей. Вместо этого оценивают количество операций, которые делает код.
Это оценка сверху. Пример: int x = 5; делает константное число операций — это $O(1)$. Два цикла по $n$ делают $2n$ операций — но $2n = n \cdot \text{конст}$, значит тоже $O(n)$.
Код, который делает $n^2$ операций, можно оценить и как $O(n^3)$: ведь $n^2 \le n^3$ для $n \ge 1$. Оценка сверху — это «можно сказать грубо». Поэтому:
Скрытая константа бывает огромной. Например, сумма массива циклом — $O(n)$; но можно написать 1000 if-ов для каждого возможного размера — формально тоже $O(1)$, но работать будет плохо. Другой пример: insert в set — $O(\log n)$, но с константой порядка 10.
| Ограничение на $n$ | Типичная ожидаемая сложность |
|---|---|
| $n \le 15$ | $n!$ или $2^n$ |
| $n \le 20$ | $2^n$ |
| $n \le 100$ | $n^4$ (или $n^3$) |
| $n \le 500$ | $n^3$ |
| $n \le 1000$ | $n^2$ (смачный, с константой) |
| $n \le 10^4$ | $n^2$ (лёгкий) |
| $n \le 10^5$ | $n \log n$ |
| $n \le 10^6$ | $n$ (или $n\log\log n$) |
| $n \le 10^{12}$ | $\sqrt n$ |
| $n \le 10^{18}$ | $O(1)$ или $\log n$ |
Правило не строгое (иногда при $n\le1000$ бывает решение за $O(n\log n)$), но по ограничениям в условии уже видно, какую сложность ждёт жюри. На олимпиадах типа ВсОШ это работает постоянно — по подгруппам ($n\le10$, $n\le100$, $n\le500$, $n\le1000$…).
| Тип | Размер | Диапазон (знаковый) |
|---|---|---|
char | 1 байт | $[-2^7,\ 2^7)$ |
short | 2 байта | $[-2^{15},\ 2^{15})$ |
int | 4 байта | $[-2^{31},\ 2^{31})$ ≈ $\pm 2\cdot10^9$ |
long long | 8 байт | $[-2^{63},\ 2^{63})$ ≈ $\pm 9\cdot10^{18}$ |
unsigned | как у базы | только $\ge 0$, до $2^{32}-1$ (для int) |
__int128 | 16 байт | примерно $[-2^{127},\ 2^{127})$ |
Для олимпиадного программирования можно считать, что int — всегда 4 байта, long long — 8 байт (на самом деле стандарт это не гарантирует, но на практике так). Если числа до $\sim 2\cdot10^9$ — хватает int; до $\sim 9\cdot10^{18}$ — long long.
Если положить в int его максимум и прибавить единицу, произойдёт переполнение.
long long x = 1e9;
long long y = x * x * 10; // ОШИБКА: x * x * 10 = 10^19 > 9,2·10^18 — переполнение long longПроблема в том, что произведение вычисляется в типе операндов, а присваивание в long long происходит уже после него. Здесь $x\cdot x\cdot10=10^{19}$ не помещается даже в long long. Ещё хуже, если $x$ — int порядка $10^9$: тогда переполнится уже $x\cdot x$, хотя результат присваивается в long long. Нужно следить за типом каждого промежуточного шага.
__int128 24:00Для очень больших промежуточных значений (например, перемножение двух long long) используют __int128. Это расширение GCC/Clang, а не тип стандарта C++ — работает на судейских системах на практике, но не описан в стандарте и может быть недоступен на других компиляторах (например, MSVC). Его нельзя напрямую вводить и выводить (cin/cout), но для промежуточных вычислений он годится. Приводить нужно явно: (__int128)a * b.
char 26:29char внутри — это число. Буква 'x' — номер по таблице ASCII. Поэтому:
char c = 'x';
cout << c - 'a'; // номер буквы x в алфавите (0-индексация): 23Задача. Есть объекты «бабушка» с тремя полями (возраст, рост, зарплата). Нужно хранить их вместе и сортировать по разным ключам.
Если полей много, сортировать три отдельных массива одинаковым образом неудобно. Вместо этого заводим структуру:
struct Granny {
int age;
int height;
int salary;
};
vector<Granny> v(n);
// ... ввод ...
Теперь «вся бабушка» — один объект. Но sort(v.begin(), v.end()) не скомпилируется: C++ не знает, как сравнивать двух бабушек. Нужен компаратор — функция, реализующая «меньше».
bool cmp(const Granny& left, const Granny& right) {
return left.salary < right.salary;
}
sort(v.begin(), v.end(), cmp); // сортировка по зарплатеКомпаратор возвращает true тогда и только тогда, когда left строго меньше right. Если объекты равны — нужно вернуть false (оба порядка).
true для cmp(a, b) и для cmp(b, a) одновременно (например, при равенстве), это нарушает контракт «меньше» — sort может упасть или выдать мусор.operator< внутри структуры 40:32struct Granny {
int age, height, salary;
bool operator<(const Granny& other) const {
return salary < other.salary;
}
};
sort(v.begin(), v.end()); // C++ сам использует operator<Здесь this — «левый» объект, other — «правый». Ключевое слово const в конце запрещает случайно менять свой объект внутри сравнения (если его убрать — 20 ошибок компиляции). После этого sort, set и другие контейнеры умеют сравнивать бабушек автоматически.
sort(v.begin(), v.end(), [](const Granny& l, const Granny& r) {
return l.salary < r.salary;
});Пусть сначала идут более взрослые, при равном возрасте — более высокие, при равном росте — с меньшей зарплатой:
bool operator<(const Granny& o) const {
if (age != o.age) return age > o.age; // старше — раньше
if (height != o.height) return height > o.height; // выше — раньше
return salary < o.salary; // беднее — раньше
}pair и tuple для хранения разнородных данных — по названиям first/second ничего не понятно. Заводите структуру с осмысленными именами полей.По умолчанию C++ выводит вещественное число с произвольным числом знаков. Чтобы вывести ровно нужное число знаков после запятой:
#include <iomanip>
cout << fixed << setprecision(15) << x;setprecision без fixed задаёт число значащих цифр; с fixed — ровно столько знаков после запятой (дополняя нулями).double хранит ~15 значащих цифр — больше 15 выводить бессмысленно.vector — обёртка над массивом. Два главных свойства:
push_back) и удалять с конца (pop_back).size и capacitysize < capacity, вставка — $O(1)$. Когда места нет, буфер удваивается и копируется; в сумме это всё равно $O(1)$ на вставку.Пока size < capacity, push_back просто кладёт элемент на позицию size и увеличивает size — это $O(1)$. Когда size == capacity, выделяется новый буфер в два раза больше, всё копируется, и только тогда дописывается новый элемент.
push_back амортизированно $O(1)$ 1:07:18Переаллокация стоит $O(\text{size})$, но происходит всё реже и реже. Если буфер удваивается, то суммарная стоимость $n$ операций push_back ограничена $O(n)$: после дорогой переаллокации размера $s$ следующие $s$ операций «бесплатны». Итого $O(1)$ амортизированно на операцию.
| Операция | Что делает | Сложность |
|---|---|---|
push_back(x) | добавить в конец | $O(1)$ амортизированно |
pop_back() | убрать последний | $O(1)$ |
back() | последний элемент (как a[size-1]) | $O(1)$ |
reserve(n) | зарезервировать capacity $\ge n$ | не более $O(n)$ (если capacity уже $\ge n$ — $O(1)$) |
resize(n, v) | изменить size, заполняя новое значением v | $O(n)$ |
assign(n, v) | заменить содержимое на n копий v | $O(n)$ |
insert(pos, v) | вставить в середину | $O(n)$ — медленно |
erase(pos) | удалить из середины | $O(n)$ — медленно |
insert и erase в середину вектора сдвигают все элементы справа — это $O(n)$. Если такие операции нужны часто, вектор не подходит (нужен set или список).Ещё: vector<int> v(n, 5) — создаёт вектор из $n$ элементов, равных $5$. И resize добавляет новые элементы со значением по умолчанию, не трогая старые; assign — перезаписывает всё.
Стек (LIFO — last in, first out) — это просто вектор, у которого доступ только к верхнему элементу: push (добавить сверху) и pop (убрать сверху). std::stack по умолчанию реализован через deque, но вектор «умеет всё то же самое» — проще пользоваться вектором.
Очередь — first in, first out: добавляют в конец, достают из начала. В отличие от стека, у очереди «двигается» начало, поэтому просто на статическом буфере её не сделать — начало «отмирает», а конец дописывается.
head и tail идут по кругу по модулю capacity; очередь может «переехать» через край массива.Держим два указателя head и tail. Добавление двигает tail вперёд, удаление — head. Когда указатель доходит до конца буфера, он «сбрасывается» в ноль (по модулю capacity). Главное требование: tail не должен догонять head — иначе очередь переполнится.
Дек (double-ended queue) умеет добавлять и удалять с обоих концов. Внутри — не сплошной массив, а указатели на блоки фиксированного размера (в libstdc++ — по 512 байт). Поэтому:
Реально дек нужен редко — только если надо добавлять в начало и в конец при переменном размере.
Любой способ сделать стек задаёт способ сделать очередь. Держим два стека: в первый добавляем, из второго достаём. Когда второй пуст, перекладываем в него всё из первого (переворачивая порядок).
// стек хранит пары {значение, сумма всего, что ниже}
vector<pair<int,long long>> st;
void push(int x) {
long long s = st.empty() ? 0 : st.back().second;
st.push_back({x, s + x});
}
// сумма всех элементов = st.back().second;
// pop: просто st.pop_back(); // сумма нижних остаётся корректнойЭто работает благодаря тому, что «цепочка» элементов под верхушкой нерушима: когда удаляешь верхний, всё, что ниже, остаётся как было.
Итератор — «умный указатель» на элемент контейнера, который умеет шагать по контейнеру. Два ключевых умения: разыменование *it (значение) и инкремент ++it (перейти к следующему).
auto it = v.begin(); // итератор на первый элемент
*it; // значение первого элемента
++it; // теперь на второй
v.end(); // итератор ЗА последний (как size в мини-векторе)Для вектора итератор — это фактически индекс: v[1] эквивалентно *(v.begin() + 1). Полуинтервал [begin, end) — универсальная договорённость всех алгоритмов STL.
sort, merge, max_element…) написаны так, что работают с любым контейнером, лишь бы у него были итераторы. Разность итераторов вектора даёт индекс: it - v.begin().priority_queue 1:53:37Приоритетная очередь (куча) хранит данные так, чтобы быстро доставать максимум (по умолчанию) или минимум.
#include <queue>
priority_queue<int> pq; // куча на максимум
pq.push(x); // добавить, O(log n)
pq.top(); // максимум, O(1)
pq.pop(); // удалить максимум, O(log n)Внутри это двоичное дерево (бинарная куча): у каждой вершины до двух детей, корень — самый большой. Все операции добавления/удаления — $O(\log n)$, взятие максимума — $O(1)$.
Чтобы получить кучу на минимум, есть два варианта:
greater<int>);set, multiset, map 2:03:30set — множество уникальных элементов, отсортированное по возрастанию. Внутри — сбалансированное двоичное дерево, поэтому все операции за $O(\log n)$.
set<int> s;
s.insert(5); // добавить
s.erase(5); // удалить по значению
s.erase(it); // удалить по итератору
s.count(5); // 0 или 1 (есть ли элемент)
s.find(5); // итератор на элемент или end()
s.contains(5); // C++20: есть ли элемент (bool)
*s.begin(); // минимальный элементПроверка наличия: s.count(x) возвращает $0$ или $1$; или s.find(x) != s.end(). Две функции, о которых ещё будет отдельный разговор — lower_bound и upper_bound (но для set нужно использовать методы, не алгоритмы — об этом в §10).
Отличается тем, что хранит все копии одного элемента. Важный нюанс удаления:
multiset<int> ms;
ms.erase(2); // удалит ВСЕ двойки!
auto it = ms.find(2);
ms.erase(it); // удалит только одну двойкуms.count(x) в multiset работает за $O(\log n + k)$, где $k$ — количество копий $x$. Не используйте count для проверки наличия — есть find/contains.map — «словарь»: пары (ключ → значение), ключи отсортированы и уникальны. Устроен как set из пар, но сравниваются только ключи.
map<int,string> mp;
mp[5] = "hello"; // записать значение по ключу 5
cout << mp[1]; // читать (создаст, если ключа нет)
mp.erase(key); // удалить по ключу
auto it = mp.find(6); // итератор на пару {key, value} или end()
it->second; // значениеmp[key] при отсутствии ключа создаёт его со значением по умолчанию. Если нужно только проверить наличие — используйте find или contains.Классическое применение — подсчёт частоты:
map<char,int> cnt;
for (char c : s) cnt[c]++; // сколько раз встречается каждая букваВсе алгоритмы лежат в <algorithm> и работают с полуинтервалом [begin, end).
| Функция | Что делает | Сложность / условие |
|---|---|---|
sort(b, e) | сортировка по возрастанию | $O(n\log n)$ |
sort(b, e, cmp) | сортировка с компаратором | $O(n\log n)$ |
reverse(b, e) | развернуть | $O(n)$ |
min_element(b, e) | итератор на минимум | $O(n)$ |
max_element(b, e) | итератор на максимум | $O(n)$ |
rotate(b, mid, e) | циклический сдвиг | $O(n)$ |
unique(b, e) | сдвинуть уникальные в начало | $O(n)$; нужен сортированный |
lower_bound(b, e, x) | первый $\ge x$ | $O(\log n)$; нужен сортированный |
upper_bound(b, e, x) | первый $> x$ | $O(\log n)$; нужен сортированный |
binary_search(b, e, x) | есть ли $x$ (bool) | $O(\log n)$; нужен сортированный |
shuffle(b, e, rng) | перемешать | $O(n)$ |
iota(b, e, v) | заполнить $v, v+1, v+2,\dots$ | $O(n)$ |
next_permutation(b, e) | следующая перестановка | $O(n)$ |
sort(v.rbegin(), v.rend()); // обратные итераторы
// или: sort(v.begin(), v.end()); reverse(v.begin(), v.end());Работает только на отсортированном массиве: сдвигает все уникальные значения в начало и возвращает итератор на «конец уникальных». Обычно:
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // оставить только уникальныеЕсли элемента нет — обе функции укажут на первый элемент, больший $x$. Если $x$ больше всех — вернут end. Требуется отсортированность.
lower_bound(s.begin(), s.end(), x) для set работает за $O(n)$! Итераторы сета не умеют быстро прыгать в середину. Используйте метод контейнера: s.lower_bound(x) — $O(\log n)$.mt19937 rng(1000); // фиксированный seed
shuffle(v.begin(), v.end(), rng); // перемешатьС фиксированным seed последовательность случайных чисел всегда одна и та же — удобно для воспроизводимых тестов.
Undefined behavior (UB) — ситуация, когда стандарт не определяет, что должно произойти. После UB программа может сделать «всё, что угодно»: локально работать, а в тестирующей системе — упасть. Примеры:
lower_bound на несортированном массиве);auto it = s.begin();
s.erase(it); // итератор it теперь указывает на удалённый элемент
*it; // ОШИБКА: обращение к тому, чего уже нетПосле удаления элемента итератор на него становится «инвалидным» — использовать его нельзя (память могли освободить).
Идея. Есть «медленное, но точно правильное» решение (брутфорс) и «быстрое, но сомнительное». Генерируем случайные маленькие тесты, прогоняем оба решения и сравниваем ответы. Как только разошлись — найден контрпример.
// генератор случайных тестов
mt19937 rng(1000);
vector<int> gen() {
int n = rng() % 10 + 1; // маленький размер
vector<int> a(n);
for (int &x : a) x = rng() % 100; // значения 0..99
return a;
}
int brute(vector<int> a) { /* медленное, но верное O(n^2) */ }
int fast(vector<int> a) { /* быстрое, но подозрительное */ }
int main() {
for (int it = 0; it < 10000; ++it) {
vector<int> a = gen();
int r1 = brute(a), r2 = fast(a);
if (r1 != r2) {
// нашли контрпример — выводим его и останавливаемся
for (int x : a) cout << x << " ";
return 0;
}
}
}vector<int> p(n);
iota(p.begin(), p.end(), 0); // 0, 1, 2, ..., n-1
do {
check(p); // проверяем тест-перестановку
} while (next_permutation(p.begin(), p.end())); // все перестановкиnext_permutation перебирает все перестановки в лексикографическом порядке; когда доходит до последней — возвращает false.
#include <chrono>
auto start = chrono::steady_clock::now();
/* ... запускаем решение ... */
auto finish = chrono::steady_clock::now();
double ms = chrono::duration_cast<chrono::milliseconds>(finish - start).count();
cerr << ms << " ms\n"; // пишем в stderr, чтобы не мешать выводуПолезно сгенерировать макстест и замерить, работает ли он локально за разумное время (локальная скорость может отличаться от тестирующей системы).
Компиляция из терминала: g++ main.cpp -o main. Полезные флаги:
| Флаг | Что делает |
|---|---|
-std=c++17 | стандарт языка |
-O2 / -O3 | оптимизация (для макстестов; ejudge использует -O2) |
-O0 | без оптимизаций (для отладки) |
-Wall | предупреждения (например, неиспользуемые переменные) |
-g | отладочная информация |
-fsanitize=address,undefined | санитайзеры (ловит UB и выход за границы) |
Санитайзеры — специальный режим компиляции, который вставляет проверки: выход за границы массива, деление на ноль, использование неинициализированной памяти и т. п. Минус — сильно замедляют работу, поэтому с ними только отлаживаются; для макстестов их убирают и компилируют с -O2.