C++ — олимпиадные шаблоны

НЕ ОБЯЗАТЕЛЬНО ДЛЯ НОВИЧКОВ

Приветствую! Здесь вы наверняка найдете, что ищете. Примеры в лаборатории рассчитаны на то, что мы разбираем что-то конкретное.

Текущая статья посвящена готовым заготовкам C++17 для школьных олимпиад и Codeforces.

Поэтому за теорией по текущей теме вам — в энциклопедию. Если ещё не погружались, то маршрут прост:

Обязательно пройдитесь.

А теперь приступим к нашему предмету.

Теория и соседние материалы

Теория алгоритмов — раздел "Алгоритмы"
Синтаксис C++ — C++ — о разделе, первая программа — Первая программа
Те же приёмы на Python — Алгоритмы на Python — ЕГЭ и олимпиадка
Оценка скорости кода — Big-O — шпаргалка
Код алгоритмов, написанный вручную (merge sort, BST, trie и др.) — репозиторий TheAlgorithms/C-Plus-Plus и его документация. На контесте копируйте шаблоны из этой статьи и используйте STL (vector, sort, map).
Между блоками задач — Turtle на Python

Навигация по примерам

Раздел	Что ищут
Каркас файла	`iostream`, ускорение `cin`/`cout`
Стартовые шаблоны	сумма, максимум, массив
1. Быстрый ввод-вывод	много чисел, `t` тестов
2. vector и sort	сортировка, `lower_bound`
3. map и set	частоты, `unordered_map`
4. Префиксные суммы	сумма на отрезке
5. Два указателя	пара с суммой, палиндром
6. Числа	НОД, модуль, быстрая степень
7. Строки	`string`, подстрока
8. Графы	список смежности, BFS, DFS
9. ДП	рюкзак, лестница
10. Битмаски	перебор подмножеств
11. DSU	компоненты связности
14. Топологическая сортировка	порядок вершин в DAG, алгоритм Кана
15. Запросы на отрезках	дерево Фенвика, sparse table
16. Поиск подстроки	префикс-функция, алгоритм Кнута-Морриса-Пратта
17. Каталог TheAlgorithms	учебный C++ по темам энциклопедии
12. Шпаргалка	чек-лист
13. Файл целиком	одна заготовка

Основы решения задач на C++

На олимпиаде программа почти всегда устроена одинаково:

Прочитать вход строго по формату условия.
Посчитать ответ (vector, сортировка, граф, ДП…).
Вывести ровно то, что просят — без лишних подписей и с правильными пробелами.

Стандартной библиотеки (STL) достаточно для большинства задач уровня региональной олимпиады и Div.2 Codeforces.

Обязательный каркас

Минимальный файл, который копируют в начало решения на контесте.

Разбор:

Строка	Смысл
`ios::sync_with_stdio(false)`	отключает синхронизацию `cin`/`cout` с C-stdio — ускоряет ввод
`cin.tie(nullptr)`	`cout` не сбрасывается перед каждым `cin`
`using namespace std`	на контесте экономит место; в учебных проектах лучше писать `std::` явно
`return 0`	код завершения для ОС (на проверяющей системе не критичен)

ЕГЭ и олимпиада

На ЕГЭ по информатике часто достаточно обычного cin. На Codeforces при n = 10⁵ и больше без ускорения ввода решение может получить TLE (Time Limit Exceeded). Формат вывода должен буквально совпадать с условием.

Стартовые шаблоны

Сумма n чисел

Пример:

Вход:
5
3 1 4 1 5

Выход:
14

long long для суммы — чтобы не переполнить int, если числа до 10⁹.

Максимум в массиве

int n;
cin >> n;
vector<int> a(n);
for (int &x : a) {
    cin >> x;
}
int mx = *max_element(a.begin a.end());
cout << mx << '\n';

max_element возвращает итератор на максимум; * снимает значение.

Массив из одной строки входа

Условие: одна строка из n целых.

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

Примеры по темам

1. Быстрый ввод-вывод

Несколько независимых тестов

Формат: первая строка t, дальше t задач одного типа.

Каждая итерация читает свой кусок входа и печатает одну строку ответа.

Чтение до конца файла

Редко на школьных олимпиадах, иногда в архивных задачах.

int x;
while (cin >> x) {
    cout << x * 2 << '\n';
}

2. vector и sort

vector<int> a = {5, 1, 4, 2};
sort(a.begin a.end());           // по возрастанию
sort(a.rbegin a.rend());         // по убыванию

// сортировка пар: сначала по первому, при равенстве — по второму
vector<pair<int, int>> p = {{1, 3}, {1, 1}, {2, 0}};
sort(p.begin p.end());

// бинарный поиск в отсортированном массиве
int pos = lower_bound(a.begin a.end 4) - a.begin();
// pos — индекс первого элемента >= 4

lower_bound работает за O(log n) только на отсортированном диапазоне.

k-й порядковый статистик (nth_element)

Когда нужен только k-й по величине элемент, без полной сортировки — в среднем O(n).

vector<int> a = {5, 1, 4, 2, 3};
int k = 2;  // 0-based: третий по порядку
nth_element(a.begin a.begin() + k, a.end());
cout << a[k] << '\n';

3. map и set

Частоты элементов

#include <map>

map<int, int> cnt;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    ++cnt[x];
}
for (auto [value, frequency] : cnt) {
    cout << value << ": " << frequency << '\n';
}

map хранит ключи отсортированными (красно-чёрное дерево), операции O(log n).

Быстрый счётчик (unordered_map)

#include <unordered_map>

unordered_map<int, int> cnt;
// ++cnt[x];  — в среднем O(1)

На контесте подключайте только то, что используете — лишние #include не мешают, но засоряют шаблон.

Множество уникальных значений

#include <set>

set<int> uniq;
uniq.insert(3);
uniq.insert(3);
cout << uniq.size() << '\n';  // 1

if (uniq.count(5)) {
    cout << "есть\n";
}

4. Префиксные суммы

Сумма на отрезке [l, r] за O(1) после O(n) предобработки (0-based, включительно).

vector<int> a = {2, 1, 5, 3};
int n = a.size();
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + a[i];
}

auto range_sum = [&](int l, int r) {
    return pref[r + 1] - pref[l];
};

cout << range_sum(1, 2) << '\n';  // a[1]+a[2] = 1+5 = 6

5. Два указателя

Пара с заданной суммой в отсортированном массиве

Проверка палиндрома строки

string s = "abba";
int l = 0, r = (int)s.size() - 1;
bool ok = true;
while (l < r) {
    if (s[l] != s[r]) {
        ok = false;
        break;
    }
    ++l;
    --r;
}
cout << (ok ? "YES\n" : "NO\n");

6. Числа

НОД (алгоритм Евклида)

long long gcd_ll(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

В C++17 можно std::gcd из <numeric>:

#include <numeric>
cout << gcd(12, 18) << '\n';  // 6

Остатки по модулю

const int MOD = 1'000'000'007;

int add_mod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int mul_mod(long long a, long long b) {
    return int((a * b) % MOD);
}

При сложении нескольких слагаемых удобнее сразу брать % MOD после каждого шага.

Быстрое возведение в степень

long long binpow(long long a, long long n, long long mod) {
    long long res = 1;
    a %= mod;
    while (n > 0) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

7. Строки

#include <string>

string s;
cin >> s;                    // одно слово без пробелов
getline(cin, s);               // строка с пробелами (осторожно после cin >>)

cout << s.size() << '\n';
cout << s.substr(2, 4) << '\n'; // 4 символа с индекса 2

if (s.find("abc") != string::npos) {
    cout << "найдено\n";
}

Сортировка символов для проверки анаграммы:

string a = "listen", b = "silent";
sort(a.begin a.end());
sort(b.begin b.end());
cout << (a == b ? "YES\n" : "NO\n");

8. Графы

Список смежности (ненаправленный)

int n = 5;  // вершины 0.n-1
vector<vector<int>> g(n);
auto add_edge = [&](int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
};

BFS — кратчайшие расстояния без весов

DFS — обход, острова, компоненты

BFS на сетке (лабиринт)

9. Динамическое программирование

Подъём по лестнице (1 или 2 ступени)

int n;
cin >> n;
vector<long long> dp(n + 1);
dp[0] = 1;
if (n >= 1) dp[1] = 1;
for (int i = 2; i <= n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << '\n';

0/1-рюкзак

w[i] — вес, c[i] — ценность, W — вместимость.

int W, n;
cin >> W >> n;
vector<int> w(n), c(n);
for (int i = 0; i < n; ++i) cin >> w[i] >> c[i];

vector<int> dp(W + 1);
for (int i = 0; i < n; ++i) {
    for (int cap = W; cap >= w[i]; --cap) {
        dp[cap] = max(dp[cap], dp[cap - w[i]] + c[i]);
    }
}
cout << dp[W] << '\n';

Цикл по cap с конца — чтобы каждый предмет использовали не больше одного раза.

10. Битмаски

Перебор всех подмножеств множества {0, …, n-1}:

int n = 4;
vector<int> a = {10, 20, 30, 40};
for (int mask = 0; mask < (1 << n); ++mask) {
    vector<int> subset;
    for (int i = 0; i < n; ++i) {
        if (mask & (1 << i)) {
            subset.push_back(a[i]);
        }
    }
    // обработка subset
}

Проверка i-го бита: mask & (1 << i). Включить бит: mask | (1 << i).

11. DSU (система непересекающихся множеств)

Объединение компонент, проверка, в одной ли группе две вершины, — почти за константу.

14. Топологическая сортировка

Топологическая сортировка — список вершин ориентированного графа, в котором для каждого ребра u → v вершина u стоит раньше v. Такой порядок нужен, когда объекты связаны зависимостями.

Типичные условия задач:

курс нельзя сдать, пока не пройдены предметы-требования;
модуль сборки ждёт готовности других модулей;
в расписании событие A должно произойти раньше B.

Ориентированный граф — рёбра имеют направление (стрелка от u к v). DAG (Directed Acyclic Graph, ациклический ориентированный граф) — граф без циклов по направлению рёбер. Топосорт определён только для DAG. Если цикл есть, упорядочить все вершины невозможно.

Входящая степень вершины — сколько рёбер в неё входят. В коде ниже это массив indeg.

Алгоритм Кана (Kahn's algorithm) строит порядок так:

В очередь кладут все вершины с входящей степенью 0.
Вершину из очереди добавляют в ответ и снимают исходящие рёбра (у соседей indeg уменьшается на 1).
Соседа с новым нулевым indeg снова кладут в очередь.
Если в ответе меньше n вершин — в графе есть цикл.

Сложность O(V + E), где V — число вершин, E — число рёбер. Та же асимптотика, что у BFS на списке смежности.

#include <queue>

int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
vector<int> indeg(n);
for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u; --v;  // если в условии вершины нумеруются с 1
    g[u].push_back(v);
    ++indeg[v];
}

queue<int> q;
for (int i = 0; i < n; ++i) {
    if (indeg[i] == 0) q.push(i);
}

vector<int> order;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    order.push_back(v);
    for (int to : g[v]) {
        if (--indeg[to] == 0) q.push(to);
    }
}

if ((int)order.size() != n) {
    cout << "cycle\n";  // в условии может быть NO или -1
} else {
    for (int v : order) cout << v + 1 << ' ';  // обратно к нумерации 1..n
    cout << '\n';
}

Разбор ключевых мест

g[u].push_back(v) — список смежности: из u можно перейти в v.
indeg[v] растёт при каждом входящем ребре.
--u; --v переводит вершины из диапазона 1..n в 0..n-1, если так задано в условии.

Теория и примеры

Графы — модели и задачи
Нотация O — оценка O(V + E)
Учебный файл на C++ — topological_sort_by_kahns_algo.cpp

15. Запросы на отрезках

В разделе 4 префиксные суммы считают сумму на отрезке [l, r] для неизменяемого массива. Ниже — две структуры для множества запросов:

Fenwick — массив меняется (точечные прибавления);
sparse table — массив фиксирован после построения, нужен минимум на отрезке.

Дерево Фенвика (Fenwick tree, BIT)

BIT (Binary Indexed Tree, двоичное индексированное дерево) — компактная структура в памяти. Поддерживает за O(log n):

прибавление к одному элементу a[i] += v;
сумму на префиксе [1..i];
сумму на отрезке [l, r] как sum(r) - sum(l - 1).

В олимпиадных задачах BIT часто заменяет префиксные суммы, когда массив меняется между запросами.

Индексация в примере с 1 — так короче формулы i += i & -i. Если в условии индексы с 0, сдвиньте их при чтении.

struct Fenwick {
    int n;
    vector<long long> bit;

    explicit Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}

    void add(int i, long long v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }

    long long sum(int i) const {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

    long long range_sum(int l, int r) const {
        return sum(r) - sum(l - 1);
    }
};

// массив a[1..n], m запросов: прибавить v к a[i] или сумма на [l, r]
int n, m;
cin >> n >> m;
vector<long long> a(n + 1);
Fenwick fw(n);
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    fw.add(i, a[i]);
}
while (m--) {
    int t;
    cin >> t;
    if (t == 1) {
        int i;
        long long v;
        cin >> i >> v;
        fw.add(i, v);
    } else {
        int l, r;
        cin >> l >> r;
        cout << fw.range_sum(l, r) << '\n';
    }
}

Разбор

i & -i выделяет младший установленный бит — основа обхода дерева за O(log n).
long long в суммах снижает риск переполнения при больших n и значениях.

Связанные материалы

Префиксные суммы в этой статье
Реализация структур данных — теория массивов и деревьев
fenwick_tree.cpp

Sparse table (RMQ на статическом массиве)

RMQ (Range Minimum Query) — запрос минимума на отрезке [l, r]. Sparse table (разреженная таблица) подходит, когда:

массив после построения не меняется;
запросов минимума очень много.

Построение за O(n log n), один запрос за O(1).

vector<vector<int>> build_sparse_table(const vector<int>& a) {
    int n = (int)a.size();
    int LOG = 1;
    while ((1 << LOG) <= n) ++LOG;
    vector<vector<int>> st(LOG, vector<int>(n));
    st[0] = a;
    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i + (1 << k) <= n; ++i) {
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
    return st;
}

int rmq(const vector<vector<int>>& st, const vector<int>& lg, int l, int r) {
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

// lg[i] = floor(log2(i)); заранее: lg[1]=0; for (int i=2..n) lg[i]=lg[i/2]+1

Связанные материалы

sparse_table_range_queries.cpp
prefix_sum_array.cpp — префиксы в том же разделе репозитория

16. Поиск подстроки

Подстрока — непрерывный фрагмент строки. В задаче обычно даны текст t и образец (шаблон) p; нужно найти все позиции, где p встречается в t.

Префикс-функция (массив π)

Для строки s значение pi[i] — длина наибольшего собственного префикса подстроки s[0..i], который одновременно является её суффиксом.

Пример для s = "ababc":

pi[0] = 0 (у одного символа нет собственного префикса);
у "aba" совпадают префикс "a" и суффикс "a" → pi[2] = 1;
префикс-функция помогает при сдвиге образца и лежит в основе KMP.

vector<int> prefix_function(const string& s) {
    int n = (int)s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}

Алгоритм Кнута-Морриса-Пратта (KMP)

Проходит текст один раз, сравнивая с образцом. Время O(|t| + |p|) вместо наивного O(|t| · |p|) при многократных сравнениях.

vector<int> kmp_search(const string& t, const string& p) {
    auto pi = prefix_function(p);
    vector<int> pos;
    int j = 0;
    for (int i = 0; i < (int)t.size(); ++i) {
        while (j > 0 && t[i] != p[j]) j = pi[j - 1];
        if (t[i] == p[j]) ++j;
        if (j == (int)p.size()) {
            pos.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    return pos;
}

Когда какой приём брать

короткие строки, один поиск — часто хватает s.find(sub) из раздела 7;
длинный текст, жёсткий лимит времени (TLE), много вхождений — KMP или префикс-функция;
теория строк в энциклопедии — Алгоритмы сортировки и поиска (бинарный поиск по ответу часто рядом по сложности).

Учебный код

knuth_morris_pratt.cpp
z_function.cpp — родственный приём для поиска

17. Каталог TheAlgorithms

TheAlgorithms/C-Plus-Plus — открытый репозиторий с сотнями файлов на C++17. Каждый файл — один алгоритм или структура данных, без сторонних библиотек. Лицензия MIT. Удобно читать после теории в энциклопедии, когда псевдокод из статьи хочется сопоставить с рабочим кодом.

Как пользоваться вместе с этой статьей

на контесте и в тренировке Codeforces — шаблоны из разделов 1–13 выше и контейнеры STL;
для разбора устройства merge sort, BST, trie — соответствующий .cpp в репозитории;
полный список файлов — DIRECTORY.md;
комментарии и схемы — документация Doxygen.

Темы энциклопедии и папки репозитория

Тема	Где в энциклопедии	Папка на GitHub
Сортировка и поиск	глава 2	`sorting/`, `search/`
Графы	глава 4, Дейкстра	`graph/`
Структуры данных	о разделе, реализация	`data_structures/`
Числа и НОД	Евклид	`math/`
Динамическое программирование	раздел 9	`dynamic_programming/`
Битовые трюки	раздел 10	`bit_manipulation/`
Запросы на отрезках	раздел 15	`range_queries/`
Строки	раздел 7, раздел 16	`strings/`

Файлы в репозитории пишутся для обучения. Стиль и имена переменных могут отличаться от идиом C++ в вашем проекте — сравнивайте с ООП и STL.

12. Шпаргалка перед отправкой

Приём	Когда	Сложность (типично)
`sort` + два указателя	пары, triplets	O(n log n)
`map` / `unordered_map`	частоты	O(n log n) / O(n)
Префиксные суммы	много запросов на отрезок	O(n + q)
`lower_bound`	поиск в отсортированном	O(log n)
BFS	кратчайший путь без весов	O(V + E)
DFS	компоненты, острова	O(V + E)
Топосорт (Кан)	порядок в DAG, зависимости	O(V + E)
ДП	оптимум, рюкзак	зависит от таблицы
DSU	связность, минимальный остов (Крускал)	≈ O(n α(n))
Fenwick / sparse table	сумма или минимум на отрезке	O(log n) / O(1) на запрос
KMP / π	поиск подстроки в длинном тексте	O(n + m)
Битмаски	перебор подмножеств	O(2ⁿ · n)

Граничные случаи

n = 0 или пустой массив
один элемент
все числа одинаковые
переполнение int — используйте long long
индексация с 0 или с 1 в ответе
лишний пробел или перевод строки в выводе

13. Файл целиком на контест

Скопируйте в начало, допишите логику в solve() или сразу в main.

accumulate из <numeric> считает сумму диапазона.

Куда двигаться дальше

Уровень	Материал
Те же задачи на Python	Алгоритмы на Python — ЕГЭ и олимпиадка
Сложность O(n)	Нотация O
Сортировка и поиск	глава 2
Графы	глава 4
Учебный C++ по темам	раздел 17, TheAlgorithms/C-Plus-Plus
STL подробнее	Справочник C++, Работа с данными
Сборка локально	CMake
Игры на C++	Разработка игр