Visual Studio Code - инструкция по работе с программой для написания кода
Оглавление
1) Бинарный поиск
2) Префикс-суммы
3) Сортировки и связанные приёмы
4) Базовые структуры данных
5) Динамическое программирование
6) Жадные алгоритмы
7) Графы
8) Рюкзаки
9) Комбинаторика
10) Теория чисел
11) DSU / СНМ
12) Дерево отрезков
13) Побитовые операции
14) STL C++ и оптимизация
1) Бинарный поиск
База: поиск в отсортированном массиве
Что это (очень просто)
Массив отсортирован. Ты хочешь понять: где находится x (или что его нет). Вместо перебора всех элементов ты каждый раз “выкидываешь половину”.
Где используется
- поиск элемента
- проверка “есть ли число”
- подсчёты через границы (см. lower/upper)
Где НЕ использовать
- массив не отсортирован
- “похоже отсортирован” — это не подходит
Логика (разжёвано)
- Берём середину
m.
- Если
a[m] == x — готово.
- Если
a[m] < x, значит всё слева ≤ a[m] < x, там x быть не может → идём вправо.
- Если
a[m] > x — аналогично, идём влево.
Код
Python
def bin_search(a, x):
l, r = 0, len(a) - 1
while l <= r:
m = (l + r) // 2
if a[m] == x:
return m
if a[m] < x:
l = m + 1
else:
r = m - 1
return -1
C++
int bin_search(const vector<int>& a, int x) {
int l = 0, r = (int)a.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == x) return m;
if (a[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}
Задача 1 (микро)
Условие: дана отсортированная последовательность из n целых и число x. Вывести индекс x (0-индексация) или -1.
Идея: классический бинпоиск.
Решение (Python):
n = int(input())
a = list(map(int, input().split()))
x = int(input())
print(bin_search(a, x))
Решение (C++):
#include <bits/stdc++.h>
using namespace std;
int bin_search(const vector<int>& a, int x) {
int l = 0, r = (int)a.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == x) return m;
if (a[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int x;
cin >> x;
cout << bin_search(a, x) << "\n";
}
Разбор логики: мы всегда оставляем инвариант: если x есть, то он внутри текущего [l, r]. Каждым шагом сужаем диапазон в 2 раза.
Пример 2 — подробный разбор
Условие: даны отсортированный массив a длины n и число x. Нужно найти минимальный индекс i, такой что a[i] >= x. Если такого нет, вывести -1.
Идея и инварианты: мы ищем первую позицию, где значение не меньше x. Поддерживаем интервал [l, r) (полуоткрытый), где все индексы < l гарантированно имеют a[idx] < x, а все индексы >= r гарантированно имеют a[idx] >= x или находятся за пределом массива. В конце l == r — это наша позиция. Если l == n, значит таких элементов нет.
Пошаговое решение (Python, читаемо):
def lower_bound(a, x):
# поиск в полуинтервале [l, r)
l, r = 0, len(a)
while l < r:
m = (l + r) // 2
# если a[m] >= x, ответ слева включая m
if a[m] >= x:
r = m
else:
# a[m] < x, ответ правее
l = m + 1
# l == r — индекс первой позиции с a[i] >= x, либо len(a)
return l if l < len(a) else -1
# пример использования
n = int(input())
a = list(map(int, input().split()))
x = int(input())
print(lower_bound(a, x))
Почему это безопасно: при каждом шаге мы сохраняем инвариант о границах; цикл завершается потому, что длина интервала строго уменьшается, и при завершении l — минимальная позиция удовлетворяющая условию.
Разбор возможных ошибок:
- Неправильный выбор закрытой формы
[l, r] без осторожности может привести к бесконечному циклу — поэтому удобнее и безопаснее использовать [l, r).
- Не забывайте проверять выход за пределы массива: если функция вернула
len(a), значит подходящей позиции нет — возвращаем -1.
lower_bound / upper_bound
Что это
Они не ищут “равно”, они ищут границу:
lower_bound(x) = первый индекс, где a[i] >= xupper_bound(x) = первый индекс, где a[i] > x
Где используется
- посчитать сколько раз встречается
x
- посчитать сколько элементов в диапазоне значений
[L, R]
- найти “место вставки”
Где НЕ использовать
Логика (почему работает)
Мы ищем первую позицию, где условие становится истинным (монотонность по индексу).
Код
Python (руками)
def lower_bound(a, x):
l, r = 0, len(a) # [l, r)
while l < r:
m = (l + r) // 2
if a[m] >= x:
r = m
else:
l = m + 1
return l
def upper_bound(a, x):
l, r = 0, len(a)
while l < r:
m = (l + r) // 2
if a[m] > x:
r = m
else:
l = m + 1
return l
C++ (STL)
int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
int ub = upper_bound(a.begin(), a.end(), x) - a.begin();
Задача 1 (важная)
Условие: дан отсортированный массив. Вывести, сколько раз встречается число x.
Решение (логика): все x стоят подряд. Их количество = upper_bound(x) - lower_bound(x).
Python
n = int(input())
a = list(map(int, input().split()))
x = int(input())
print(upper_bound(a, x) - lower_bound(a, x))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int x; cin >> x;
int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
int ub = upper_bound(a.begin(), a.end(), x) - a.begin();
cout << (ub - lb) << "\n";
}
Разбор: lower_bound — “левая граница блока x”, upper_bound — “точка сразу после блока”. Разность = длина блока.
Бинпоиск по монотонному условию
Что это
Иногда нет массива. Но есть вопрос типа:
“Если я возьму t, получится? Да/Нет.”
И если при большем t становится легче, то ответ монотонный.
Где используется
- минимальный размер/время/скорость/ёмкость
- “сколько дней нужно”
- “какой минимальный предел”
Где НЕ использовать
- если при увеличении
t иногда становится хуже (нет монотонности)
Ключевая логика
Секрет — в инварианте:
- хотим найти первое True
- держим границы так, чтобы ответ точно не потерять
Код-шаблон (первое True)
Python
def first_true(l, r, ok): # l..r целые
while l < r:
m = (l + r) // 2
if ok(m):
r = m
else:
l = m + 1
return l
C++
long long first_true(long long l, long long r, auto ok) {
while (l < r) {
long long m = l + (r - l) / 2;
if (ok(m)) r = m;
else l = m + 1;
}
return l;
}
Задача 1 (классика муниципа)
Условие: даны w, h, n. Найдите минимальную сторону квадрата s, чтобы в него поместилось n прямоугольников w×h, не поворачивая, укладывая в сетку.
Идея: если сторона s увеличивается, помещается не меньше прямоугольников ⇒ монотонность.
ok(s): (s//w) * (s//h) >= n.
Python
w, h, n = map(int, input().split())
def ok(s):
return (s // w) * (s // h) >= n
l, r = 0, 1
while not ok(r):
r *= 2
while l < r:
m = (l + r) // 2
if ok(m):
r = m
else:
l = m + 1
print(l)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long w, h, n;
cin >> w >> h >> n;
auto ok = здесь символ кв. скобка откр потом И потом закр (long long s) {
return (s / w) * (s / h) >= n;
};
long long l = 0, r = 1;
while (!ok(r)) r *= 2;
while (l < r) {
long long m = l + (r - l) / 2;
if (ok(m)) r = m;
else l = m + 1;
}
cout << l << "\n";
}
Разбор логики:
- Мы гарантируем, что
r уже “достаточно большой” (ok(r)=True).
- Бинпоиск сужает интервал, пока не останется минимальный True.
Бинпоиск по ответу (шаблон)
Что это
Это просто “бинпоиск по монотонному условию”, но ты сначала придумываешь переменную ответа.
Как применять (мышление)
- Ответ — число
ans.
- Умеем проверять
ok(ans).
- Доказываем монотонность.
- Бинпоиск.
Задача 1
Условие: есть n досок длины a[i]. Надо распилить на куски одинаковой длины, чтобы получить не меньше k кусков. Найти максимальную длину куска.
Монотонность: если длина куска x увеличивается → кусков получается меньше или равно.
Значит ok(x): pieces(x) >= k монотонно по x (True на малых x, False на больших).
Python
n, k = map(int, input().split())
a = list(map(int, input().split()))
def pieces(x):
return sum(v // x for v in a)
def ok(x):
return pieces(x) >= k
l, r = 1, max(a)
while l < r:
m = (l + r + 1) // 2 # ищем максимум True
if ok(m):
l = m
else:
r = m - 1
print(l)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
vector<long long> a(n);
long long mx = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
mx = max(mx, a[i]);
}
auto ok = здесь символ кв. скобка откр потом И потом закр(long long x) {
long long cnt = 0;
for (long long v : a) cnt += v / x;
return cnt >= k;
};
long long l = 1, r = mx;
while (l < r) {
long long m = (l + r + 1) / 2; // максимум True
if (ok(m)) l = m;
else r = m - 1;
}
cout << l << "\n";
}
Разбор: тут важна форма бинпоиска “на максимум True”: берём m вверх (l+r+1)//2, иначе зациклится.
Вещественный бинпоиск
Что это
Ответ — число с дробью. Мы не можем “дойти до равенства”, поэтому делаем фиксированное число итераций.
Где используется
- корни уравнений
- минимальная/максимальная величина с точностью
1e-6
Где НЕ использовать
- если можно найти точный ответ формулой (бывает)
- если функция не монотонна
Код
Python
def real_bin_search(l, r, ok, iters=80):
for _ in range(iters):
m = (l + r) / 2
if ok(m):
r = m
else:
l = m
return r
C++
double real_bin_search(double l, double r, auto ok) {
for (int it = 0; it < 100; ++it) {
double m = (l + r) / 2;
if (ok(m)) r = m;
else l = m;
}
return r;
}
Задача 1
Условие: найти sqrt(x) с точностью 1e-6.
Идея: m*m >= x — монотонно по m.
Python
x = float(input())
def ok(m):
return m*m >= x
ans = real_bin_search(0.0, max(1.0, x), ok)
print(f"{ans:.6f}")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
double x;
cin >> x;
auto ok = здесь символ кв. скобка откр потом И потом закр(double m) { return m*m >= x; };
double l = 0.0, r = max(1.0, x);
for (int it = 0; it < 100; ++it) {
double m = (l + r) / 2;
if (ok(m)) r = m;
else l = m;
}
cout.setf(std::ios::fixed);
cout << setprecision(6) << r << "\n";
}
Разбор: 100 итераций почти всегда достаточно для 1e-6.
Тернарный поиск
Что это
Ищет минимум/максимум унimодальной функции (одна “яма” или один “пик”).
Где используется
- оптимизация по одной переменной, когда функция выпуклая/вогнутая
Где НЕ использовать
- если много локальных минимумов/максимумов
Логика
Берём две точки m1 и m2. Если f(m1) <= f(m2), минимум не правее m2, иначе не левее m1.
Код
Python
def ternary_min(l, r, f, iters=120):
for _ in range(iters):
m1 = l + (r - l) / 3
m2 = r - (r - l) / 3
if f(m1) <= f(m2):
r = m2
else:
l = m1
return (l + r) / 2
C++
double ternary_min(double l, double r, auto f) {
for (int it = 0; it < 150; ++it) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) <= f(m2)) r = m2;
else l = m1;
}
return (l + r) / 2;
}
Задача 1
Условие: найти x, минимизирующий (x-a)^2 + (x-b)^2.
Решение: функция выпуклая (сумма квадратов), тернарка работает.
Python
a, b = map(float, input().split())
def f(x):
return (x-a)**2 + (x-b)**2
ans = ternary_min(min(a,b)-1000, max(a,b)+1000, f)
print(f"{ans:.6f}")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
double a, b;
cin >> a >> b;
auto f = здесь символ кв. скобка откр потом И потом закр(double x) {
double t1 = x - a;
double t2 = x - b;
return t1*t1 + t2*t2;
};
double l = min(a,b) - 1000;
double r = max(a,b) + 1000;
for (int it = 0; it < 150; ++it) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(m1) <= f(m2)) r = m2;
else l = m1;
}
double ans = (l + r) / 2;
cout.setf(std::ios::fixed);
cout << setprecision(6) << ans << "\n";
}
Разбор: у выпуклой функции один минимум, значит “сужение” всегда сохраняет его.
Поиск прыжками
Что это
Ищем блоками (обычно размер sqrt(n)), чтобы сократить число “дорогих доступов”.
Где используется
Редко на олимпиадах, но бывает: когда “доступ к элементу” дорогой (например, запрос к API/диску).
Где НЕ нужно
Если обычный бинпоиск доступен и быстрее.
Код
Python
import math
def jump_search(a, x):
n = len(a)
step = int(math.sqrt(n))
start = 0
while start < n and a[min(n-1, start + step - 1)] < x:
start += step
for i in range(start, min(n, start + step)):
if a[i] == x:
return i
return -1
C++
int jump_search(const vector<int>& a, int x) {
int n = (int)a.size();
int step = (int)sqrt(n);
int start = 0;
while (start < n && a[min(n - 1, start + step - 1)] < x) {
start += step;
}
for (int i = start; i < min(n, start + step); ++i) {
if (a[i] == x) return i;
}
return -1;
}
Задача 1
Та же, что и у бинпоиска: найти x в отсортированном массиве. (Это учебная задача, чтобы понимать метод.)
2) Префикс-суммы
1D префиксы
Что это
pref[i] = сумма первых i элементов (pref[0]=0).
Тогда сумма подотрезка [l, r] равна pref[r+1] - pref[l].
Где используется
- очень много запросов сумм на отрезках
- трюки с подотрезками: сумма = x, чётность, количество подотрезков по условию
Где НЕ использовать
- если часто меняем элементы (тогда нужны Fenwick/segment tree)
Логика
Мы заранее посчитали “сумму до каждой позиции”. Тогда любой отрезок — разность двух префиксов.
Код
Python
def build_pref(a):
pref = [0]*(len(a)+1)
for i, x in enumerate(a):
pref[i+1] = pref[i] + x
return pref
C++
vector<long long> build_pref(const vector<int>& a) {
vector<long long> pref(a.size() + 1, 0);
for (int i = 0; i < (int)a.size(); ++i) pref[i+1] = pref[i] + a[i];
return pref;
}
Дополнительные примеры и разборы
Задача A — сумма на отрезке с 0/1-индексацией
Условие: дан массив длины n. Затем q запросов в формате l r (0-индексация). Для каждого вывести сумму a[l..r].
Решение: считаем префикс pref, отвечаем pref[r+1] - pref[l].
Python
n, q = map(int, input().split())
a = list(map(int, input().split()))
pref = build_pref(a)
for _ in range(q):
l, r = map(int, input().split())
print(pref[r+1] - pref[l])
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + a[i];
while (q--) {
int l, r;
cin >> l >> r;
cout << (pref[r+1] - pref[l]) << "\n";
}
}
Задача B — есть ли подотрезок с суммой x (включая отрицательные числа)
Условие: дан массив (могут быть отрицательные). Нужно ответить YES/NO: существует ли подотрезок с суммой x.
Идея: при обходе считаем текущую префикс-сумму s. Если ранее встречался префикс s-x, то существует подотрезок.
Python
n, x = map(int, input().split())
a = list(map(int, input().split()))
seen = {0}
s = 0
ok = False
for v in a:
s += v
if (s - x) in seen:
ok = True
break
seen.add(s)
print("YES" if ok else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
unordered_set<long long> seen;
seen.reserve(n * 2);
seen.insert(0);
long long s = 0;
bool ok = false;
for (long long v : a) {
s += v;
if (seen.count(s - x)) {
ok = true;
break;
}
seen.insert(s);
}
cout << (ok ? "YES" : "NO") << "\n";
}
---
## Задачи на 1D префиксы
### Задача 1: сумма на отрезке (база)
**Условие:** дан массив длины `n`. Затем `q` запросов: `l r`. Для каждого вывести сумму `a[l..r]`.
**Решение:** строим префикс, отвечаем за O(1).
Python
```python
n, q = map(int, input().split())
a = list(map(int, input().split()))
pref = build_pref(a)
for _ in range(q):
l, r = map(int, input().split())
print(pref[r+1] - pref[l])
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + a[i];
while (q--) {
int l, r;
cin >> l >> r;
cout << (pref[r+1] - pref[l]) << "\n";
}
}
Логика: сумма на [0..r] минус сумма на [0..l-1].
Задача 2: есть ли подотрезок с суммой x (важно)
Условие: дан массив (могут быть отрицательные). Нужно ответить YES/NO: существует ли подотрезок с суммой x.
Идея:
Если pref[r] - pref[l] = x, то pref[l] = pref[r] - x. Значит при проходе слева направо можно хранить множество префиксов.
Python
n, x = map(int, input().split())
a = list(map(int, input().split()))
seen = {0}
s = 0
ok = False
for v in a:
s += v
if (s - x) in seen:
ok = True
break
seen.add(s)
print("YES" if ok else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
unordered_set<long long> seen;
seen.reserve(n * 2);
seen.insert(0);
long long s = 0;
bool ok = false;
for (long long v : a) {
s += v;
if (seen.count(s - x)) {
ok = true;
break;
}
seen.insert(s);
}
cout << (ok ? "YES" : "NO") << "\n";
}
Разбор логики: мы ищем два префикса, которые отличаются на x. Это ровно условие подотрезка.
2D префиксы
Что это
Для матрицы: pref[i][j] — сумма прямоугольника от (1,1) до (i,j).
Сумма любого прямоугольника за O(1) по формуле включения-исключения.
Где используется
- “много запросов суммы в прямоугольнике”
- плотность, картинки, тепловые карты, подматрицы
Где НЕ использовать
- если матрица часто обновляется
Формула
Для 1-индексации:
S(x1,y1,x2,y2) = pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]
Код
Python
def build_pref2(a):
n, m = len(a), len(a[0])
pref = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
pref[i][j] = a[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]
return pref
def rect_sum(pref, x1, y1, x2, y2):
return pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]
C++
vector<vector<long long>> build_pref2(const vector<vector<int>>& a) {
int n = (int)a.size(), m = (int)a[0].size();
vector<vector<long long>> pref(n+1, vector<long long>(m+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
pref[i][j] = a[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
}
}
return pref;
}
long long rect_sum(const vector<vector<long long>>& pref, int x1, int y1, int x2, int y2) {
return pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1];
}
Задача 1
Условие: дана матрица n×m. Дано q запросов прямоугольника (x1,y1,x2,y2) (1-индексация). Вывести сумму.
Решение: строим 2D префикс, отвечаем за O(1).
3) Сортировки и связанные приёмы
Сортировка вставками
Что это
Держим левую часть отсортированной, текущий элемент “вставляем” на правильное место.
Где используется
- маленькие массивы
- почти отсортированные
- как часть гибридных сортировок
Где НЕ использовать
- n большой (десятки тысяч и больше)
Задача 1
Условие: отсортировать n<=2000.
(Решение — код из определения, так как это сама сортировка.)
Пример реализации
Python
def insertion_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key
return a
C++
#include <vector>
using namespace std;
vector<int> insertion_sort(vector<int> a) {
int n = (int)a.size();
for (int i = 1; i < n; ++i) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
--j;
}
a[j+1] = key;
}
return a;
}
Сортировка подсчётом
Что это
Если значения в диапазоне [0..K], считаем частоты.
Где используется
- оценки 0..100
- символы (байты)
- события по небольшому диапазону
Где НЕ использовать
Задача 1
Условие: отсортировать оценки (0..100).
Решение: counting sort.
Python
def counting_sort(a, K=100):
cnt = [0]*(K+1)
for x in a:
cnt[x] += 1
res = []
for v in range(K+1):
res.extend([v]*cnt[v])
return res
C++
#include <vector>
using namespace std;
vector<int> counting_sort(const vector<int>& a, int K) {
vector<int> cnt(K+1, 0);
for (int x : a) ++cnt[x];
vector<int> res;
res.reserve(a.size());
for (int v = 0; v <= K; ++v) for (int t = 0; t < cnt[v]; ++t) res.push_back(v);
return res;
}
Merge sort
Что это
Разделяй и властвуй: сортируем половины и сливаем.
Где используется
- гарантированное
O(n log n)
- подсчёт инверсий
Где НЕ использовать
- когда память критична и нельзя O(n) буфер
Задача 1 (инверсии — очень полезно)
Условие: дан массив. Посчитать число инверсий (пар i<j, a[i]>a[j]).
Идея: при слиянии, когда берём элемент из правой половины раньше, чем оставшиеся в левой — он образует инверсии со всеми оставшимися.
Python
def count_inversions(a):
if len(a) <= 1:
return a, 0
mid = len(a)//2
left, inv_l = count_inversions(a[:mid])
right, inv_r = count_inversions(a[mid:])
i = j = 0
merged = []
inv = inv_l + inv_r
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
inv += (len(left) - i)
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inv
n = int(input())
a = list(map(int, input().split()))
_, inv = count_inversions(a)
print(inv)
C++
#include <bits/stdc++.h>
using namespace std;
long long merge_count(vector<int>& a, vector<int>& tmp, int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
long long inv = 0;
inv += merge_count(a, tmp, l, m);
inv += merge_count(a, tmp, m, r);
int i = l, j = m, k = l;
while (i < m && j < r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
tmp[k++] = a[j++];
inv += (m - i);
}
}
while (i < m) tmp[k++] = a[i++];
while (j < r) tmp[k++] = a[j++];
for (int p = l; p < r; ++p) a[p] = tmp[p];
return inv;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n), tmp(n);
for (int i = 0; i < n; ++i) cin >> a[i];
cout << merge_count(a, tmp, 0, n) << "\n";
}
Разбор логики:
- Внутри половин инверсии считаются рекурсией.
- Между половинами: когда выбираем правый элемент, он “перепрыгивает” через оставшиеся левые → добавляем их количество.
Quick sort
Что это
Опорный элемент pivot. Разделяем на части и рекурсируем.
Где используется
Где НЕ использовать
- если нельзя допустить
O(n^2) (без рандома)
Задача 1
Условие: отсортировать массив.
Совет: на контестах почти всегда лучше std::sort.
Реализация (рандомизированный опорный элемент)
Python
import random
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[random.randrange(len(a))]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + mid + quicksort(right)
C++ (in-place)
#include <bits/stdc++.h>
using namespace std;
void quicksort(vector<int>& a, int l, int r) {
if (l >= r) return;
int pivot = a[l + rand() % (r - l + 1)];
int i = l, j = r;
while (i <= j) {
while (a[i] < pivot) ++i;
while (a[j] > pivot) --j;
if (i <= j) swap(a[i++], a[j--]);
}
if (l < j) quicksort(a, l, j);
if (i < r) quicksort(a, i, r);
}
NSL/NSR (монотонный стек)
Что это
Для каждого i найти ближайший индекс слева/справа с меньшим значением.
Где используется
- “гистограмма” (макс прямоугольник)
- “на сколько я могу расшириться”
- границы сегмента для каждого элемента
Где НЕ использовать
- если нужно не ближайший меньший, а ближайший другой (тогда другой стек)
Задача 1 (тяжёлая и частая): максимальный прямоугольник в гистограмме
Условие: дан массив высот h[0..n-1]. Найти максимальную площадь прямоугольника, полностью лежащего под гистограммой.
Идея: для каждого столбика i найти границы, куда он может расшириться, пока высота не станет меньше h[i].
L[i] = индекс ближайшего меньшего слева (или -1)R[i] = индекс ближайшего меньшего справа (или n)
Тогда ширина = R[i]-L[i]-1, площадь = h[i]*ширина.
Python
def max_hist_area(h):
n = len(h)
L = [-1]*n
st = []
for i in range(n):
while st and h[st[-1]] >= h[i]:
st.pop()
L[i] = st[-1] if st else -1
st.append(i)
R = [n]*n
st = []
for i in range(n-1, -1, -1):
while st and h[st[-1]] >= h[i]:
st.pop()
R[i] = st[-1] if st else n
st.append(i)
ans = 0
for i in range(n):
ans = max(ans, h[i]*(R[i]-L[i]-1))
return ans
n = int(input())
h = list(map(int, input().split()))
print(max_hist_area(h))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<long long> h(n);
for (int i = 0; i < n; ++i) cin >> h[i];
vector<int> L(n, -1), R(n, n);
vector<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
long long width = R[i] - L[i] - 1;
ans = max(ans, h[i] * width);
}
cout << ans << "\n";
}
Разбор логики: монотонный стек гарантирует, что каждый индекс добавляется/удаляется максимум 1 раз → O(n).
Пересечение отрезков на прямой
Что это
Есть [l1,r1] и [l2,r2]. Пересечение есть, если max(l1,l2) <= min(r1,r2).
Задача 1
Условие: для каждого из q запросов определить, пересекаются ли два отрезка.
Python
def inter(l1, r1, l2, r2):
return max(l1, l2) <= min(r1, r2)
q = int(input())
for _ in range(q):
l1, r1, l2, r2 = map(int, input().split())
print("YES" if inter(l1, r1, l2, r2) else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q; cin >> q;
while (q--) {
long long l1,r1,l2,r2;
cin >> l1 >> r1 >> l2 >> r2;
cout << (max(l1,l2) <= min(r1,r2) ? "YES" : "NO") << "\n";
}
}
4) Базовые структуры данных
Массив
Что это
Непрерывный блок памяти. Доступ по индексу O(1).
Где используется
Почти везде.
Задача 1
Условие: найти максимум массива.
(Это учебная задача: понимаем, что один проход O(n).)
Стек
Что это
LIFO. Подходит, когда нужно “помнить последний незакрытый элемент”.
Где используется
- скобки
- DFS (итеративно)
- монотонные стеки (NSL/NSR)
Задача 1
Условие: проверить корректность скобочной последовательности из ()[]{} .
Python
s = input().strip()
match = {')':'(', ']':'[', '}':'{'}
st = []
ok = True
for c in s:
if c in '([{':
st.append(c)
else:
if not st or st[-1] != match.get(c, ''):
ok = False
break
st.pop()
if st:
ok = False
print("YES" if ok else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
unordered_map<char,char> match{{')','('},{']','['},{'}','{'}};
vector<char> st;
bool ok = true;
for (char c : s) {
if (c=='(' || c=='[' || c=='{') st.push_back(c);
else {
if (st.empty() || st.back() != match[c]) {
ok = false;
break;
}
st.pop_back();
}
}
if (!st.empty()) ok = false;
cout << (ok ? "YES" : "NO") << "\n";
}
Логика: любая закрывающая должна закрыть именно последнюю незакрытую открывающую.
Очередь
Что это
FIFO. Ключевой инструмент BFS.
Задача 1
Условие: дан невзвешенный граф, найти расстояние от s до всех вершин.
(Это BFS — см. раздел BFS.)
Дополнительные структуры и примеры
Deque (двусторонняя очередь)
Что это
Позволяет вставлять/удалять элементы с обоих концов за O(1). Удобна для 0-1 BFS (deque с push_front/push_back).
Python
from collections import deque
d = deque()
d.append(1)
d.appendleft(2)
v = d.popleft()
C++
#include <deque>
using namespace std;
deque<int> d;
d.push_back(1);
d.push_front(2);
int v = d.front(); d.pop_front();
Hash map / словарь
Что это
Ассоциативный контейнер для быстрого доступа по ключу (среднее O(1)). В Python — dict, в C++ — unordered_map.
Python
mp = {}
mp['a'] = 10
print(mp.get('b', 0))
C++
#include <unordered_map>
using namespace std;
unordered_map<string,int> mp;
mp["a"] = 10;
if (mp.count("b")) {}
Приоритетная очередь (heap)
Где используется
Для Dijkstra, поиска k-элементов, планировщиков.
Python
import heapq
pq = []
heapq.heappush(pq, (5, 'a'))
val = heapq.heappop(pq)
C++
#include <queue>
using namespace std;
priority_queue<pair<int,string>, vector<pair<int,string>>, greater<>> pq;
pq.emplace(5, "a");
auto val = pq.top(); pq.pop();
5) Динамическое программирование
DP 1D (идея + как формулировать)
Что это
DP — это “табличка ответов на подзадачи”.
1D DP: состояние определяется одним параметром (обычно индексом).
Как понять, что тут DP
Сигналы:
- “максимум/минимум/количество способов”
- “пройти по позиции i”
- “выбор: взять/не взять, перейти так/иначе”
Как строить DP (шаги)
- Определи состояние
dp[i] (что оно значит).
- Определи переходы (откуда приходит).
- База.
- Порядок заполнения.
Задача 1
Условие: лестница из n ступеней. Можно идти на 1 или 2 ступени. Сколько способов дойти до n?
Python
n = int(input())
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
dp[i] = dp[i-1]
if i >= 2:
dp[i] += dp[i-2]
print(dp[n])
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<long long> dp(n+1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i-1];
if (i >= 2) dp[i] += dp[i-2];
}
cout << dp[n] << "\n";
}
Разбор: dp[i] = способы попасть на i. На i приходим из i-1 и i-2.
Дополнительные примеры и разборы
Задача A — лестница с шагами 1 или 2 (быстрое решение)
Условие: лестница из n ступеней. Можно подниматься на 1 или 2 ступени. Сколько способов добраться до n?
Решение: dp[0]=1, dp[i]=dp[i-1]+dp[i-2] для i>=1.
Python
n = int(input())
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
dp[i] = dp[i-1]
if i >= 2:
dp[i] += dp[i-2]
print(dp[n])
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<long long> dp(n+1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i-1];
if (i >= 2) dp[i] += dp[i-2];
}
cout << dp[n] << "\n";
}
Задача B — рюкзак достижимости сумм (1D DP пример)
Условие: даны n предметов с весами w[i]. Можно ли набрать сумму S? (Каждый предмет можно взять не более одного раза.)
Идея: используем булевый dp[s] — достижимость суммы s. Проходим по предметам и обновляем dp справа-налево.
Python
n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [False] * (S+1)
dp[0] = True
for weight in w:
for s in range(S, weight-1, -1):
if dp[s-weight]:
dp[s] = True
print("YES" if dp[S] else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, S;
cin >> n >> S;
vector<int> w(n);
for (int i = 0; i < n; ++i) cin >> w[i];
vector<char> dp(S+1, 0);
dp[0] = 1;
for (int weight : w) {
for (int s = S; s >= weight; --s) {
if (dp[s-weight]) dp[s] = 1;
}
}
cout << (dp[S] ? "YES" : "NO") << "\n";
}
Задача C — 0/1 рюкзак (максимум ценности)
Условие: даны n предметов, каждый имеет вес w[i] и ценность v[i]. Вместимость рюкзака W. Нужно максимизировать суммарную ценность.
Идея: dp[s] — максимум ценности при суммарном весе s. Обновляем по предметам справа-налево.
Python
n, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0]*(W+1)
for i in range(n):
wt = w[i]
val = v[i]
for s in range(W, wt-1, -1):
dp[s] = max(dp[s], dp[s-wt] + val)
print(max(dp))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W; cin >> n >> W;
vector<int> w(n), v(n);
for (int i = 0; i < n; ++i) cin >> w[i];
for (int i = 0; i < n; ++i) cin >> v[i];
vector<long long> dp(W+1, 0);
for (int i = 0; i < n; ++i) {
for (int s = W; s >= w[i]; --s) dp[s] = max(dp[s], dp[s-w[i]] + v[i]);
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
DP 2D
Рюкзаки — полный разбор (формат: что, когда, код, примеры, логика)
Что это (очень просто)
Рюкзак — класс задач, где у предметов есть вес и, возможно, ценность. Надо выбрать подмножество предметов под ограничение по весу, чтобы выполнить цель (достичь точной суммы, максимизировать ценность и т.д.).
Когда стоит применять
- когда каждый предмет можно взять не более одного раза → 0/1 рюкзак;
- когда предметы можно брать неограниченно → complete/unbounded рюкзак;
- когда нужно только узнать достижимость сумм → булевый DP (subset-sum);
- подходит для задач с ограничением
W до ~1e6 и n не очень большим (память и время зависят от W).
Когда не стоит
- если
W очень большой (например, 1e9) и нет дополнительных ограничений — используйте meet-in-the-middle или DP по сумме ценностей;
- если предметов слишком много и
W большой — рассмотрите другие подходы.
- Достижимость суммы (subset-sum, 0/1)
Условие: даны n предметов с весами w[i]. Можно ли набрать сумму S? Каждый предмет можно взять не более одного раза.
Идея: dp[s] — достижимость суммы s. Для каждого предмета обновляем dp справа-налево: если dp[s-w] было достижимо, то dp[s] становится достижимым.
Python
n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [False] * (S + 1)
dp[0] = True
for weight in w:
for s in range(S, weight - 1, -1):
if dp[s - weight]:
dp[s] = True
print("YES" if dp[S] else "NO")
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, S;
if (!(cin >> n >> S)) return 0;
vector<int> w(n);
for (int i = 0; i < n; ++i) cin >> w[i];
vector<char> dp(S + 1, 0);
dp[0] = 1;
for (int weight : w) {
for (int s = S; s >= weight; --s) if (dp[s - weight]) dp[s] = 1;
}
cout << (dp[S] ? "YES" : "NO") << '\n';
}
Пример применения
n=4, w=[3,1,4,2], S=6 → YES (3+1+2);
Логика подробно
dp[0]=True — пустое подмножество; при проходе по предметам мы комбинируем новые веса с уже достижимыми; обновление справа-налево гарантирует, что каждый предмет используется не более одного раза.
- 0/1 рюкзак (максимум ценности)
Условие: даны n предметов, вес w[i], ценность v[i], вместимость W. Найти максимум суммарной ценности.
Идея: одномерный dp[s] — максимум ценности при суммарном весе s. Для каждого предмета обновляем dp справа-налево по весу.
Python
n, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0] * (W + 1)
for i in range(n):
wt = w[i]
val = v[i]
for s in range(W, wt - 1, -1):
if dp[s - wt] + val > dp[s]:
dp[s] = dp[s - wt] + val
print(max(dp))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i = 0; i < n; ++i) cin >> w[i];
for (int i = 0; i < n; ++i) cin >> v[i];
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; ++i) {
for (int s = W; s >= w[i]; --s) dp[s] = max(dp[s], dp[s - w[i]] + v[i]);
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
Пример
n=3, W=50, items: (10,60),(20,100),(30,120) → оптимум 220 (взять первые два).
Логика подробно
dp[s] содержит лучший результат для веса ровно s после рассмотренных предметов. Обновление справа-налево гарантирует корректное использование каждого предмета не более одного раза. Ответ — максимум по dp[0..W].
- Неограниченный рюкзак (unbounded)
Идея: если предметы можно брать неограниченно, для каждого предмета идём по весам слева-направо и используем текущие значения dp[s - w[i]] несколько раз.
Python
n, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0] * (W + 1)
for i in range(n):
for s in range(w[i], W + 1):
dp[s] = max(dp[s], dp[s - w[i]] + v[i])
print(max(dp))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i = 0; i < n; ++i) cin >> w[i] >> v[i];
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; ++i) for (int s = w[i]; s <= W; ++s) dp[s] = max(dp[s], dp[s - w[i]] + v[i]);
cout << *max_element(dp.begin(), dp.end()) << '\n';
}
DP 2D
Что это
Состояние dp[i][j] зависит от двух параметров: позиция+вторая характеристика.
Где используется
- LCS
- рюкзак
- задачи на решётке
Задача 1
Условие: в клетчатой таблице n×m можно ходить только вправо и вниз. Сколько путей из (1,1) в (n,m)?
(Код и объяснение — стандартное заполнение таблицы по зависимостям.)
НОП / LCS
Что это
Длина наибольшей общей подпоследовательности двух строк.
Где используется
- сравнение последовательностей
- близость строк
Где НЕ использовать
- большие строки (n,m ~ 1e5) — обычный DP O(nm) не пройдёт
Задача 1 (классика)
Условие: даны строки a и b (длины <= 2000). Найти длину LCS.
Python
a = input().strip()
b = input().strip()
n, m = len(a), len(b)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
int n = (int)a.size(), m = (int)b.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout << dp[n][m] << "\n";
}
Разбор логики:
dp[i][j] — LCS для префиксов. Если последние символы равны, то продлеваем диагональ. Иначе выбираем лучшее из двух “пропусков”.
DP 2D — дополнительный пример
Задача: в клетчатой таблице n×m можно ходить только вправо и вниз. Сколько путей из (1,1) в (n,m)? Числа могут быть большими — вывести по модулю MOD.
Идея: dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD, dp[1][1]=1.
Python
MOD = 10**9+7
n, m = map(int, input().split())
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
continue
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD
print(dp[n][m])
C++
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
dp[1][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i == 1 && j == 1) continue;
dp[i][j] = ( (long long)dp[i-1][j] + dp[i][j-1] ) % MOD;
}
}
cout << dp[n][m] << "\n";
}
LCS — восстановление и пример с восстановлением
Задача: даны строки a и b. Найти не только длину, но и саму LCS (одну из). Длины ≤ 2000.
Идея: заполнить таблицу dp, затем пройти назад от dp[n][m], восстанавливая символы.
Python
a = input().strip()
b = input().strip()
n, m = len(a), len(b)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = n, m
res = []
while i > 0 and j > 0:
if a[i-1] == b[j-1]:
res.append(a[i-1])
i -= 1
j -= 1
elif dp[i-1][j] >= dp[i][j-1]:
i -= 1
else:
j -= 1
res.reverse()
print(dp[n][m])
print(''.join(res))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
int n = (int)a.size(), m = (int)b.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
int i = n, j = m;
string res;
while (i > 0 && j > 0) {
if (a[i-1] == b[j-1]) { res.push_back(a[i-1]); --i; --j; }
else if (dp[i-1][j] >= dp[i][j-1]) --i;
else --j;
}
reverse(res.begin(), res.end());
cout << dp[n][m] << "\n" << res << "\n";
}
LIS — O(n log n) и пояснение
Задача: найти длину наибольшей возрастающей подпоследовательности (LIS) за O(n log n).
Идея: массив d хранит минимально возможный хвост для каждой длины подпоследовательности. Для каждого x ищем позицию i = lower_bound(d, x) и заменяем d[i]=x или добавляем.
Python
import bisect
n = int(input())
a = list(map(int, input().split()))
d = []
for x in a:
i = bisect.bisect_left(d, x)
if i == len(d):
d.append(x)
else:
d[i] = x
print(len(d))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> d;
for (int x : a) {
auto it = lower_bound(d.begin(), d.end(), x);
if (it == d.end()) d.push_back(x);
else *it = x;
}
cout << (int)d.size() << "\n";
}
НВП / LIS
Что это
Длина наибольшей возрастающей подпоследовательности.
Где используется
- “максимальная цепочка”
- оптимизация выбора по порядку
Задача 1
Условие: найти длину LIS за O(n log n).
Python
import bisect
n = int(input())
a = list(map(int, input().split()))
d = []
for x in a:
i = bisect.bisect_left(d, x)
if i == len(d):
d.append(x)
else:
d[i] = x
print(len(d))
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> d;
for (int x : a) {
auto it = lower_bound(d.begin(), d.end(), x);
if (it == d.end()) d.push_back(x);
else *it = x;
}
cout << (int)d.size() << "\n";
}
Разбор логики: d[len] — минимальный возможный “хвост” подпоследовательности длины len+1. Чем хвост меньше, тем легче продолжить.
Восстановление ответа
Что это
Мы хотим вывести не только значение, но и путь/набор элементов.
Где используется
- LCS восстановить строку
- рюкзак восстановить выбранные предметы
Задача 1 (LCS восстановить)
(Тут используется движение назад по dp, выбирая, откуда пришли.)
6) Жадные алгоритмы
Как распознать и доказать жадность
Что это
Жадность = каждый шаг берём “лучшее локально”. Работает не всегда.
Когда стоит применять
Если можно доказать хотя бы одно:
- обменный аргумент: любое оптимальное решение можно превратить в жадное без ухудшения
- оптимальная подструктура + жадный выбор
Где часто ломается
- “сдача монет” при странных номиналах
- “возьмём самый большой/самый дешёвый” без доказательства
Задача 1 (классика): максимум непересекающихся отрезков
Условие: есть отрезки [l,r]. Выбрать максимум непересекающихся.
Жадный выбор: сортируем по r и берём, когда можно.
Python
n = int(input())
seg = [tuple(map(int, input().split())) for _ in range(n)]
seg.sort(key=lambda x: x[1])
ans = 0
last_end = -10**18
for l, r in seg:
if l >= last_end:
ans += 1
last_end = r
print(ans)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<pair<long long,long long>> seg(n);
for (int i = 0; i < n; ++i) cin >> seg[i].first >> seg[i].second;
sort(seg.begin(), seg.end(), кв откр кв закр (auto знак и A, auto знак и B){
return A.second < B.second;
});
long long last_end = (long long)-4e18;
int ans = 0;
for (auto [l, r] : seg) {
if (l >= last_end) {
ans++;
last_end = r;
}
}
cout << ans << "\n";
}
Разбор: самый ранний конец оставляет максимум места для остальных.
Пример 2 — дробный рюкзак (fractional knapsack)
Условие: даны предметы с весом w[i] и ценностью v[i]. Можно брать дробные части предметов. Как максимизировать ценность при вместимости W?
Жадная идея: сортировать предметы по плотности v[i]/w[i] по убыванию и брать пока есть место.
Python
n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
items.sort(key=lambda x: x[1]/x[0], reverse=True)
res = 0.0
rem = W
for wt, val in items:
take = min(rem, wt)
res += take * (val / wt)
rem -= take
if rem == 0: break
print(res)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long W; cin >> n >> W;
vector<pair<double, pair<long long,long long>>> items;
for (int i = 0; i < n; ++i) {
long long w,v; cin >> w >> v;
items.push_back({(double)v / w, {w,v}});
}
sort(items.begin(), items.end(), кв откр кв закр (auto знак иA, auto знак иB){ return A.first > B.first; });
double res = 0.0;
long long rem = W;
for (auto &it : items) {
long long wt = it.second.first;
long long val = it.second.second;
long long take = min(rem, wt);
res += take * (it.first);
rem -= take;
if (rem == 0) break;
}
cout.setf(std::ios::fixed);
cout << setprecision(6) << res << "\n";
}
Внимание: жадность может ломаться (пример — сдача)
Если номиналы монет заданы произвольно, жадный алгоритм "взять максимально возможное количество больших монет" не всегда даёт оптимальное число монет. Для корректности нужно доказать обменный аргумент.
7) Графы
Представление графа (списки смежности)
Что это
g[v] хранит список соседей. Это почти всегда лучший формат на олимпиадах.
Шаблоны
Невзвешенный:
- Python:
g = [[] for _ in range(n)]
- C++:
vector<vector<int>> g(n)
Взвешенный:
- Python:
g[v].append((to, w))
- C++:
vector<vector<pair<int,int>>> g(n)
DFS: компоненты, цикл, диаметр дерева
Что это
DFS идёт глубоко.
Где используется
- компоненты связности
- поиск цикла (через цвета)
- диаметр дерева (2 обхода)
Задача 1: число компонент связности
Условие: дан неориентированный граф. Найти число компонент.
Идея: запускаем DFS из каждой непосещённой вершины.
Python
import sys
sys.setrecursionlimit(1_000_000)
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
u -= 1; v -= 1
g[u].append(v)
g[v].append(u)
used = [False]*n
def dfs(v):
used[v] = True
for to in g[v]:
if not used[to]:
dfs(to)
cnt = 0
for i in range(n):
if not used[i]:
cnt += 1
dfs(i)
print(cnt)
C++
#include <bits/stdc++.h>
using namespace std;
void dfs(int v, const vector<vector<int>>& g, vector<int>& used) {
used[v] = 1;
for (int to : g[v]) if (!used[to]) dfs(to, g, used);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> used(n, 0);
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
cnt++;
dfs(i, g, used);
}
}
cout << cnt << "\n";
}
Разбор: каждый запуск DFS “закрашивает” одну компоненту.
BFS обычный
Что это
BFS идёт слоями и даёт кратчайшие пути в невзвешенном графе.
Задача 1: кратчайшее расстояние
Условие: дан граф и вершины s, t. Найти минимальное число рёбер.
(Решение — стандартный BFS, dist[t].)
Python
from collections import deque
def bfs_dist(n, g, s):
INF = 10**9
dist = [INF]*n
q = deque([s])
dist[s] = 0
while q:
v = q.popleft()
for to in g[v]:
if dist[to] == INF:
dist[to] = dist[v] + 1
q.append(to)
return dist
C++
#include <vector>
#include <queue>
using namespace std;
vector<int> bfs_dist(int n, const vector<vector<int>>& g, int s) {
const int INF = 1e9;
vector<int> dist(n, INF);
queue<int> q;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int to : g[v]) if (dist[to] == INF) {
dist[to] = dist[v] + 1;
q.push(to);
}
}
return dist;
}
Мультистарт BFS
Что это
Стартуем одновременно из нескольких вершин.
Задача 1
Условие: есть k источников. Найти расстояние до ближайшего источника для каждой вершины.
(Решение — BFS, где в очереди сразу все источники с dist=0.)
0-1 BFS
Что это
Кратчайший путь при весах 0/1. Используем deque.
Где используется
“бесплатный переход / платный переход”, “переключить/не переключить”.
Задача 1 (важная)
Условие: граф, веса 0 или 1, найти кратчайшее расстояние от s до t.
(Решение — 0-1 BFS, как в разделе.)
Python
from collections import deque
def zero_one_bfs(n, g, s):
INF = 10**18
dist = [INF]*n
dq = deque([s])
dist[s] = 0
while dq:
v = dq.popleft()
for to, w in g[v]:
nd = dist[v] + w
if nd < dist[to]:
dist[to] = nd
if w == 0:
dq.appendleft(to)
else:
dq.append(to)
return dist
C++
#include <deque>
#include <vector>
using namespace std;
vector<long long> zero_one_bfs(int n, const vector<vector<pair<int,int>>>& g, int s) {
const long long INF = (long long)4e18;
vector<long long> dist(n, INF);
deque<int> dq;
dq.push_back(s);
dist[s] = 0;
while (!dq.empty()) {
int v = dq.front(); dq.pop_front();
for (auto [to,w] : g[v]) {
long long nd = dist[v] + w;
if (nd < dist[to]) {
dist[to] = nd;
if (w == 0) dq.push_front(to);
else dq.push_back(to);
}
}
}
return dist;
}
1-2 BFS
Что это
Если веса 1 или 2, можно заменить ребро веса 2 двумя ребрами веса 1 через фиктивную вершину, затем BFS.
Задача 1
Условие: веса 1/2, найти кратчайшее расстояние.
Идея: преобразуем в невзвешенный граф.
Подробно и реализация
Когда применять: веса ограничены {1,2} — можно получить быстрее, чем общий Dijkstra, за счёт простого преобразования или использования deque/двухуровневого обхода.
Идея 1 (фиктивные вершины): заменить каждое ребро весом 2 парой рёбер весом 1 через новую вершину; после этого обычный BFS даёт ответ. Это увеличивает число вершин, но для небольших графов работает.
Идея 2 (оптимальнее): преобразовать ребро весом 2 в два шага с использованием deque или применять 0-1 BFS с весами 0/1 после редукции (пересчитать шкалу). Ниже — простая реализация через преобразование в невзвешенный граф и BFS.
Python
from collections import deque
def one_two_bfs(n, edges, s):
g = [[] for _ in range(n)]
for u,v,w in edges:
if w == 1:
g[u].append(v)
g[v].append(u)
else:
idx = len(g)
g.append([])
g[u].append(idx)
g[idx].append(v)
g[v].append(idx)
g[idx].append(u)
N = len(g)
dist = [-1]*N
q = deque([s])
dist[s] = 0
while q:
v = q.popleft()
for to in g[v]:
if dist[to] == -1:
dist[to] = dist[v] + 1
q.append(to)
return dist[:n]
C++
#include <bits/stdc++.h>
using namespace std;
vector<int> one_two_bfs(int n, const vector<tuple<int,int,int>>& edges, int s) {
vector<vector<int>> g(n);
for (auto [u,v,w] : edges) {
if (w == 1) {
g[u].push_back(v);
g[v].push_back(u);
} else {
int idx = (int)g.size();
g.emplace_back();
g[u].push_back(idx);
g[idx].push_back(v);
g[v].push_back(idx);
g[idx].push_back(u);
}
}
int N = (int)g.size();
vector<int> dist(N, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
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); }
}
dist.resize(n);
return dist;
}
Разбор логики
- преобразование даёт невзвешенный граф, где путь минимизирует число рёбер (каждое ребро весом 2 стало двумя рёбрами), BFS даёт минимальное число единичных шагов; результат делён на 1 даёт суммарную длину.
1-k BFS (Dial)
Что это
Dijkstra без кучи, если веса маленькие 1..k.
Задача 1
Условие: веса 1..5, найти кратчайшие пути.
Идея: бакеты по расстоянию.
Подробно и реализация (Dial)
Когда применять: максимальный вес ребра K небольшой (например, ≤1000) и граф плотный по расстоянию; Dial эффективнее обычной кучи при малых K.
Идея: расстояния хранятся в бакетах bucket[d] для каждого возможного расстояния d. Поддерживаем текущую позицию cur. Вставляем вершину в бакет по её расстоянию; извлекаем из наименьшего непустого бакета. Диапазон бакетов ограничен K*(n-1) в худшем случае.
Python (Dial)
from collections import deque
def dial(n, g, s, K):
INF = 10**18
maxd = K * (n - 1) + 1
dist = [INF]*n
buckets = [deque() for _ in range(maxd)]
dist[s] = 0
buckets[0].append(s)
cur = 0
while cur < maxd:
while cur < maxd and not buckets[cur]:
cur += 1
if cur >= maxd: break
v = buckets[cur].popleft()
if dist[v] != cur: continue
for to, w in g[v]:
nd = cur + w
if nd < dist[to]:
dist[to] = nd
if nd < maxd:
buckets[nd].append(to)
return dist
C++ (Dial)
#include <bits/stdc++.h>
using namespace std;
vector<long long> dial(int n, const vector<vector<pair<int,int>>>& g, int s, int K) {
const long long INF = (long long)4e18;
int maxd = K * (n - 1) + 1;
vector<long long> dist(n, INF);
vector<deque<int>> buckets(maxd);
dist[s] = 0;
buckets[0].push_back(s);
int cur = 0;
while (cur < maxd) {
while (cur < maxd && buckets[cur].empty()) ++cur;
if (cur >= maxd) break;
int v = buckets[cur].front(); buckets[cur].pop_front();
if (dist[v] != cur) continue;
for (auto [to,w] : g[v]) {
int nd = cur + w;
if (nd < dist[to]) {
dist[to] = nd;
if (nd < maxd) buckets[nd].push_back(to);
}
}
}
return dist;
}
Логика подробно
- для каждого возможного расстояния поддерживаем список вершин; извлечение идёт из минимального доступного бакета; сложность амортизированно O(n + m + K * n).
Дейкстра
Что это
Кратчайшие пути при неотрицательных весах.
Где используется
дороги/времена/стоимости.
Где НЕЛЬЗЯ
есть отрицательные ребра.
Задача 1
Условие: взвешенный граф, найти кратчайшее расстояние s->t.
(Решение — Dijkstra.)
Python
import heapq
def dijkstra(n, g, s):
INF = 10**18
dist = [INF]*n
dist[s] = 0
pq = [(0, s)]
while pq:
d, v = heapq.heappop(pq)
if d != dist[v]:
continue
for to, w in g[v]:
nd = d + w
if nd < dist[to]:
dist[to] = nd
heapq.heappush(pq, (nd, to))
return dist
C++
#include <vector>
#include <queue>
using namespace std;
vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& g, int s) {
const long long INF = (long long)4e18;
vector<long long> dist(n, INF);
dist[s] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (d != dist[v]) continue;
for (auto [to,w] : g[v]) {
long long nd = d + w;
if (nd < dist[to]) {
dist[to] = nd;
pq.emplace(nd, to);
}
}
}
return dist;
}
Дополнительно — когда применять и сложность
- работает для неотрицательных весов; если есть отрицательные ребра, используйте Bellman-Ford или алгоритмы на DAG;
- сложность: O((n + m) log n) при использовании кучи; для небольших целых весов можно использовать Dial/бакеты.
Подробная логика (разжёвано)
- Инициализируем
dist[s]=0, остальные INF.
- Поддерживаем минимум в куче по текущей оценке расстояния до вершины.
- На извлечении вершины
v с расстоянием d все рёбра v->to дают потенциальное улучшение nd = d + w.
- Если
nd < dist[to], обновляем dist[to] и кладём (nd,to) в кучу.
- Так как каждая вершина может быть обновлена много раз, но в куче хранится старое значение, при извлечении мы проверяем
d != dist[v] и пропускаем неактуальные записи.
Частые ошибки
- забыть обработать случай, когда
dist[t] остаётся INF (недостижимо);
- запускать на графе с отрицательными рёбрами — результат неверен.
Топологическая сортировка
Что это
Порядок выполнения задач без циклов.
Задача 1
Условие: дан DAG. Вывести топологический порядок или -1, если есть цикл.
(Решение — Кана, если порядка нет → цикл.)
Python
from collections import deque
def kahn_toposort(n, g):
indeg = [0]*n
for v in range(n):
for to in g[v]:
indeg[to] += 1
q = deque([i for i in range(n) if indeg[i]==0])
order = []
while q:
v = q.popleft()
order.append(v)
for to in g[v]:
indeg[to] -= 1
if indeg[to]==0:
q.append(to)
if len(order) != n:
return []
return order
C++
#include <vector>
#include <queue>
using namespace std;
vector<int> kahn_toposort(int n, const vector<vector<int>>& g) {
vector<int> indeg(n,0);
for (int v = 0; v < n; ++v) for (int to : g[v]) ++indeg[to];
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) return {};
return order;
}
КСС (SCC) + конденсация + DP на КСС
Что это
Сжимаем циклы в компоненты, получаем DAG.
Где используется
- максимальные пути при циклах
- достижимость “с учётом циклов”
Задача 1 (тяжёлая и очень полезная)
Условие: ориентированный граф, у каждой вершины вес. Найти максимальную сумму весов по пути.
Идея:
- Найти КСС.
- Сжать граф в DAG КСС.
- Вес компоненты = сумма весов вершин внутри.
- DP по топологическому порядку на DAG.
(Чтобы не раздувать листинг в 5 раз: реализация КСС (Косарайю) и DP — приведены ниже.)
Когда применять
- когда граф ориентированный и внутри циклов поведение “сворачивается” (все вершины компоненты взаимодостижимы) — удобно сжимать компоненты и работать на DAG;
- полезно при задачах на максимальную сумму/достижимость, где циклы мешают простому DP.
Пример задачи с решением
Условие: ориентированный граф, каждой вершине присвоен вес a[v]. Нужно найти максимальную сумму весов вдоль пути (можно проходить через циклы, но каждую вершину считать только один раз).
Решение (шаги):
- Найти все сильные компоненты (SCC) и сжать граф: заменить каждую SCC на одну вершину.
- Для каждой компоненты вычислить
comp_weight[c] — сумма a[v] по вершинам в компоненте.
- Получается DAG; на нём запускаем DP:
dp[c] = максимальная сумма, начиная из компоненты c. Для компоненты c: dp[c] = comp_weight[c] + max(dp[to]) по исходящим рёбрам c->to.
- Ответ = max по всем
dp[c].
Сложность: O(n + m) для поиска SCC + O(n + m) для DP на DAG.
Логика (детально)
- Косарайю: первый DFS собирает порядок выхода вершин; второй DFS на транспонированном графе в порядке убывания времени выхода даёт компоненты. Это работает потому, что вершины с наибольшим временем выхода принадлежат компонентам без исходящих рёбер в ещё не обработанные компоненты.
- Сжатие даёт DAG: внутри компоненты вершины взаимодостижимы, поэтому путь, проходящий через компоненту, может суммировать все её вершины разом.
- DP на DAG прост: порядок топологический, переходим от концов к началам и аккумулируем максимумы.
Python (Kosaraju)
def kosaraju(n, g):
order = []
used = [False]*n
def dfs1(v):
used[v] = True
for to in g[v]:
if not used[to]: dfs1(to)
order.append(v)
for v in range(n):
if not used[v]: dfs1(v)
gt = [[] for _ in range(n)]
for v in range(n):
for to in g[v]:
gt[to].append(v)
comp = [-1]*n
cid = 0
def dfs2(v):
comp[v] = cid
for to in gt[v]:
if comp[to] == -1: dfs2(to)
for v in reversed(order):
if comp[v] == -1:
dfs2(v)
cid += 1
return cid, comp
C++ (Kosaraju)
#include <vector>
using namespace std;
pair<int, vector<int>> kosaraju(int n, const vector<vector<int>>& g) {
vector<int> order;
vector<char> used(n, 0);
function<void(int)> dfs1 = здесь символ кв. скобка откр потом И потом закр(int v) {
used[v] = 1;
for (int to : g[v]) if (!used[to]) dfs1(to);
order.push_back(v);
};
for (int i = 0; i < n; ++i) if (!used[i]) dfs1(i);
vector<vector<int>> gt(n);
for (int v = 0; v < n; ++v) for (int to : g[v]) gt[to].push_back(v);
vector<int> comp(n, -1);
int cid = 0;
function<void(int)> dfs2 = здесь символ кв. скобка откр потом И потом закр (int v) {
comp[v] = cid;
for (int to : gt[v]) if (comp[to]==-1) dfs2(to);
};
for (int i = (int)order.size()-1; i >= 0; --i) {
int v = order[i];
if (comp[v] == -1) { dfs2(v); ++cid; }
}
return {cid, comp};
}
Эйлеров путь и цикл (Хиерхольцер)
Что это
Путь по всем рёбрам ровно один раз.
Где используется
маршрутизация “использовать каждое ребро”.
Задача 1
Условие: дан неориентированный граф. Определить, существует ли Эйлеров цикл.
Идея: все степени чётные и граф связный (если игнорировать изолированные вершины).
Когда использовать
- нужен путь или цикл, проходящий по каждому ребру ровно один раз (маршрутизация, задачи на обход рёбер);
- для ориентированного графа условие: в каждой вершине входящая степень равна исходящей и граф связен по ребрам (в компоненте реберной связности);
- для неориентированного: все степени чётные и граф реберно связен (игнорировать изолированные вершины).
Подробная логика алгоритма Hierholzer
- Начинаем из вершины, у которой есть рёбра (или из заданной стартовой вершины).
- Идём по неиспользованным рёбрам, пока не застрянем в вершине без доступных рёбер — получаем цикл.
- Если остались неиспользованные рёбра, переходим к вершине на уже построенном пути, у которой есть неиспользованные рёбра, и повторяем — вставляем новый цикл в общий путь.
- В конце получаем путь/цикл, который использует каждое ребро ровно один раз.
Сложность: O(n + m) при хранении указателей/итераторов на неиспользованные рёбра.
Python (Hierholzer)
def hierholzer(n, g):
st = [0]
path = []
it = [0]*n
while st:
v = st[-1]
while it[v] < len(g[v]) and g[v][it[v]] == -1:
it[v] += 1
if it[v] == len(g[v]):
path.append(v)
st.pop()
else:
to = g[v][it[v]]
g[v][it[v]] = -1
for i in range(len(g[to])):
if g[to][i] == v:
g[to][i] = -1
break
st.append(to)
return path[::-1]
C++ (Hierholzer)
#include <vector>
using namespace std;
vector<int> hierholzer(int n, vector<vector<int>>& g) {
vector<int> st{0}, path, it(n,0);
while (!st.empty()) {
int v = st.back();
while (it[v] < (int)g[v].size() && g[v][it[v]] == -1) ++it[v];
if (it[v] == (int)g[v].size()) { path.push_back(v); st.pop_back(); }
else {
int to = g[v][it[v]];
g[v][it[v]] = -1;
for (int i = 0; i < (int)g[to].size(); ++i) if (g[to][i] == v) { g[to][i] = -1; break; }
st.push_back(to);
}
}
reverse(path.begin(), path.end());
return path;
}
8) Рюкзаки
0/1 рюкзак: вес + ценность
Что это
Максимум ценности при ограничении веса.
Где используется
выбор предметов, бюджет/ограничение.
Задача 1 (база)
Условие: n предметов (w,v), W. Найти максимум ценности.
(Решение — 1D dp справа налево.)
Рюкзак: достижимость сумм (веса)
Что это
Можно ли набрать сумму S.
Задача 1 (гирьки)
Условие: можно ли разделить веса на две кучки равной суммы?
Идея: если сумма нечётная — сразу NO. Иначе проверяем достижимость sum/2.
Meet-in-the-middle
Что это
Для n~40 перебираем суммы половин.
Задача 1
Условие: выбрать подмножество с суммой максимально близкой к W (≤W).
(Решение — как в разделе MiTM.)
Что это (подробно)
Meet-in-the-middle (MiTM) — приём для задач перебора, когда n ≈ 30..40: массив делят на две половины, перебирают все подмножества в каждой половине (2^(n/2) каждой) и комбинируют результаты. Это даёт ≈ O(2^{n/2}) вместо O(2^n).
Когда применять
- n ≤ ~40 и прямой перебор 2^n невозможен;
- задачи про суммы подмножеств, выборы по весу/ценности, минимизация/максимизация при ограничении W.
Идея (на примере подмножества с суммой ≤ W и максимальной суммой):
- Разбить массив на
A и B.
- Посчитать все суммы подмножеств
sumA, sumB.
- Отсортировать
sumB и для каждой x из sumA найти лучший y из sumB такой, что x + y ≤ W (binary search).
Python
def mitm_best_leq(a, W):
n = len(a)
m = n // 2
A = a[:m]
B = a[m:]
sumA = []
for mask in range(1<<len(A)):
s = 0
for i in range(len(A)):
if mask >> i & 1:
s += A[i]
sumA.append(s)
sumB = []
for mask in range(1<<len(B)):
s = 0
for i in range(len(B)):
if mask >> i & 1:
s += B[i]
sumB.append(s)
sumB.sort()
import bisect
best = -10**18
for x in sumA:
if x > W: continue
i = bisect.bisect_right(sumB, W - x) - 1
if i >= 0:
best = max(best, x + sumB[i])
return best
C++
#include <bits/stdc++.h>
using namespace std;
long long mitm_best_leq(const vector<int>& a, long long W) {
int n = (int)a.size();
int m = n/2;
vector<long long> sumA, sumB;
for (int mask = 0; mask < (1<<m); ++mask) {
long long s = 0;
for (int i = 0; i < m; ++i) if (mask >> i & 1) s += a[i];
sumA.push_back(s);
}
int rem = n - m;
for (int mask = 0; mask < (1<<rem); ++mask) {
long long s = 0;
for (int i = 0; i < rem; ++i) if (mask >> i & 1) s += a[m + i];
sumB.push_back(s);
}
sort(sumB.begin(), sumB.end());
long long best = LLONG_MIN;
for (long long x : sumA) {
if (x > W) continue;
auto it = upper_bound(sumB.begin(), sumB.end(), W - x);
if (it != sumB.begin()) {
--it;
best = max(best, x + *it);
}
}
return best;
}
Пример применения
- задача «есть ли подмножество с суммой ровно S» при n≈40 — можно генерировать массив сумм для одной половины и проверять в множестве другой; для оптимума ≤W использовать сортировку + бинпоиск.
Логика подробно
- перебор 2^{n/2} для каждой половины даёт приемлемое время при n≈40; сортировка второй половины + бинарный поиск позволяет для каждой суммы первой половины быстро найти совместимую сумму второй.
9) Комбинаторика
Что это
Комбинаторика — раздел, посвящённый подсчёту и перечислению комбинаций, перестановок и подмножеств. Часто встречается в задачах перебора и в задачах на подсчёт по модулю.
Когда использовать
- когда задача просит "число способов" или перебрать все варианты (n! небольшое);
- когда n ≤ 20 — подменножества через битовые маски; когда n ≤ 10 — перебор перестановок.
Маски подмножеств
Задача 1
Условие: дан массив n<=20. Найти, есть ли подмножество с суммой S.
Идея: перебрать маски.
Примеры и шаблоны
Python
def subset_sum_exists(a, S):
n = len(a)
for mask in range(1<<n):
s = 0
for i in range(n):
if mask >> i & 1:
s += a[i]
if s == S:
return True
return False
C++
#include <vector>
using namespace std;
bool subset_sum_exists(const vector<int>& a, int S) {
int n = (int)a.size();
for (int mask = 0; mask < (1<<n); ++mask) {
int s = 0;
for (int i = 0; i < n; ++i) if (mask >> i & 1) s += a[i];
if (s == S) return true;
}
return false;
}
Логика подробно
- каждая маска кодирует подмножество; биты маски соответствуют включению/исключению элементов; полный перебор 2^n даёт все подмножества.
Перестановки
Задача 1
Условие: дано n<=10. Найти минимум стоимости обхода по всем точкам (перебор перестановок).
Генерация перестановок
Python
import itertools
for p in itertools.permutations(range(n)):
pass
C++
#include <algorithm>
#include <vector>
using namespace std;
vector<int> p(n);
for (int i = 0; i < n; ++i) p[i] = i;
do {
// use p
} while (next_permutation(p.begin(), p.end()));
Логика подробно
next_permutation генерирует перестановки в лексикографическом порядке; перебор всех перестановок даёт сложность O(n! * n) по времени, поэтому применим для n ≤ 10.
Комбинаторные объекты: C(n,k), A(n,k), n!
Задача 1
Условие: сколько способов выбрать k из n?
Факториалы и C(n,k) по модулю
Python
MOD = 10**9+7
def prep_fact(n):
fact = [1]*(n+1)
for i in range(1, n+1):
fact[i] = fact[i-1]*i % MOD
inv = [1]*(n+1)
inv[n] = pow(fact[n], MOD-2, MOD)
for i in range(n, 0, -1):
inv[i-1] = inv[i]*i % MOD
return fact, inv
def C(n,k,fact,inv):
if k < 0 or k > n: return 0
return fact[n]*inv[k]%MOD*inv[n-k]%MOD
C++
#include <vector>
using namespace std;
const long long MOD = 1000000007;
vector<long long> fact, invfact;
long long modpow(long long a, long long e) {
long long r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
void prep_fact(int n) {
fact.assign(n+1, 1);
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1] * i % MOD;
invfact.assign(n+1, 1);
invfact[n] = modpow(fact[n], MOD-2);
for (int i = n; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;
}
long long Cnk(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}
Логика подробно
fact[i] содержит i! mod MOD; invfact[i] — обратный факториал. Используем быстрое возведение в степень для обратного fact[n]^(MOD-2) при простом модуле, затем восстанавливаем остальные invfact умножением на i в обратном порядке.
10) Теория чисел
Что это
Теория чисел изучает свойства целых чисел: простоту, делимость, факторизацию, операции по модулю. В алгоритмике это основа для проверок простоты, поиска делителей и работы с модулем (C(n,k) по модулю, обратные элементы).
Когда использовать
- когда нужно проверить простоту большого количества чисел → решето, Miller-Rabin для больших чисел;
- когда нужно факторизовать число до ~1e12 → пробное деление с простыми из решета; для больших чисел нужны специализированные методы (Pollard Rho);
- для модульной арифметики используйте
modpow и inv_mod (Ферма) при простом модуле.
НОД / НОК
Задача 1
Условие: дано n чисел, найти их НОД.
Python
import math
n = int(input())
a = list(map(int, input().split()))
g = 0
for x in a:
g = math.gcd(g, x)
print(g)
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
long long g = 0;
for (int i = 0; i < n; ++i) {
long long x; cin >> x;
g = std::gcd(g, x);
}
cout << g << "\n";
}
Проверка простоты
Задача 1
Условие: для каждого числа вывести PRIME/COMPOSITE.
(Решение — Miller-Rabin или пробная делимость до sqrt для небольших чисел.)
Python (простая проверка и Miller-Rabin)
def is_probable_prime(n):
if n < 2: return False
small_primes = [2,3,5,7,11,13,17,19,23,29]
for p in small_primes:
if n % p == 0:
return n == p
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
def check(a):
x = pow(a, d, n)
if x == 1 or x == n-1: return True
for _ in range(s-1):
x = x*x % n
if x == n-1: return True
return False
for a in [2,325,9375,28178,450775,9780504,1795265022]:
if a % n == 0: continue
if not check(a): return False
return True
C++ (Miller-Rabin deterministic for 64-bit)
#include <bits/stdc++.h>
using namespace std;
using u128 = unsigned __int128;
long long modmul(long long a, long long b, long long mod) {
return (u128)a*b % mod;
}
long long modpow(long long a, long long e, long long mod) {
long long r = 1;
while (e) {
if (e & 1) r = modmul(r, a, mod);
a = modmul(a, a, mod);
e >>= 1;
}
return r;
}
bool isPrime(long long n) {
if (n < 2) return false;
for (long long p : {2,3,5,7,11,13,17,19,23,29}) {
if (n%p==0) return n==p;
}
long long d = n-1, s = 0;
while ((d & 1) == 0) { d >>= 1; ++s; }
for (long long a : {2,325,9375,28178,450775,9780504,1795265022}) {
if (a % n == 0) continue;
long long x = modpow(a, d, n);
if (x==1 || x==n-1) continue;
bool comp = true;
for (int r = 1; r < s; ++r) {
x = modmul(x, x, n);
if (x == n-1) { comp = false; break; }
}
if (comp) return false;
}
return true;
}
Логика подробно
- Miller-Rabin разделяет
n-1 на d*2^s. Для базы a проверяем a^d mod n и последовательные квадраты; если никакая проверка не даёт n-1, то n составное относительно этой базы. Набор баз, указанный в коде, даёт детерминированный тест для 64-битных чисел.
Все делители
Задача 1
Условие: вывести все делители числа по возрастанию.
Python
def divisors(n):
small, large = [], []
i = 1
while i*i <= n:
if n % i == 0:
small.append(i)
if i*i != n:
large.append(n//i)
i += 1
return small + large[::-1]
C++
#include <vector>
using namespace std;
vector<long long> divisors(long long n) {
vector<long long> a, b;
for (long long i = 1; i*i <= n; ++i) if (n%i==0) {
a.push_back(i);
if (i*i != n) b.push_back(n/i);
}
reverse(b.begin(), b.end());
a.insert(a.end(), b.begin(), b.end());
return a;
}
Логика подробно
- перебираем делители до sqrt(n); для каждого найденного делителя
i также есть парный делитель n/i. Собираем малые и большие делители отдельно, чтобы вернуть список в порядке возрастания.
Факторизация
Задача 1
Условие: разложить число на простые множители и вывести пары (p, степень).
Python (пробная факторизация с решетом)
def sieve_primes(n):
bs = [True]*(n+1)
bs[0]=bs[1]=False
for i in range(2, int(n**0.5)+1):
if bs[i]:
for j in range(i*i, n+1, i): bs[j]=False
return [i for i,v in enumerate(bs) if v]
primes = sieve_primes(100000)
def factorize(x):
res = []
for p in primes:
if p*p > x: break
if x % p == 0:
cnt = 0
while x % p == 0:
x //= p
cnt += 1
res.append((p, cnt))
if x > 1: res.append((x,1))
return res
C++ (trial division using precomputed primes)
#include <vector>
using namespace std;
vector<long long> sieve(int n) {
vector<char> bs(n+1, true);
bs[0]=bs[1]=false;
for (int i = 2; i*i <= n; ++i) if (bs[i]) for (int j = i*i; j <= n; j += i) bs[j]=false;
vector<long long> p;
for (int i = 2; i <= n; ++i) if (bs[i]) p.push_back(i);
return p;
}
vector<pair<long long,int>> factorize(long long x, const vector<long long>& primes) {
vector<pair<long long,int>> res;
for (long long p : primes) {
if (p*p > x) break;
if (x % p == 0) {
int cnt = 0;
while (x % p == 0) { x /= p; ++cnt; }
res.emplace_back(p, cnt);
}
}
if (x > 1) res.emplace_back(x,1);
return res;
}
Логика подробно
- пробная факторизация перебирает простые до sqrt(x); если после делений остаётся >1, то это простое большое множитель. Для больших x (>1e12) стоит применять Pollard Rho.
Решето Эратосфена
Задача 1
Условие: посчитать количество простых до N.
Python
def sieve_count(n):
bs = [True]*(n+1)
bs[0]=bs[1]=False
for i in range(2, int(n**0.5)+1):
if bs[i]:
for j in range(i*i, n+1, i): bs[j]=False
return sum(bs)
C++
#include <vector>
using namespace std;
int sieve_count(int n) {
vector<char> bs(n+1, true);
bs[0]=bs[1]=false;
for (int i = 2; i*i <= n; ++i) if (bs[i]) for (int j = i*i; j <= n; j += i) bs[j]=false;
int cnt = 0; for (int i = 2; i <= n; ++i) if (bs[i]) ++cnt; return cnt;
}
Логика подробно
- решето отмечает составные числа, начиная с квадратов простых; сложность O(n log log n). Часто используется для подготовки массива простых до нужного предела и для массовых проверок делимости.
Модульная арифметика: powmod и обратный элемент
Python
def powmod(a, e, mod):
return pow(a, e, mod)
def inv_mod(a, mod):
return pow(a, mod-2, mod)
C++
long long modpow(long long a, long long e, long long mod) {
long long r = 1;
while (e) {
if (e & 1) r = (__int128)r * a % mod;
a = (__int128)a * a % mod;
e >>= 1;
}
return r;
}
long long inv_mod(long long a, long long mod) { return modpow(a, mod-2, mod); }
Логика подробно
- быстрое возведение в степень работает за O(log e). Для обратного элемента при простом модуле используем
a^(mod-2) mod mod по малой теореме Ферма; для составного модуля нужен расширенный алгоритм Евклида.
11) DSU (union-find)
DSU (union-find)
Задача 1
Условие: есть запросы двух типов: объединить (a,b) и спросить, в одной ли компоненте.
(Решение — DSU.)
12) Дерево отрезков
Сегдерево: сумма/минимум + обновления
Что это
Поддержка:
- запрос на отрезке (sum/min/max)
- точечное обновление
в
O(log n).
Где используется
“много запросов” + “данные меняются”.
Задача 1 (важная)
Условие: массив и q операций:
1 i x (a[i]=x)2 l r (сумма на [l,r])
(Решение — сегдерево из раздела.)
13) Побитовые операции
AND/OR/XOR, маски, свойства и задачи
Ключевые свойства (то, что надо помнить)
x ^ x = 0x ^ 0 = x- XOR ассоциативен/коммутативен
x & (x-1) убирает младший установленный бит
Расширенные свойства
XOR:
x ^ x = 0 — число с собой даёт 0x ^ 0 = x — число с нулём даёт себяx ^ y = y ^ x — коммутативность(x ^ y) ^ z = x ^ (y ^ z) — ассоциативность- если
a ^ b ^ c ^ d = 0, то a = b ^ c ^ d (и любые перестановки)
- XOR удобен для поиска "непарного" элемента (когда остальные встречаются чётное число раз)
AND/OR:
x & x = x, x | x = xx & 0 = 0, x | 0 = xx & (x-1) убирает самый младший бит (последний установленный бит справа)x & -x выделяет самый младший установленный бит (в виде степени 2)popcount(x) — количество единичных битов в x
Когда применять: подсчёт битов, проверка на степень двойки, разные наборы, «интересные» подсчёты на битовом уровне.
Задача 1 (классика)
Условие: все числа встречаются дважды, одно — один раз. Найти его.
(Решение — XOR всех.)
Python
def find_unique(a):
res = 0
for x in a:
res ^= x
return res
Логика: все парные элементы XOR друг с другом дают 0, остаётся только уникальный.
Задача 2 (частая)
Условие: проверить, является ли число степенью двойки.
Python
def is_pow2(x):
return x > 0 and (x & (x-1)) == 0
C++
bool is_pow2(long long x) {
return x > 0 && (x & (x - 1)) == 0;
}
Разбор: у степени двойки ровно один бит =1.
Задача 3 (муниципальная): интересный XOR четырёх чисел
Условие: дан массив n различных чисел. Проверить, существуют ли четыре различных числа a, b, c, d такие, что a ^ b ^ c ^ d = 0.
Идея: заметить, что a ^ b ^ c ^ d = 0 эквивалентно a ^ b = c ^ d. Перебрать все пары (O(n^2)), вычислить XOR каждой пары, и проверить, существуют ли две разные пары с одинаковым XOR.
Python
def four_xor_zero(a):
n = len(a)
xor_pairs = {}
for i in range(n):
for j in range(i + 1, n):
xor_val = a[i] ^ a[j]
if xor_val not in xor_pairs:
xor_pairs[xor_val] = []
xor_pairs[xor_val].append((i, j))
for xor_val, pairs in xor_pairs.items():
if len(pairs) >= 2:
for p1 in range(len(pairs)):
for p2 in range(p1 + 1, len(pairs)):
i1, j1 = pairs[p1]
i2, j2 = pairs[p2]
if len({i1, j1, i2, j2}) == 4:
return True
return False
C++
#include <bits/stdc++.h>
using namespace std;
bool four_xor_zero(const vector<int>& a) {
int n = (int)a.size();
map<int, vector<pair<int,int>>> xor_pairs;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int xor_val = a[i] ^ a[j];
xor_pairs[xor_val].emplace_back(i, j);
}
}
for (auto& [xor_val, pairs] : xor_pairs) {
if ((int)pairs.size() >= 2) {
for (int p1 = 0; p1 < (int)pairs.size(); ++p1) {
for (int p2 = p1 + 1; p2 < (int)pairs.size(); ++p2) {
auto [i1, j1] = pairs[p1];
auto [i2, j2] = pairs[p2];
set<int> indices{i1, j1, i2, j2};
if ((int)indices.size() == 4) return true;
}
}
}
}
return false;
}
Логика подробно
- ключевое свойство:
a ^ b ^ c ^ d = 0 означает a ^ b = c ^ d. Мы порождаем все пары и их XOR; если одно значение XOR получается из двух разных (непересекающихся) пар, то мы нашли четыре числа с нулевым XOR.
- сложность: O(n^2 log n + результат) для поиска и проверки; при большом количестве пар с одинаковым XOR может потребоваться O(n^4) в худшем случае, но обычно работает быстро.
14) Сканлайн
Что это (базовое объяснение)
Сканлайн — техника, где мы "сканируем" пространство в одном направлении (обычно слева направо или по событиям), поддерживая активное множество объектов. На каждом событии мы обновляем множество и отвечаем на запрос.
Когда применять
- задачи на объединение отрезков (точное или приблизительное)
- поиск пересечений, покрытий на одной оси
- подсчёт площадей геометрических фигур (прямоугольники, объединение отрезков)
- обработка событий в хронологическом порядке
Идея на примере: объединение отрезков и суммарная длина
Условие: даны отрезки на оси, найти объединение (суммарная длина покрытого диапазона).
Алгоритм:
- Создать события: для каждого отрезка
[l, r] создать событие "открыть в l" и "закрыть в r".
- Отсортировать события по позиции.
- Сканировать слева направо: при открытии увеличиваем счётчик активных отрезков; при закрытии уменьшаем.
- Во время сканирования считаем суммарную длину на участках между активными событиями.
Python
def scan_line_union_length(intervals):
events = []
for l, r in intervals:
events.append((l, 1))
events.append((r, -1))
events.sort()
total = 0
active = 0
prev_pos = None
for pos, delta in events:
if prev_pos is not None and active > 0:
total += pos - prev_pos
active += delta
prev_pos = pos
return total
C++
#include <bits/stdc++.h>
using namespace std;
long long scan_line_union_length(const vector<pair<int,int>>& intervals) {
vector<pair<int,int>> events;
for (auto [l,r] : intervals) {
events.emplace_back(l, 1);
events.emplace_back(r, -1);
}
sort(events.begin(), events.end());
long long total = 0;
int active = 0;
int prev_pos = -1;
for (int i = 0; i < (int)events.size(); ++i) {
auto [pos, delta] = events[i];
if (i > 0 && active > 0) {
total += (long long)(pos - prev_pos);
}
active += delta;
prev_pos = pos;
}
return total;
}
Пример применения
Задача: даны события (начало мероприятия, конец). Найти общее время, когда хотя бы одно мероприятие идёт.
- подход: сканлайн по времени, в каждый момент смотрим, сколько мероприятий активно, учитываем время только если активно хотя бы одно.
Логика подробно
- событие "открыть" и "закрыть" позволяют отслеживать, какие отрезки активны в каждой точке; сортировка по позиции гарантирует, что мы обрабатываем в правильном порядке; счётчик активных отрезков говорит, покрыта ли текущая позиция.
- вариант "2D сканлайн": когда нужно слить несколько наборов (например, найти площадь объединения прямоугольников), применяем сканлайн по одной оси и на каждой вертикальной линии слияния отрезков по другой оси.
15) Два указателя
Что это (базовое объяснение)
Два указателя — техника, где мы поддерживаем два указателя (индекса) на массиве или двух массивах, чтобы за один проход решить задачу вместо вложенного перебора.
Когда применять
- массив отсортирован и нужно найти пару с суммой S
- слияние двух отсортированных массивов (merge sort)
- окно с двумя концами: поиск подмассива по условию
- задачи на "максимальную площадь" (столбцы, треугольник и т.д.)
Идея на примере 1: два суммирования
Условие: найти пару в отсортированном массиве с суммой ровно S.
Алгоритм:
- Указатель
l = 0 слева, r = n-1 справа.
- Если
a[l] + a[r] == S, найти.
- Если
a[l] + a[r] < S, то l++ (нужна большая сумма).
- Если
a[l] + a[r] > S, то r-- (нужна меньшая сумма).
Python
def two_sum(a, S):
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == S:
return (l, r)
if s < S:
l += 1
else:
r -= 1
return None
C++
#include <vector>
using namespace std;
pair<int,int> two_sum(const vector<int>& a, int S) {
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == S) return {l, r};
if (s < S) l++;
else r--;
}
return {-1, -1};
}
Идея на примере 2: окно (sliding window)
Условие: найти минимальный подмассив с суммой ≥ S.
Алгоритм:
- Два указателя:
l = 0 (левая граница окна), r = 0 (правая).
- Расширяем окно вправо (
r++), пока сумма < S.
- Когда сумма ≥ S, пытаемся сжать слева (
l++), пока сумма остаётся ≥ S.
- Ответ — минимальная длина найденного окна.
Python
def min_subarray_sum(a, S):
n = len(a)
l = 0
current_sum = 0
min_len = float('inf')
for r in range(n):
current_sum += a[r]
while current_sum >= S:
min_len = min(min_len, r - l + 1)
current_sum -= a[l]
l += 1
return min_len if min_len != float('inf') else -1
C++
#include <bits/stdc++.h>
using namespace std;
int min_subarray_sum(const vector<int>& a, long long S) {
int n = (int)a.size();
int l = 0;
long long current_sum = 0;
int min_len = INT_MAX;
for (int r = 0; r < n; ++r) {
current_sum += a[r];
while (current_sum >= S) {
min_len = min(min_len, r - l + 1);
current_sum -= a[l];
l++;
}
}
return min_len == INT_MAX ? -1 : min_len;
}
Логика подробно
- для пары сумм: в отсортированном массиве движение указателей гарантирует, что мы посетим все релевантные пары за O(n).
- для окна: каждый элемент посещается левым и правым указателем ровно один раз, поэтому общее время O(n); сжимаем окно, пока условие выполняется, расширяем, пока не выполняется.
- применимо к задачам, где ответ подчиняется монотонности: если окно размера k удовлетворяет условию, то большее окно тоже (или наоборот).
16) STL C++ и оптимизация
Быстрый ввод-вывод
ios::sync_with_stdio(false);
cin.tie(nullptr);
Когда нужно: почти всегда.
vector, pair, sort
vector — динамический массивpair — 2 значенияsort — интросорт (быстро)
Мини-практика:
vector<pair<int,int>> a;
sort(a.begin(), a.end()); // сначала по first, потом second
map / set vs unordered_map / unordered_set
Что важно понимать
map/set — дерево: O(log n), есть порядок и lower_bound.unordered_* — хеш: среднее O(1), порядка нет.
Где использовать
- нужен порядок/границы →
map/set
- нужен быстрый “словарь” →
unordered_map
Лайфхаки g++ и практика на контесте
Компиляция и флаги
Базовая команда (обычно):
g++ -std=c++17 -O2 -pipe main.cpp -o main
Флаги оптимизации (как использовать и когда)
-O0 (без оптимизации):
- отключены все оптимизации
- используется при отладке (быстрая компиляция, медленный код)
-O2 (стандартный выбор):
g++ -std=c++17 -O2 main.cpp
- сбалансированные оптимизации: скорость компиляции и скорость кода
- рекомендуется для соревнований (большинство систем оценки используют именно это)
- включает: инлайнинг, циклические оптимизации, удаление мёртвого кода и т.д.
-O3:
- более агрессивная оптимизация, чем
-O2
- может увеличить размер бинарного файла
- иногда медленнее из-за кэш-промахов, реже даёт выигрыш
-Ofast:
g++ -std=c++17 -Ofast main.cpp
- самые агрессивные оптимизации, включая
-ffast-math
-ffast-math нарушает точность вычислений с плавающей точкой (опасно для задач с FP)- может нарушить поведение кода, требующего точных IEEE 754 результатов
- используйте только если: задача целочисленная или вы понимаете следствия для ваших вычислений
-march=native:
g++ -std=c++17 -O2 -march=native main.cpp
- компилятор генерирует инструкции для вашего процессора (AVX2, SSE и т.д.)
- может дать выигрыш на локальной машине
- внимание: часто не разрешён на судейских системах (машины могут быть другие)
Прагмы в коде (когда флаги не помогают)
Если вам нужна фина тюнинг без изменения флагов, используйте прагмы прямо в коде:
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
Это делает то же самое локально для файла, но учтите: судейские системы могут игнорировать эти прагмы.
Практика при написании кода
Рекомендации по выбору флагов для соревнований
- По умолчанию: используй
-O2 (самый предсказуемый и быстрый)
- Если TLE и задача целочисленная: пробуй
-O3 или -Ofast
- Если задача использует FP (double, float): остановись на
-O2 (безопаснее)
- Локальная машина vs судейская:
-march=native работает только на вашей машине; не полагайся на это для финального решения
