Про графы [см. 2012-02-09]

1. Сила dfs-а
1. 2-связность (реберная и вершинная, алгоритм со стэком)
2. Гамильтоновы путь и цикл
1. Динамика за 2ⁿ n² (состояние = множество посещенных вершин и последняя посещенная)
2. Полный перебор
3. Эвристика конем
4. Эвристика связности

Про игры [см. 2012-02-16]

1. Функция Смита (без док-ва)
1. Смысл: то же, что и Гранди, только с циклами
2. Определение
3. Вычисление функции Смита за O(VE) = whil (run) do

Перебор

1. Полный перебор.
1. Рекурсия.
2. Мир глобален, не копируется, после отката из рекурсии возвращается в старое состояние.
2. Метод Ветвей и Границ (на примере задачи timus : 1152)
1. Жадность и перебор с сортировкой ребер
2. Выбор первых k ребер.
3. Iterative Increasing of k
4. Нерекурсивная реализация bfs-ом. Очередь с ограничением по длине.

Задачи про перебор

1. Японский комьютер: нужно получить какое-то множество чисел от 1 до 42. Изначально есть только число 1. Допустимые операции: +, -, *2^k.
2. Поезда: заказ = отрезок [L_i, R_i] и кол-во пассажиров K_i. Вместимость поезда = C, нужно принять max число заявок.

Задачи (примеры) к графам

1. Найти путь из A в B : max вес ребра в пути минимален
2. Для каждой пары вершина A и B сделать (1)
3. Дополнить граф до связного
4. Дополнить граф до сильносвязного
5. Найти диаметр графа (2 самые удаленные вершины)
6. Найти диаметр дерева
7. Проверить, является ли граф деревом
8. Число способов пройти по шахматной доске конем из (1,1) в (N,N).
9. Маша и грибы (Маша ходит по матрице и собирает грибы, ходить можно только вниз и вправо, нельзя врезаться в деревья).
10. Найти расстояние от множества A до множества B в невзвешенном графе.
11. Найти расстояние от множества A до множества B во взвешенном графе.
12. Not read Разбить кактус на циклы

Стурктуры данных

1. Частичные суммы
1. sum[R+1] - sum[L]
2. Обобщение на плоскость
3. Sparse Table для минимума
4. Обобщение на дерево
5. Двоичный подъем по дереву для нахождения LCA и минимума, и суммы на пути