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

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

Для кого эта статья

Подборка готовых фрагментов C++17 с пояснением «что и зачем» в каждом блоке. Материал рассчитан на:

школьные олимпиады по информатике и кружки (ВсОШ, региональные этапы);
платформы Codeforces, Timus, e-olymp, informatics.msk.ru;
тех, кто уже знает циклы и vector, но хочет скопировать рабочий каркас и не терять время на ввод-вывод.

Каждый пример можно сохранить в main.cpp и собрать:

g++ -std=c++17 -O2 -pipe -static -s main.cpp -o main
./main < input.txt

На Windows в MinGW флаг -static иногда не нужен; на контесте обычно достаточно g++ -std=c++17 -O2 main.cpp.

Сначала теория

Алгоритмы в общем виде — раздел «Алгоритмы». Синтаксис C++ — C++ — о разделе, первая программа — Первая программа. Те же идеи на Python с разбором задач — Алгоритмы на Python — ЕГЭ и олимпиадка. Визуальная пауза между задачами — 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	компоненты связности
12. Шпаргалка	чек-лист
13. Файл целиком	одна заготовка

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

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

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

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

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

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ваш код

    return 0;
}

Разбор:

Строка	Смысл
`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 чисел

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << '\n';
    return 0;
}

Пример:

Вход:
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 t;
cin >> t;
while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    long long sum = 0;
    for (int x : a) {
        sum += x;
    }
    cout << sum << '\n';
}

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

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

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

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. Два указателя

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

vector<int> a = {1, 2, 3, 4, 6};
int target = 6;
int l = 0, r = (int)a.size() - 1;
while (l < r) {
  int s = a[l] + a[r];
  if (s == target) {
    cout << l << " " << r << '\n';
    break;
  }
  if (s < target) {
    ++l;
  } else {
    --r;
  }
}

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

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 — кратчайшие расстояния без весов

#include <queue>

vector<int> bfs(int start, const vector<vector<int>> &g) {
    int n = g.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v]) {
            if (dist[to] == -1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }
    return dist;
}

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

void dfs(int v, const vector<vector<int>> &g, vector<bool> &used) {
    used[v] = true;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to, g, used);
        }
    }
}

// запуск обхода всего графа
vector<bool> used(n);
for (int i = 0; i < n; ++i) {
    if (!used[i]) {
        dfs(i, g, used);
    }
}

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

const int dr[4] = {1, -1, 0, 0};
const int dc[4] = {0, 0, 1, -1};

int bfs_grid(int sr, int sc, int tr, int tc,
             const vector<string> &grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        if (r == tr && c == tc) {
            return dist[r][c];
        }
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc] == '#') continue;
            if (dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return -1;
}

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 (система непересекающихся множеств)

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

struct DSU {
    vector<int> parent, rank;

    explicit DSU(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int v) {
        if (v == parent[v]) return v;
        return parent[v] = find(parent[v]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b]) ++rank[a];
    }
};

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)
ДП	оптимум, рюкзак	зависит от таблицы
DSU	связность, Крускал	≈ O(n α(n))
Битмаски	перебор подмножеств	O(2ⁿ · n)

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

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

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

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <numeric>

using namespace std;

using ll = long long;
const ll INF = (1LL << 60);
const int MOD = 1'000'000'007;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cout << accumulate(a.begin(), a.end(), 0LL) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;   // раскомментируйте, если в условии несколько тестов
    while (t--) {
        solve();
    }
    return 0;
}

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

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

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

См. также

Другие статьи этого же раздела в боковом меню (как на странице "О разделе").

Для кого эта статья​

Краткий указатель по разделам​

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

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

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

Сумма n чисел​

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

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

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

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

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

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

2. vector и sort​

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

3. map и set​

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

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

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

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

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

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

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

6. Числа​

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

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

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

7. Строки​

8. Графы​

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

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

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

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

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

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

0/1-рюкзак​

10. Битмаски​

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

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

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

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

Связанные темы