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

  1. Сила dfs-а
    1. 2-связность (реберная и вершинная, алгоритм со стэком)

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

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

Перебор

  1. Полный перебор (на примере задачи paths с контеста)
    1. Рекурсия.
    2. Мир глобален, не копируется, после отката из рекурсии возвращается в старое состояние.

Задачи (примеры) к теме перебор

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

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

  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. Д.З. Разбить кактус на циклы

Задачи (примеры) на стурктуры данных

  1. Найти подотрезок с максимальной суммой.
  2. Найти подматрицу с оптимальной суммой.
  3. Найти путь в дереве с XOR-ом всех чисел = нолю.
  4. Пусть у нас есть массив перестановок и запрос на отрезке [L..R] = применить все перестановки с L-й по R-ю.

Одномерные Структуры данных

  1. Не меняющийся массив - продолжение
    1. Минимум на отрезке фиксированной длины за O(1) с предподсчетом за O(N)
    2. Обобщение до матрицы
  2. Меняющийся массив
    1. Корневая оптимизация [sqrt(N)]
    2. Отложенныее операции [sqrt(N)]
    3. Одномерное Дерево Отрезков для суммы (запрос снизу) [logN]
    4. Дерево Фенвика для суммы [logN]
  3. Деревья отрезков
    1. Запрос снизу для суммы, для минимума, для любой ассоциативной операции
    2. Запрос сверху
    3. += на отрезке для запросов сверху
    4. присваивание на отрезке для запросов сверху
    5. Решение задачи K-е число в множестве
    6. Решение задачи следующее число в множестве
  4. LCA в дереве = RMQ на отрезке (RMQ ±1) [Эйлеров обход за O(N)]
  5. RMQ на отрезке = LCA в дереве [постоение Декартового Дерева за O(N)], получили LCA за [O(NlogN), O(1)]
  6. Сумма в дереве (даже меняющемся) = LCA + сумма на отрезке