Занятие начинается с разбора контеста по DFS (графы), затем идёт обзор приёмов динамического программирования и семинар с разбором задач на динамику. Условия на записи пересказываются устно — где формулировку не удаётся восстановить, это отмечено. Код ко всем приведённым алгоритмам проверен случайными тестами против перебора. Запись обрывается на последней задаче семинара (про телефоны); её разбор завершён ниже по собственному решению.
3:18 Преподаватель отмечает, что основная ценность контеста — в задачах, начиная с восьмой: первые пять разбирались на лекции, ещё две «на две минуты». Чтобы брать олимпиады, нужно знать не алгоритмы, а идеи, которые повторяются в задачах; поэтому такие задачи нужно дорешать, даже если они разбираются. Время до разбора даётся, чтобы подумать над максимальным числом задач, а не решить как можно больше: на разбор следует приходить с прочитанными условиями и 15–30 минутами размышлений над каждой.
7:33 Условие. Даны две строки длины $n$: символ $i$-й позиции — проект (одна из 26 латинских букв), в котором в $i$-й день работает Алексей (первая строка) или Иван (вторая). В любой день они могут поменяться проектами. Можно ли выбрать дни обмена так, чтобы к концу у каждого было поровну задач в каждом проекте? Нужно также вывести выбор.
11:55 Выбрасываем лишнее. (1) Неважно, кто в каком порядке стоит в паре — перестановка пары не меняет возможность. (2) Порядок дней неважен. Остаётся набор из $n$ неупорядоченных пар букв, и для каждой пары нужно решить, кому какая достанется.
13:38 Граф. Вершина — проект (всего 26), ребро — день, соединяющий два проекта. Выбор «Алексей получает $a$, Иван — $b$» — это ориентация ребра $a\to b$. Условие «каждый сделал поровну задач в проекте $x$» означает: входящих рёбер в $x$ столько же, сколько исходящих. Это условие эйлерова цикла: необходимо, чтобы в каждой вершине степень была чётной.
17:03 Достаточность. Если степени всех вершин чётны, то в каждой компоненте существует эйлеров цикл; ориентируем рёбра по направлению обхода — в каждой вершине вход и выход встречаются поровну. Реализация: пока у вершины есть свободное ребро, идём по свободным рёбрам и ориентируем их по ходу; из-за чётных степеней маршрут всегда замыкается в начальной вершине, поэтому полная ориентация сбалансирована, и искать сам эйлеров цикл не нужно. Если какая-то степень нечётна, ответ «нельзя» (это же — простая проверка «число задач в каждом проекте чётно»).
// Каждый день — ребро между проектами (s_i, t_i). Нужно ориентировать рёбра так, чтобы в каждой вершине входящих было столько же, сколько исходящих.
// Ребро направлено a→b: Алексей делает проект a, Иван — проект b (swap не нужен); b→a — нужен swap.
// Возможно ⇔ все степени чётны (проект встречается чётное число раз). Ориентация = направление обхода замкнутых маршрутов, найденных «пока есть свободное ребро».
vector<int> orientDays(int n, const vector<pair<int,int>> &e, bool &ok) { // результат: swap[i] = 1, если в день i нужно поменяться
vector<vector<pair<int,int>>> adj(n);
vector<int> deg(n, 0);
for (int i = 0; i < (int)e.size(); i++) {
adj[e[i].first].push_back({e[i].second, i}); adj[e[i].second].push_back({e[i].first, i});
deg[e[i].first]++; deg[e[i].second]++;
}
ok = true;
for (int d : deg) if (d % 2) ok = false;
vector<int> swp(e.size(), 0), ptr(n, 0);
vector<char> used(e.size(), 0);
if (!ok) return swp;
for (int s = 0; s < n; s++) {
for (;;) { // выпускаем замкнутые маршруты из s, пока у s есть свободные рёбра
while (ptr[s] < (int)adj[s].size() && used[adj[s][ptr[s]].second]) ptr[s]++;
if (ptr[s] == (int)adj[s].size()) break;
int v = s;
for (;;) {
while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]].second]) ptr[v]++;
if (ptr[v] == (int)adj[v].size()) break; // идти некуда: из-за чётных степеней мы вернулись в s
auto [to, id] = adj[v][ptr[v]];
used[id] = 1;
swp[id] = (e[id].first != v); // шли v→to; если v — «второй» конец, значит порядок надо перевернуть
if (e[id].first == e[id].second) swp[id] = 0;
v = to;
}
}
}
return swp;
}19:57 Условие. Дан граф: вершина — монета, ребро означает, что монеты разных типов. Типов три (серебряная, бронзовая, медная), медных не более одной. Определить, какие монеты могут быть медными.
21:04 Переформулировка. Удалим медную монету — останутся серебряные и бронзовые, и граф должен стать двудольным. Нужно найти все вершины $v$, после удаления которых граф двудольный. Если граф двудольный изначально — подходят все вершины.
22:07 Идея. Построим дерево DFS. Все рёбра, не вошедшие в дерево, вертикальные. Назовём такое ребро нечётным, если вместе с путём по дереву оно образует цикл нечётной длины (то есть разность глубин концов чётна), и чётным иначе. Граф двудольный ⇔ нечётных циклов нет ⇔ нечётных вертикальных рёбер нет. Вершина $v$ подходит, если выполнено два условия.
34:10 Лектор подчёркивает, что идея «все не-деревянные рёбра вертикальны» — опора решения, и её нужно держать в голове.
// Вершины v, после удаления которых граф становится двудольным. DFS-дерево; «нечётное» вертикальное ребро — то, что вместе с путём по дереву даёт нечётный цикл.
struct Bip {
int n, oddTotal = 0;
vector<vector<pair<int,int>>> adj; // (сосед, номер ребра)
vector<int> depth, par, cover, minOdd, minEven;
vector<vector<int>> child;
int m = 0;
Bip(int n) : n(n), adj(n), depth(n, -1), par(n, -1), cover(n, 0), minOdd(n, INT_MAX), minEven(n, INT_MAX), child(n) {}
void addEdge(int a, int b) { adj[a].push_back({b, m}); if (a != b) adj[b].push_back({a, m}); m++; }
void dfs(int v, int pe) {
for (auto [to, id] : adj[v]) {
if (id == pe) continue;
if (depth[to] < 0) { depth[to] = depth[v] + 1; par[to] = v; child[v].push_back(to); dfs(to, id); }
else if (depth[to] <= depth[v]) { // вертикальное ребро v → предок to (или петля)
bool odd = (depth[v] - depth[to]) % 2 == 0; // чётная разность глубин ⇒ цикл нечётной длины
if (odd) { oddTotal++; cover[v]++; if (par[to] >= 0) cover[par[to]]--; minOdd[v] = min(minOdd[v], depth[to]); }
else minEven[v] = min(minEven[v], depth[to]);
}
}
for (int c : child[v]) { // подъём значений и накопление покрытий по поддереву
cover[v] += cover[c]; minOdd[v] = min(minOdd[v], minOdd[c]); minEven[v] = min(minEven[v], minEven[c]);
}
}
vector<int> goodVertices() { // все вершины, удаление которых даёт двудольный граф
for (int r = 0; r < n; r++) if (depth[r] < 0) { depth[r] = 0; dfs(r, -1); }
vector<int> res;
for (int v = 0; v < n; v++) {
if (cover[v] != oddTotal) continue; // каждое нечётное ребро должно «накрывать» v (или заканчиваться в нём)
bool ok = true;
for (int c : child[v]) if (minOdd[c] < depth[v] && minEven[c] < depth[v]) ok = false; // из одного поддерева наверх не должно идти рёбер обеих чётностей
if (ok) res.push_back(v);
}
return res;
}
};34:33 Условие (по записи). Таблица $1000\times1000$ чисел от 1 до 9 и нечётное число $X\in[1,9]$. Стоимость шага в соседнюю по стороне клетку из клетки со значением $a$ в клетку со значением $b$ равна $(a-b)^X$ (может быть отрицательной). Нужно отвечать на $10^5$ запросов: минимальная стоимость пути между двумя клетками (или сообщить, что путь неограниченно дешёвый).
36:17 Замечание. Так как $X$ нечётно, $(a-b)^X=-(b-a)^X$: шаг назад стоит ровно столько же, но с противоположным знаком. Значит, ходьба «туда-обратно» бесплатна, а отрицательные циклы — главная проблема: если есть цикл ненулевой стоимости, то в одну из сторон он отрицателен и по нему можно ходить сколько угодно, получив $-\infty$. Поэтому если есть хоть один цикл ненулевой стоимости, ответом на любой запрос будет «неограниченно» ( INVALID) (граф связный).
39:05 Если все циклы нулевые. Для двух клеток и двух любых путей между ними объединение прямого и обратного пути — цикл, поэтому его стоимость нулевая, значит стоимости путей равны. Достаточно взять один путь — сначала по строке, потом по столбцу — и посчитать его префиксными суммами по строкам и столбцам: ответ за $O(1)$.
41:51 Как проверить, что все циклы нулевые. Достаточно проверить все квадраты $2\times2$: цикл любой формы разлагается в сумму таких квадратов (в сетке любой путь можно постепенно «переключать» по клеточкам, а при нулевой стоимости каждого квадрата стоимость пути не меняется).
// Сетка n×m, стоимость шага из клетки со значением a в клетку со значением b равна (a − b)^X, X нечётно. Запрос: минимальная стоимость пути между клетками.
// Нечётная степень ⇒ стоимость обратного шага противоположна. Если все циклы 2×2 имеют нулевую стоимость, то стоимость пути зависит только от концов.
typedef long long ll;
ll ipow(ll b, int e) { ll r = 1; while (e--) r *= b; return r; }
struct GridCost {
int n, m, X; bool valid = true;
vector<vector<int>> a;
vector<vector<ll>> rowPref, colPref; // rowPref[i][j]: цена пути по строке i от столбца 0 до j; colPref[i][j]: по столбцу j от строки 0 до i
GridCost(vector<vector<int>> g, int X) : n(g.size()), m(g[0].size()), X(X), a(g) {
for (int i = 0; i + 1 < n && valid; i++)
for (int j = 0; j + 1 < m; j++) { // цикл (i,j) → (i,j+1) → (i+1,j+1) → (i+1,j) → (i,j)
ll c = ipow(a[i][j] - a[i][j + 1], X) + ipow(a[i][j + 1] - a[i + 1][j + 1], X)
+ ipow(a[i + 1][j + 1] - a[i + 1][j], X) + ipow(a[i + 1][j] - a[i][j], X);
if (c != 0) { valid = false; break; } // цикл ненулевого веса: пройдя его в нужную сторону бесконечно, получаем −∞
}
rowPref.assign(n, vector<ll>(m, 0)); colPref.assign(n, vector<ll>(m, 0));
for (int i = 0; i < n; i++) for (int j = 1; j < m; j++) rowPref[i][j] = rowPref[i][j - 1] + ipow(a[i][j - 1] - a[i][j], X);
for (int j = 0; j < m; j++) for (int i = 1; i < n; i++) colPref[i][j] = colPref[i - 1][j] + ipow(a[i - 1][j] - a[i][j], X);
}
// стоимость пути из (r1,c1) в (r2,c2): сначала по строке r1 до столбца c2, затем по столбцу c2 до строки r2
bool query(int r1, int c1, int r2, int c2, ll &res) {
if (!valid) return false;
res = (rowPref[r1][c2] - rowPref[r1][c1]) + (colPref[r2][c2] - colPref[r1][c2]);
return true;
}
};46:19 Дан ориентированный граф с отмеченными вершинами $1$ и $n$; нужно найти вершины, которые лежат на каждом пути из $1$ в $n$ (и такие, что путь простой). Из обсуждения: (1) вершины, не лежащие ни на одном пути $1\to n$, выбрасываем: оставляем те, что достижимы из $1$ и из которых достижима $n$ (два обхода: по рёбрам и по обратным рёбрам). (2) Если в оставшемся графе есть компоненты сильной связности размера больше одной, то каждая из них не даёт «обязательных» вершин, и её сжимают. (3) Остаётся DAG. Участники предлагали искать точки сочленения в неориентированной версии — лектор показывает, что на таком графе (например, «ромбик» с двумя источниками) это ломается, и рекомендует проверять решение на ромбе. Рабочий критерий в DAG: вершина $v$ обязательна ⇔ $\mathrm{paths}(1\to v)\cdot\mathrm{paths}(v\to n)=\mathrm{paths}(1\to n)$ (52:03, количество путей считается по модулям — несколько простых).
52:23 В таблице отмечены клетки, причём в каждой строке и каждом столбце не более одной. Для каждой клетки нужно выбрать одно из двух направлений (горизонтально или вертикально) к отмеченной клетке в своей строке или столбце; направления должны быть согласованы: если клетка $A$ смотрит на отмеченную $B$, то $B$ смотрит туда же. Решение: переменная на клетку — «горизонтально/вертикально». Для соседних отмеченных клеток в строке: «$A$ смотрит вправо» влечёт «$B$ смотрит вправо» (и контрапозиция), дизъюнктами по две переменные. Невозможность направления запрещается дизъюнктом вида $(\lnot x\lor y)$ — это обычный 2-SAT (разобран на предыдущей лекции).
58:20 Условие. Неориентированный граф малого размера (12 вершин, 17 рёбер), на каждом ребре запас $x$ монет. Идём по рёбрам; при проходе по ребру забираем $\lceil x/2\rceil$ монет, остаётся $\lfloor x/2\rfloor$. Закончить можно, только когда ходить некуда. Найти максимум собранных монет. (Лектор отмечает, что это композитная задача, где идеи накапливаются по шагам.)
1:00:05 Шаг 1: кратные рёбра. Ребро с запасом $x$ можно пройти не более $\log_2 x+1\le30$ раз; заменим его на $k$ параллельных «слоёв» с выигрышами $\lceil x/2\rceil$, затем остаток и так далее. Тогда маршрут не повторяет рёбер — это эйлеров путь/цикл в мультиграфе.
1:01:07 Шаг 2: критерий Эйлера. Нужно выбрать подмножество слоёв так, чтобы получившийся связный мультиграф имел эйлеров путь: не более двух вершин нечётной степени.
1:02:30 Шаг 3: жадное замечание. Между любыми двумя вершинами оптимально убрать не более одного слоя (последнего — он самый дешёвый): удаление двух слоёв не меняет чётность степеней, зато уменьшает выигрыш.
1:04:12 Шаг 4: перебор масок. Чётности степеней определяют, годится ли ответ. Перебираем $2^{17}$ подмножеств рёбер, у которых убираем последний слой; для каждой компоненты связности получившегося мультиграфа с не более чем двумя нечётными вершинами ответ — сумма оставшихся слоёв в ней. Максимум по маскам и компонентам.
// Ходим по рёбрам графа; на ребре с запасом x за проход забираем ceil(x/2), остаётся floor(x/2). Закончить можно только когда ход невозможен. Максимум собранного.
// Ребро с запасом w — это k ≤ ~30 «слоёв» с выигрышами g_1 ≥ g_2 ≥ ...; проход по ребру использует слои по порядку. Маршрут по c_e слоям каждого ребра — эйлеров путь в мультиграфе.
// Критерий: связный мультиграф, не более двух вершин нечётной степени. Достаточно рассматривать c_e ∈ {k_e, k_e − 1} (убрать последний слой): две копии не меняют чётность.
typedef long long ll;
ll bestWalk(int n, const vector<array<int,3>> &edges) { // edges: (u, v, w)
int m = edges.size();
vector<vector<ll>> g(m);
for (int i = 0; i < m; i++) { ll w = edges[i][2]; while (w > 0) { g[i].push_back((w + 1) / 2); w /= 2; } } // слои: ceil(w/2), затем остаток floor(w/2)
ll best = 0;
for (int mask = 0; mask < (1 << m); mask++) { // mask — рёбра, у которых убираем последний слой
vector<int> p(n), deg(n, 0);
iota(p.begin(), p.end(), 0);
function<int(int)> f = [&](int x) { return p[x] == x ? x : p[x] = f(p[x]); };
vector<int> cnt(m);
for (int i = 0; i < m; i++) {
cnt[i] = (int)g[i].size() - ((mask >> i) & 1);
if (cnt[i] > 0) { p[f(edges[i][0])] = f(edges[i][1]); deg[edges[i][0]] += cnt[i]; deg[edges[i][1]] += cnt[i]; }
}
vector<ll> sum(n, 0); vector<int> odd(n, 0);
for (int i = 0; i < m; i++) if (cnt[i] > 0) {
ll s = 0; for (int k = 0; k < cnt[i]; k++) s += g[i][k];
sum[f(edges[i][0])] += s;
}
for (int v = 0; v < n; v++) if (deg[v] % 2) odd[f(v)]++;
for (int v = 0; v < n; v++) if (f(v) == v && odd[v] <= 2) best = max(best, sum[v]); // берём одну компоненту связности целиком
}
return best;
}1:12:29 Дан ориентированный граф слов: слово $u$ можно заменить на $v$ при ребре $u\to v$. Нужно найти минимальный размер множества слов после оптимальных замен. Решение (по записи): сжимаем компоненты сильной связности (внутри цикла можно схлопнуть слова в одно, ничего не теряя); после сжатия получается DAG; ответ не меньше числа его листьев (стоков) — слово из стока некуда «передать»; любую нелистовую вершину можно протолкнуть в сына. Итог: число компонент-стоков.
1:14:13 Условие. Дан связный граф. Какое минимальное число рёбер нужно добавить, чтобы мостов не осталось? Решение. Внутри компоненты рёберной двусвязности мостов нет, поэтому сжимаем такие компоненты — получается дерево (мосты исходного графа). Ответ — $\lceil\ell/2\rceil$, где $\ell$ — число листьев этого дерева (для единственной вершины — 0). Достаточность: соединим листья «через одного» парами; в силу связности деревьев получаются циклы, покрывающие каждое ребро. Нижняя граница: каждый лист нужно «закрыть» хотя бы одним новым ребром, а одно ребро закрывает не более двух листьев.
// Минимальное число рёбер, которые нужно добавить связному графу, чтобы в нём не осталось мостов: ⌈листьев / 2⌉ в дереве компонент рёберной двусвязности.
// Использует Graph и Cut из разбора лекции (мосты одним DFS).
int minEdgesNoBridges(const Graph &g) {
Cut c(g);
vector<int> comp(g.n, -1); int k = 0;
for (int s = 0; s < g.n; s++) { // компоненты рёберной двусвязности: связность без мостов
if (comp[s] >= 0) continue;
comp[s] = k; vector<int> st{s};
while (!st.empty()) { int v = st.back(); st.pop_back(); for (auto [to, id] : g.adj[v]) if (!c.isBridge[id] && comp[to] < 0) { comp[to] = k; st.push_back(to); } }
k++;
}
vector<int> deg(k, 0);
for (int i = 0; i < (int)g.edges.size(); i++) if (c.isBridge[i]) { deg[comp[g.edges[i].first]]++; deg[comp[g.edges[i].second]]++; }
int leaves = 0;
for (int d : deg) leaves += (d == 1);
return (leaves + 1) / 2; // k = 1 (мостов нет) даёт 0
}1:18:33 Динамика состоит из двух частей: состояние и пересчёт. Асимптотика равна (число состояний) × (время пересчёта). Состояние должно хранить достаточно информации о построенной части конструкции (например, для рюкзака — набранный вес). Определение состояния нужно записывать словами (3:09:34: «какая координата за что отвечает») — это полезно и на бумаге.
1:20:00 Простая версия. У динамики, которая решается быстро, почти всегда есть более простая и медленная версия (больше состояний или медленнее пересчёт). Её полезно написать даже на олимпиаде с баллами: (1) это уже начало полного решения (сложное решение обычно — оптимизация медленного); (2) сразу получаете часть баллов; (3) пока пишете, появляются идеи; (4) получаете эталон для стресс-тестов; (5) проверка гипотезы по простой версии быстра.
1:21:42 Оптимизация состояний. (а) Зависимые параметры: на сетке позицию $(i,j)$ можно заменить номером диагонали $i+j$, если остальное зависит только от неё. (б) Если различных ответов мало, а состояний много, можно поменять параметр и значение местами: хранить в состоянии то, что раньше было ответом, а ответом сделать прежний параметр.
1:23:07 Оптимизация пересчёта. Если пересчёт — сумма по отрезку состояний, подойдут префиксные суммы или дерево отрезков. Это отдельная тема (оптимизация динамики).
1:24:48 Состояние — отрезок $[l,r)$ (плюс, возможно, ещё параметр); состояний $O(n^2)$. Пересчитывают в порядке возрастания длины. Рекомендуется использовать полуинтервалы $[l,r)$, как в дереве отрезков: при делении пополам нет «$\pm1$». Три типа пересчёта:
1:30:40 Состояние — вершина $v$ (динамика по поддереву $v$), решается DFS-ом. Пересчёт обычно линеен по числу детей, а так как каждая вершина — ребёнок ровно одной, всего $O(n)$. Типичная запись DFS для дерева: параметры $(v,p)$, соседа, равного родителю, пропускаем.
1:32:42 Динамика на DAG — вариация: пересчёт идёт по всем рёбрам, но нельзя заходить в одну и ту же вершину повторно и обходить поддерево заново. Для DAG пишут мемоизацию: массив динамики инициализируется значением «не посчитано» (например, $-1$); если при входе значение уже есть — возвращаем его.
1:35:09 Надерево. Иногда нужен ответ для «всего дерева без поддерева $v$». Над-дерево $v$ = над-дерево родителя + остальные сыновья родителя. При одном DFS на момент входа в вершину значения для братьев, ещё не посещённых, неизвестны, поэтому делают два прохода: первый считает поддеревья, второй уже знает значения для всех сыновей и передаёт нужное вниз.
1:37:13 Для динамики «по символам» состояние хранит компактную информацию об уже построенной части строки: длину и последний символ; последние два символа (если запрещены три подряд); последний символ и длину серии одинаковых и т.п. Маски — на следующем занятии.
1:39:05 Комбинаторные динамики (ответ — число способов по модулю, обычно $10^9+7$). Частая ошибка — забытый модуль или переполнение. Лектор советует написать структуру с перегруженными операторами, которая сама берёт остатки; сложение и вычитание делаются через условное вычитание вместо деления (операция взятия остатка долгая; замена двух взятий на одно в горячей функции ускоряет примерно в полтора раза). Умножение — только через long long. Ограничение подхода: на личных олимпиадах бывает быстрее просто перечитать код, поэтому полезность зависит от формата.
// Число по модулю: все операции сами берут остаток, сложение и вычитание — без деления (условное вычитание).
const int MOD = 1000000007;
struct Mint {
int x; // всегда 0 <= x < MOD
Mint(long long v = 0) { x = (int)(v % MOD); if (x < 0) x += MOD; }
Mint operator+(Mint o) const { int r = x + o.x; if (r >= MOD) r -= MOD; Mint m; m.x = r; return m; } // сумма < 2·MOD помещается в int
Mint operator-(Mint o) const { int r = x - o.x; if (r < 0) r += MOD; Mint m; m.x = r; return m; }
Mint operator*(Mint o) const { Mint m; m.x = (int)((long long)x * o.x % MOD); return m; } // умножать нужно в long long
Mint &operator+=(Mint o) { return *this = *this + o; }
};
// Мемоизация: функция возвращает значение состояния; уже вычисленное берём из таблицы.
// Пример — число путей из (0,0) в (n,m) по клеткам вправо/вниз.
long long memo[50][50];
long long paths(int i, int j) {
if (i == 0 || j == 0) return 1;
long long &r = memo[i][j]; // ссылка на ячейку: запись значения при выходе
if (r) return r; // уже считали
return r = paths(i - 1, j) + paths(i, j - 1);
}(-1) % 2 == -1. Поэтому в конце выводят (ans % MOD + MOD) % MOD. Сложение нескольких остатков в int переполняется: три числа по модулю $10^9+7$ уже дают около $3\cdot10^9$ (для знакового int предел $2{,}1\cdot10^9$, для беззнакового — $4{,}29\cdot10^9$). Умножать нужно в long long: переполнение знаковых типов — не просто «неверное значение», а неопределённое поведение.1:48:49 Условная вероятность. Если нужно посчитать количество способов при двух условиях $X$ и $Y$, иногда проще: $|X\cap Y|=|X|\cdot P(Y\mid X)$ — вручную «выкинуть» запрещённые варианты. Пример: двоичные строки длины $n$, у которых первый и второй символы не оба единицы: $2^n\cdot\tfrac34$. Лектор признаёт, что пример тривиален и строгий смысл вероятности здесь условный — это приём «выкидывать варианты руками».
1:51:39 Мемоизация — вариант записи динамики без продуманного порядка: функция от состояния рекурсивно вычисляет значение и запоминает его в таблице; при повторном обращении возвращается готовое. Часто проще писать для проверки гипотезы, но рекурсия имеет цену (см. ниже).
1:53:43 Слои. Если динамика зависит только от предыдущего слоя ($dp[i][\cdot]$ зависит от $dp[i-1][\cdot]$), хранят два слоя вместо всей таблицы и меняют их swap (за $O(1)$, а присваивание копировало бы весь вектор). Минус — нельзя восстановить ответ по значениям динамики; но можно хранить целиком только массив «откуда пришли» (меньшего размера), а значения — слоями.
long long против int): (1) вложенные vector<vector<…>> хранятся фрагментарно: обращение — это два перехода по памяти, а рост вектора периодически копирует его; если известна граница, используйте reserve или статические массивы / array; (2) для маленького второго измерения лучше array<int, 5>, чем вложенный vector; tuple и array в коде быстрее вложенных контейнеров; (3) если одно измерение мало, делайте его первым — тогда внутренний цикл идёт по подряд лежащей памяти; (4) map/unordered_map в динамике стоит заменять массивами; (5) для глубокой рекурсии на графах размера $10^6$ стек вызовов переполнится — ограничение для рекурсивного DFS обычно не больше $10^5$–$10^6$; (6) выбирайте тип минимально достаточного размера: int там, где хватает. Это не математика алгоритма, а практика.3:04:33 Классика: $dp[i][j]$ — НОП префикса первого массива длины $i$ и префикса второго длины $j$. Состояние зависит от трёх: $dp[i-1][j]$, $dp[i][j-1]$, $dp[i-1][j-1]$. Каждый «слой» по первой координате зависит только от предыдущего, поэтому храним два слоя (old и new), заполняем new по old и меняем их местами swap. Лучше брать слоем более короткий массив.
// Длина НОП двух массивов за O(nm) времени и O(min(n, m)) памяти: слой i зависит только от слоя i−1.
int lcsLength(const vector<int> &a, const vector<int> &b) {
const vector<int> &x = a.size() >= b.size() ? a : b, &y = a.size() >= b.size() ? b : a; // y — короткий массив
int m = y.size();
vector<int> oldDp(m + 1, 0), newDp(m + 1, 0); // dp[j] — НОП префикса x длины i и префикса y длины j
for (size_t i = 1; i <= x.size(); i++) {
for (int j = 1; j <= m; j++)
newDp[j] = (x[i - 1] == y[j - 1]) ? oldDp[j - 1] + 1 : max(oldDp[j], newDp[j - 1]);
swap(oldDp, newDp); // swap за O(1), копирование было бы за O(m)
}
return oldDp[m];
}3:08:50 Меняем параметр и значение местами. Пусть $d[\ell]$ — наименьшее число, которым может заканчиваться возрастающая подпоследовательность длины $\ell$ на просмотренном префиксе. Массив $d$ возрастает. Новое число $x$ заменяет первый элемент $d[\ell]\ge x$ (lower_bound): подпоследовательность длины $\ell-1$, заканчивающаяся меньше $x$, продолжается числом $x$, а ничего длиннее продлить нельзя; более короткие продолжать не нужно — длина $\ell$ уже достигнута с меньшим концом. За один шаг меняется одна ячейка.
3:11:36 Восстановление. Сохраняем историю изменений $d$ (какая ячейка, на что менялась) и «откатываем» её с конца: когда встречаем изменение, затёршее бесконечность, это число лежит в ответе. Проще (3:15:01): для каждого положенного числа запомнить, какое число стояло в $d$ на предыдущей длине в этот момент (позицию предшественника), и пройти по цепочке назад. Чтобы свести «неубывающую» к «строго возрастающей», заменяем число парой (число, индекс) (3:20:13).
// НВП за O(n log n): d[len] — минимальное число, которым может заканчиваться возрастающая подпоследовательность длины len на просмотренном префиксе.
// d возрастает, поэтому новое x заменяет первое d[len] >= x (lower_bound). Для восстановления храним, на каком месте и кого заменили, и позицию предшественника.
vector<int> lisRestore(const vector<int> &a) {
int n = a.size();
vector<int> d, idx, prv(n, -1); // d[len-1] — значение, idx[len-1] — его позиция в a
for (int i = 0; i < n; i++) {
int len = lower_bound(d.begin(), d.end(), a[i]) - d.begin(); // строго возрастающая: ищем первое >= a[i]
if (len == (int)d.size()) { d.push_back(a[i]); idx.push_back(i); }
else { d[len] = a[i]; idx[len] = i; }
prv[i] = len ? idx[len - 1] : -1; // a[i] продолжает цепочку длины len, заканчивающуюся на idx[len-1]
}
vector<int> res;
for (int i = idx.back(); i >= 0; i = prv[i]) res.push_back(a[i]);
reverse(res.begin(), res.end());
return res;
}3:17:26 Задача. Для каждого $a_i$ определить, в каком режиме он существует относительно наибольших возрастающих подпоследовательностей: (0) не лежит ни в одной; (1) лежит в некоторых, но не во всех; (2) лежит во всех.
3:22:16 Решение. Для каждой позиции считаем два числа слева: $L_i$ — длину самой длинной возрастающей подпоследовательности, заканчивающейся в $a_i$, и $c_i$ — их количество; аналогично справа $R_i$, $d_i$ — для начинающихся в $a_i$. Тогда $a_i$ лежит в какой-то НВП ⇔ $L_i+R_i-1=\ell$, где $\ell$ — длина НВП. Число НВП, проходящих через $a_i$, равно $c_i\cdot d_i$; элемент во всех НВП ⇔ $c_id_i=C$, где $C$ — общее число НВП.
3:24:21 Как посчитать $(L_i,c_i)$. Нельзя воспользоваться бинпоиском с массивом $d$, который затирает информацию о количестве. Используем дерево (Фенвика) по сжатым значениям: в ячейке $v$ лежит пара (длина, количество); запрос на префиксе значений меньше $a_i$ возвращает пару «максимальная длина и сумма количеств у ячеек с этой длиной». Затем новая пара $(\text{len}+1,\text{cnt})$ записывается в ячейку $a_i$.
3:30:13 Количества могут быть огромными (оценка $\sqrt n^{\sqrt n}$ — блоки по $\sqrt n$ убывающих чисел, из каждого можно выбрать любое). Поэтому равенство $c_id_i=C$ проверяют по нескольким простым модулям: вероятность ложного совпадения по трём модулям пренебрежимо мала. Для этого в ДП хранят пары по каждому модулю.
// Для каждого элемента: 0 — не лежит ни в одной НВП, 1 — лежит в некоторых, 2 — лежит во всех НВП (максимальной длины).
// Считаем (длина лучшей НВП, число таких НВП) на конце и на начале в каждой позиции Фенвиком по сжатым значениям (максимум пары с суммой количеств).
// Количества огромны: сравниваем произведение с общим числом по нескольким простым модулям.
typedef long long ll;
typedef unsigned long long ull;
const ll MODS[3] = {1000000007LL, 998244353LL, 1000000009LL};
struct Cell { int len = 0; ll cnt[3] = {0, 0, 0}; };
Cell better(const Cell &x, const Cell &y) { // объединение: большая длина побеждает, при равенстве количества складываются
if (x.len != y.len) return x.len > y.len ? x : y;
Cell r = x; for (int k = 0; k < 3; k++) r.cnt[k] = (x.cnt[k] + y.cnt[k]) % MODS[k];
return r;
}
struct FenMax {
int n; vector<Cell> t;
FenMax(int n) : n(n), t(n + 1) {}
void add(int i, const Cell &c) { for (i++; i <= n; i += i & -i) t[i] = better(t[i], c); }
Cell pref(int i) { Cell r; for (; i > 0; i -= i & -i) r = better(r, t[i]); return r; } // значения с индексом < i
};
vector<int> lisModes(vector<int> a) {
int n = a.size();
vector<int> s(a); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end());
for (int &x : a) x = lower_bound(s.begin(), s.end(), x) - s.begin();
int m = s.size();
vector<Cell> L(n), R(n);
{ FenMax f(m); for (int i = 0; i < n; i++) { // L[i]: НВП, заканчивающиеся в a[i]
Cell c = f.pref(a[i]); if (c.len == 0) { c.len = 0; for (int k = 0; k < 3; k++) c.cnt[k] = 1; }
c.len++; L[i] = c; f.add(a[i], c); } }
{ FenMax f(m); for (int i = n - 1; i >= 0; i--) { // R[i]: НВП, начинающиеся в a[i] (идём справа налево по убыванию)
Cell c = f.pref(m - 1 - a[i]); if (c.len == 0) { c.len = 0; for (int k = 0; k < 3; k++) c.cnt[k] = 1; }
c.len++; R[i] = c; f.add(m - 1 - a[i], c); } }
int best = 0; Cell tot;
for (int i = 0; i < n; i++) tot = better(tot, L[i]);
best = tot.len;
vector<int> mode(n, 0);
for (int i = 0; i < n; i++) {
if (L[i].len + R[i].len - 1 != best) continue; // даже лучшая цепочка через a[i] короче НВП
bool all = true;
for (int k = 0; k < 3; k++) if (L[i].cnt[k] * R[i].cnt[k] % MODS[k] != tot.cnt[k]) all = false;
mode[i] = all ? 2 : 1;
}
return mode;
}3:32:59 Задача. Даны $n$ предметов веса $w_i$ и размер $S$. Для каждого $s\le S$ узнать, можно ли набрать ровно вес $s$. Динамика: $dp[i][s]=dp[i-1][s]\lor dp[i-1][s-w_i]$. Лектор предлагает искать динамику с теми же переменными, что в вопросе, — обычно срабатывает.
3:35:48 Оптимизация. Слой dp — битовая маска достижимых весов. Новый слой — побитовое OR старого и старого, сдвинутого на $w_i$: dp |= dp << w. std::bitset хранит 64 бита в слове, поэтому память и время делятся на 64: итого $O(nS/64)$. Массив bool (даже vector<bool>) в десятки раз медленнее.
// Рюкзак «можно ли набрать вес ровно s» для всех s ≤ SMAX, bitset: новый слой = старый | (старый << w).
const int SMAX = 10000;
vector<bool> reachableSums(const vector<int> &w) {
bitset<SMAX + 1> dp;
dp[0] = 1;
for (int x : w) dp |= dp << x; // 64 состояния за одну операцию процессора
vector<bool> res(SMAX + 1);
for (int s = 0; s <= SMAX; s++) res[s] = dp[s];
return res;
}bitset-рюкзака совпали с перебором подмножеств на 500 случайных наборах.3:46:19 Задача. Даны предметы и запросы $(L,R,W)$: можно ли набрать вес $W$ предметами с номерами из $[L,R]$? Хочется предподсчёт за $O(nW)$ и ответ за $O(1)$. Сведение к префиксу «набрать $W$ на префиксе минус $K$ на другом префиксе» неверно — вычитание сумм не годится.
3:48:03 Идея: поменять параметры. Пусть $dp[i][s]$ — максимальный левый конец $g$ такой, что предметами с номерами $g,\dots,i$ можно набрать вес $s$ (или $-1$). Чем больше предметов мы берём (меньше $g$), тем больше сумм достижимо — монотонно. Пересчёт: либо не берём предмет $i$ ($dp[i-1][s]$), либо берём ($\min(dp[i-1][s-w_i],\,i)$); берём максимум. Запрос: $dp[R][W]\ge L$.
// Запросы (L, R, W): можно ли набрать вес W предметами с номерами из [L, R]? dp[i][s] — максимальное g такое, что из предметов g..i можно набрать s (−1, если нельзя).
// Чем больше предметов берём (g меньше), тем больше сумм достижимо — монотонность по g.
const int SM = 1000;
struct SegKnap {
int n; vector<array<int, SM + 1>> dp;
SegKnap(const vector<int> &w) : n(w.size()), dp(w.size() + 1) {
dp[0].fill(-1); dp[0][0] = 1 << 30; // пустой набор даёт сумму 0 при любом g
for (int i = 1; i <= n; i++)
for (int s = 0; s <= SM; s++) {
if (s == 0) { dp[i][0] = 1 << 30; continue; } // сумма 0 набирается пустым набором при любом g
int best = dp[i - 1][s]; // предмет i не берём
if (s >= w[i - 1] && dp[i - 1][s - w[i - 1]] >= 0) best = max(best, min(dp[i - 1][s - w[i - 1]], i)); // берём i
dp[i][s] = best;
}
}
bool query(int L, int R, int W) { return dp[R][W] >= L; } // номера предметов 1..n
};3:51:58 Дано $n$ предметов с весом $w_i$ и стоимостью $c_i$; максимизировать стоимость при суммарном весе $\le B$. Если $B$ небольшое — $dp[i][v]$ = максимальная стоимость при весе $v$ за $O(nB)$. Если вес $B$ огромен, а сумма стоимостей мала — меняем: $dp[c]$ — минимальный вес, которым набирается стоимость $c$, переход $dp[c]=\min(dp[c],dp[c-c_i]+w_i)$ за $O(n\cdot\sum c)$; ответ — наибольшее $c$ с $dp[c]\le B$.
// Рюкзак: максимум стоимости при суммарном весе ≤ B. Если вес большой, а сумма стоимостей мала, меняем параметр и значение местами:
// dp[c] — минимальный вес, которым можно набрать стоимость ровно c; ответ — максимальное c с dp[c] ≤ B.
typedef long long ll;
ll knapsackByCost(const vector<int> &w, const vector<int> &cost, ll B) {
int total = accumulate(cost.begin(), cost.end(), 0);
const ll INF = LLONG_MAX / 4;
vector<ll> dp(total + 1, INF);
dp[0] = 0;
for (size_t i = 0; i < w.size(); i++)
for (int c = total; c >= cost[i]; c--) // c по убыванию — предмет берётся не более одного раза
dp[c] = min(dp[c], dp[c - cost[i]] + w[i]);
ll best = 0;
for (int c = 0; c <= total; c++) if (dp[c] <= B) best = c;
return best;
}3:57:31 Условие. $n$ детей, $i$-й может съесть не более $a_i$ конфет; нужно раздать ровно $K$ конфет (можно некоторым не дать ничего). Сколько способов (по модулю)?
3:59:18 Динамика. $dp[i][k]$ — число способов раздать $k$ конфет первым $i$ детям. Последнему даём $t\in[0,a_i]$: $dp[i][k]=\sum_{t=0}^{\min(a_i,k)}dp[i-1][k-t]$. Прямо это $O(K^2)$ на слой.
4:01:06 Оптимизация. Это сумма в окне длины $a_i+1$ предыдущего слоя. При переходе $k\to k+1$ окно сдвигается на единицу: прибавляется $dp[i-1][k+1]$ и вычитается $dp[i-1][k-a_i]$ (если индекс существует): $dp[i][k+1]=dp[i][k]+dp[i-1][k+1]-dp[i-1][k-a_i]$. Итого $O(nK)$ времени, а так как слой зависит только от предыдущего, память $O(K)$.
// Сколько способов раздать ровно K конфет детям, если i-й готов съесть не более a_i (можно ничего не дать)? Ответ по модулю MOD.
// dp[i][k] = Σ_{t=0..min(a_i,k)} dp[i−1][k−t] — сумма в скользящем окне; пересчёт за O(1) вместо O(a_i).
const long long MOD = 998244353;
long long candyWays(const vector<int> &a, int K) {
vector<long long> prev(K + 1, 0), cur(K + 1, 0);
prev[0] = 1;
for (int ai : a) {
cur[0] = prev[0];
for (int k = 1; k <= K; k++) {
cur[k] = (cur[k - 1] + prev[k]) % MOD; // окно [k−ai, k] получено из окна [k−1−ai, k−1] сдвигом на 1
if (k - ai - 1 >= 0) cur[k] = (cur[k] - prev[k - ai - 1] + MOD) % MOD; // выпавший слева элемент вычитаем
}
swap(prev, cur);
}
return prev[K];
}4:06:03 Условие. Бревно длины $L$ с заданными отсечками $x_1<\dots<x_n$; разрезать по всем отсечкам. Разрез бревна (куска) длины $\ell$ стоит $\ell$. Найти минимальную суммарную стоимость. Жадные идеи (резать ближе к середине массива или по середине бревна) не работают.
4:07:25 Динамика по подотрезкам. Пусть отсечки $x_0=0,\dots,x_{n+1}=L$ (концы тоже). $dp[l][r]$ — минимальная стоимость полностью разрезать кусок между отсечками $l$ и $r$. База: $dp[l][l+1]=0$ (резать нечего). При $r-l\ge2$ выбираем отсечку $k\in(l,r)$ первого разреза: платим $x_r-x_l$ и затем независимо режем два куска:
Считаем по возрастанию длины $r-l$ (оба куска короче). Ответ — $dp[0][n+1]$. Время $O(n^3)$.
// Бревно длиной xs.back(), отсечки xs[0]=0 < xs[1] < ... < xs[m]. Разрез бревна длины ℓ стоит ℓ. dp[l][r] — минимальная стоимость разрезать кусок между отсечками l и r полностью.
typedef long long ll;
ll cutLog(const vector<ll> &xs) {
int m = xs.size(); // отсечек m (включая концы)
vector<vector<ll>> dp(m, vector<ll>(m, 0));
for (int len = 2; len < m; len++) // по возрастанию длины отрезка отсечек
for (int l = 0; l + len < m; l++) {
int r = l + len; dp[l][r] = LLONG_MAX;
for (int k = l + 1; k < r; k++) // первый разрез проводим по отсечке k
dp[l][r] = min(dp[l][r], xs[r] - xs[l] + dp[l][k] + dp[k][r]);
}
return dp[0][m - 1];
}4:14:25 Условие. Из строки разрешается за одну операцию вырезать любую подстроку-палиндром (остатки склеиваются). Найти минимальное число операций, чтобы стереть строку. Лектор замечает, что жадность (вырезать самый длинный палиндром — например, алгоритмом Манакера) не работает; нужна динамика по подотрезкам.
4:15:46 Динамика. $f[l][r]$ — минимум операций для строки $s[l..r)$. Рассмотрим, с кем удаляется первая буква $s[l]$. Варианты: (1) сама по себе — $1+f[l+1][r]$; (2) в одном палиндроме с соседней, если $s[l]=s[l+1]$ — $1+f[l+2][r]$; (3) в одном палиндроме с некоторой $s[k]$, $s[k]=s[l]$, $k>l+1$: тогда внутренность $s[l+1..k)$ стирается раньше, и в последней её операции палиндром достраивается краями $s[l]$ и $s[k]$ — операций не прибавляется: $f[l+1][k]+f[k+1][r]$. Минимум по вариантам. Время $O(n^3)$.
// За одну операцию можно вырезать палиндром-подстроку (оставшиеся части склеиваются). Минимум операций, чтобы стереть строку. O(n³).
// f[l][r] — для s[l..r). Первая буква s[l] стирается: сама по себе; вместе с соседней (если равны); или вместе с s[k] (s[k] == s[l]), тогда внутренность s[l+1..k) стирается раньше,
// а её последний палиндром достраивается краями s[l] и s[k] (операций не прибавляется).
int minPalRemovals(const string &s) {
int n = s.size();
vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; len++)
for (int l = 0; l + len <= n; l++) {
int r = l + len;
if (len == 1) { f[l][r] = 1; continue; }
int best = 1 + f[l + 1][r]; // s[l] стираем отдельно
if (s[l] == s[l + 1]) best = min(best, 1 + f[l + 2][r]); // s[l] и s[l+1] — вместе, в одном палиндроме
for (int k = l + 2; k < r; k++)
if (s[k] == s[l]) best = min(best, f[l + 1][k] + f[k + 1][r]); // s[l] и s[k] — края одного палиндрома
f[l][r] = best;
}
return f[0][n];
}4:20:57 Условие. Дано взвешенное дерево. Для каждой вершины найти сумму расстояний до всех остальных за линейное время.
4:22:00 Решение. Для корня сумма считается динамикой по поддеревьям: $down[v]=\sum_u(down[u]+w_u\cdot sz_u)$ — сумма расстояний до вершин поддерева. Затем переподвешивание: корень можно переносить по ребру. Лектор описывает это как операции «отрезать ребёнка от корня» и «подвесить родителя к ребёнку»: динамика вершины быстро пересчитывается при добавлении или удалении сына (прибавить или вычесть $w\cdot sz$). Обходя дерево DFS-ом, мы делаем корнем каждую вершину по очереди, и для текущего корня ответ известен. Эквивалентная формула: при переходе корня по ребру $(p,v)$ веса $w$ ответ меняется на $w\,(n-2\,sz_v)$.
// Сумма расстояний от каждой вершины до всех остальных в дереве с весами рёбер (переподвешивание). Без рекурсии, O(n).
typedef long long ll;
vector<ll> sumDist(int n, const vector<array<int,3>> &edges) { // (a, b, вес)
vector<vector<pair<int,int>>> g(n);
for (auto &e : edges) { g[e[0]].push_back({e[1], e[2]}); g[e[1]].push_back({e[0], e[2]}); }
vector<int> order, par(n, -1), pw(n, 0);
order.push_back(0);
for (size_t i = 0; i < order.size(); i++) { int v = order[i]; for (auto [to, w] : g[v]) if (to != par[v]) { par[to] = v; pw[to] = w; order.push_back(to); } }
vector<ll> sz(n, 1), down(n, 0), ans(n, 0);
for (int i = n - 1; i > 0; i--) { int v = order[i]; sz[par[v]] += sz[v]; down[par[v]] += down[v] + (ll)pw[v] * sz[v]; }
ans[0] = down[0]; // ответ для корня — сумма «вниз»
for (int i = 1; i < n; i++) { int v = order[i]; ans[v] = ans[par[v]] + (ll)pw[v] * (n - 2 * sz[v]); } // сдвиг корня на ребро (p, v)
return ans;
}4:26:26 Паросочетание — набор рёбер без общих вершин. Динамика по поддеревьям: $dp_0[v]$ — максимум в поддереве $v$, если $v$ никому не поставлена пара; $best[v]$ — максимум вообще. $dp_0[v]=\sum_u best[u]$ (дети независимы; лектор подчёркивает, что вершину не брать выгодно в теории). Чтобы посчитать $best[v]$, перебираем ребёнка $u$, с которым $v$ в паре: вычитаем $best[u]$, добавляем $dp_0[u]$ ($u$ при этом свободна) и ещё $1$ за ребро: $\max_u\bigl(\sum-best[u]+dp_0[u]+1\bigr)$. Берём максимум с $dp_0[v]$.
// Максимальное паросочетание в дереве: dp0[v] — максимум в поддереве v, если v никому не поставлена пара; dp1[v] — максимум, где v занята (или не имеет значения).
// Здесь dp1 храним как «лучшее значение вообще», dp0 как «v свободна».
struct TreeMatch {
int n; vector<vector<int>> g; vector<int> free0, best; // free0[v]: v свободна; best[v] = максимум по поддереву v
TreeMatch(int n) : n(n), g(n), free0(n), best(n) {}
void addEdge(int a, int b) { g[a].push_back(b); g[b].push_back(a); }
void dfs(int v, int p) {
int sum = 0;
for (int to : g[v]) if (to != p) { dfs(to, v); sum += best[to]; }
free0[v] = sum; // v свободна: дети независимы
best[v] = sum;
for (int to : g[v]) if (to != p) // пара v—to: у to должна быть свободная вершина
best[v] = max(best[v], sum - best[to] + free0[to] + 1);
}
int solve() { dfs(0, -1); return best[0]; }
};4:30:18 Условие. Сколько чисел от $L$ до $R$ ($R$ порядка $10^{5}$ цифр — строка) имеют сумму цифр ровно $S$?
4:31:00 Решение. Запрос на $[L,R]$ сводится к $f(R)-f(L-1)$, где $f(X)$ — число подходящих чисел от $0$ до $X$. Состояние: $(i,s,t)$ — собрали $i$ цифр, сумма цифр $s$, $t=1$, если префикс уже строго меньше префикса $R$ (иначе равен ему). Числа сравнивают слева направо, до первой различающейся позиции, поэтому при $t=0$ следующая цифра не больше цифры $R$ (если строго меньше — $t$ становится $1$, если равна — остаётся $0$), а при $t=1$ — любая. Время $O(\text{длина}\cdot S\cdot10)$.
// Сколько чисел от 0 до R (R — строка цифр) имеют сумму цифр ровно S? Для отрезка [L, R]: f(R) − f(L − 1).
// dp[i][s][t]: собрали i цифр, сумма s, t = 1, если префикс уже строго меньше префикса R.
typedef long long ll;
ll countDigitSum(const string &R, int S) {
int n = R.size();
vector<vector<array<ll,2>>> dp(n + 1, vector<array<ll,2>>(S + 1, {0, 0}));
dp[0][0][0] = 1;
for (int i = 0; i < n; i++)
for (int s = 0; s <= S; s++)
for (int t = 0; t < 2; t++) {
ll cur = dp[i][s][t];
if (!cur) continue;
int lim = t ? 9 : R[i] - '0'; // если ещё равны R, следующая цифра ≤ цифры R; иначе любая
for (int d = 0; d <= lim && s + d <= S; d++)
dp[i + 1][s + d][t || d < lim] += cur;
}
return dp[n][S][0] + dp[n][S][1];
}4:34:50 Условие (по записи). Сколько чисел на отрезке делятся на каждую свою ненулевую цифру?
4:35:14 Идея лектора. НОК всех чисел $1..9$ равен $2520$, различных значений НОК цифр — 48 (делители 2520). Предлагается перебирать НОК цифр, считать динамику с остатком по этому НОК и убирать дубли (числа, чьи цифры порождаются несколькими НОК), вычитая вклады меньших НОК. Лектор разбирает пример «73» — число засчитывается при нескольких НОК.
// Сколько x ∈ [0, R], делящихся на каждую свою ненулевую цифру? Состояние: (позиция, флаг «меньше R», НОК цифр (48 делителей 2520), остаток по модулю 2520).
typedef long long ll;
ll countDivisibleByDigits(const string &R) {
vector<int> divs; for (int d = 1; d <= 2520; d++) if (2520 % d == 0) divs.push_back(d);
int D = divs.size();
vector<int> id(2521, -1); for (int i = 0; i < D; i++) id[divs[i]] = i;
int n = R.size();
auto lcm = [](int a, int b) { return a / gcd(a, b) * b; };
// dp[флаг][индекс НОК][остаток]
vector<vector<vector<ll>>> cur(2, vector<vector<ll>>(D, vector<ll>(2520, 0))), nxt = cur;
cur[0][id[1]][0] = 1;
for (int i = 0; i < n; i++) {
for (auto &a : nxt) for (auto &b : a) fill(b.begin(), b.end(), 0);
for (int t = 0; t < 2; t++) for (int li = 0; li < D; li++) for (int r = 0; r < 2520; r++) {
ll c = cur[t][li][r]; if (!c) continue;
int lim = t ? 9 : R[i] - '0';
for (int d = 0; d <= lim; d++) {
int nl = d ? id[lcm(divs[li], d)] : li;
nxt[t || d < lim][nl][(r * 10 + d) % 2520] += c;
}
}
swap(cur, nxt);
}
ll ans = 0;
for (int t = 0; t < 2; t++) for (int li = 0; li < D; li++) for (int r = 0; r < 2520; r++)
if (cur[t][li][r] && r % divs[li] == 0) ans += cur[t][li][r]; // остаток по 2520 делится на НОК ⇒ число делится на НОК
return ans;
}4:41:29 Идея. Если есть $b$ одинаковых предметов веса $a$, заменим их на $O(\log b)$ предметов. Берём веса $a\cdot1,\ a\cdot2,\ a\cdot4,\dots,a\cdot2^{k-1}$, пока сумма $2^k-1$ не превысит $b$, и последний предмет — остаток $r=b-(2^k-1)$ (если он положителен). Любое количество $t\in[0,b]$ собирается: при $t\le2^k-1$ — двоичным разложением; иначе вычтем остаток, $t-r\le2^k-1$, и снова разложим по степеням двойки. При этом больше $b$ собрать нельзя. Предметов стало $O(\log b)$ вместо $b$.
4:46:42 Много разных предметов с суммой $S$. Различных весов не больше $\sqrt{2S}$ (иначе сумма превысит $S$): если различных значений $k$, то сумма $\ge k(k+1)/2$. Сгруппируем одинаковые предметы, каждую группу заменим $O(\log)$ предметами и запустим рюкзак на bitset: получаем $O(S\sqrt S\log S/64)$ плюс $O(n)$ на группировку (лектор даёт грубую оценку; настоящая лучше, так как веса возрастают).
// Ограниченный рюкзак: предметы веса a в количестве c заменяем на O(log c) предметов a·1, a·2, a·4, ..., и остаток.
// Любое количество 0..c собирается из них, больше c — нет.
vector<int> splitBinary(int a, int c) {
vector<int> res;
for (int p = 1; c > 0; p <<= 1) { int t = min(p, c); res.push_back(a * t); c -= t; }
return res;
}4:49:28 Условие (по записи, неполное). Стоим в 0 и прыгаем вправо. Первый прыжок имеет длину $d$; каждый следующий — длина предыдущего $-1$, такая же или $+1$ (длина $\ge1$). В клетках лежат монеты. Максимизировать собранное. (Лектор отмечает сходство с задачей отбора.)
4:49:49 Ключевое наблюдение. Если длина прыжка менялась от $d$ до $d+\delta$, то сумма длин прыжков не меньше $d+(d+1)+\dots$; значит, число различных значений длины на пути не превосходит $O(\sqrt{M})$ ($M$ — число клеток): иначе сумма прыжков превысит $M$. Поэтому состояние $dp[x][\ell]$ (последний прыжок длины $\ell$ привёл в клетку $x$) нужно хранить только для $|\ell-d|\le\sqrt{2M}\approx245$ — окно длиной около 500 вместо $M$. Вместо map (лишний $\log$) индекс хранится сдвигом на $d$: ноль окна соответствует длине $d-245$ (4:53:40).
// Прыжки вправо: первый прыжок длины d, каждый следующий длиннее/такой же/короче на 1 (длина ≥ 1). Монеты лежат в клетках; максимум собранного (старт в 0).
// Сумма длин ≥ 1+2+...+k, поэтому длина отличается от d не более чем на ~√(2·M) (M — число клеток): храним только «окно» длин вокруг d.
int maxCoins(int M, int d, const vector<int> &coin) { // coin[x] — монет в клетке x (0..M)
const int OFF = 250; // для M ≤ 30000: |длина − d| ≤ 245
vector<vector<int>> dp(M + 1, vector<int>(2 * OFF + 1, -1));
int ans = 0;
if (d <= M) dp[d][OFF] = coin[d];
for (int x = d; x <= M; x++)
for (int o = 0; o <= 2 * OFF; o++) {
if (dp[x][o] < 0) continue;
ans = max(ans, dp[x][o]);
int len = d + o - OFF;
for (int nl = len - 1; nl <= len + 1; nl++) {
if (nl < 1) continue;
int no = nl - d + OFF;
if (no < 0 || no > 2 * OFF || x + nl > M) continue;
dp[x + nl][no] = max(dp[x + nl][no], dp[x][o] + coin[x + nl]);
}
}
return ans;
}4:56:48 Условие. Здание на $N$ этажей, $K$ одинаковых телефонов. Есть неизвестный порог: с этого этажа и выше телефон разбивается при падении. Разбитый телефон использовать нельзя, целый — можно бросить ещё раз. Какое минимальное число бросков гарантированно хватит, чтобы найти порог? (Лектор: «лучшая задача семинара».)
4:58:09 Динамика. $dp[n][k]$ — минимальное число бросков, которого гарантированно хватает при $n$ этажах и $k$ телефонах (важна только длина интервала, а не его положение). База: нет телефонов — этажи не различить (бесконечность), нет этажей — 0. Бросаем с $x$-го этажа: разбился — остаётся $x-1$ этаж и $k-1$ телефон; цел — $n-x$ этажей и $k$ телефонов. Худший случай — максимум, лучший выбор $x$ — минимум: $dp[n][k]=1+\min_x\max\bigl(dp[x-1][k-1],\,dp[n-x][k]\bigr)$. Запись обрывается на этом месте.
// Телефоны (яйца): K телефонов, N этажей. Минимальное число бросков в худшем случае, чтобы найти первый «разбивающий» этаж. O(K·N²).
int eggsSlow(int K, int N) {
vector<vector<int>> f(K + 1, vector<int>(N + 1, 0)); // f[k][n]: k телефонов, n этажей (неизвестен порог среди n этажей)
for (int n = 1; n <= N; n++) f[0][n] = INT_MAX / 2; // без телефонов этажи не различить
for (int k = 1; k <= K; k++)
for (int n = 1; n <= N; n++) {
f[k][n] = INT_MAX;
for (int x = 1; x <= n; x++) // бросаем с x-го этажа: разбился → x−1 этажей, k−1 телефонов; цел → n−x этажей, k телефонов
f[k][n] = min(f[k][n], 1 + max(f[k - 1][x - 1], f[k][n - x]));
}
return f[K][N];
}
// Перевёрнутая динамика (меняем параметр и значение местами): g[t][k] — сколько этажей можно разобрать за t бросков с k телефонами.
// Бросок: разбился → g[t−1][k−1] этажей ниже, цел → g[t−1][k] этажей выше, плюс сам этаж: g[t][k] = g[t−1][k−1] + g[t−1][k] + 1.
int eggsFast(int K, int N) {
vector<long long> g(K + 1, 0);
int t = 0;
while (g[K] < N) {
t++;
for (int k = K; k >= 1; k--) g[k] = g[k - 1] + g[k] + 1; // k по убыванию — используем значения предыдущего слоя
}
return t;
}