Разбор прошлых задач и Структуры данных (9 октября 2014)

  1. Разбор задач на бинарный поиск
    1. Найти, сколько чисел от L до R [code] [code]
    2. Найти, сколько раз на отрезке [L..R] встречается число X [code]
  2. Ближайшие точки
    1. Код на C++ за O(nlog2n)
    2. Убираем лишний корень, улучшаем асимптотику до O(nlogn), пишем внутри while вместо for(i,8) [code]
    3. Далем ошибку (перебираем только 3 следующие точки), пытаемся ее найти тестированием [code]
  3. Вектор и начало амортизационного анализа
    1. Dequeue на массиве: {Pop,Push}{Front,Back} + индексация, все за O(1)
    2. Время работы вектора с удвоением.
    3. Вектор с удвоением без амортизации за O(1) в хедшем случае на одну операцию
    4. Тестируем вектор на C++
      1. a[i], a.at(i), struct myVector : vector [code]
      2. resize, reverse, clear
      3. Проблема большого числа маленьких векторов: переопределяем аллокатор [code]
      4. Быстрая реализация мультисписка [code]
  4. Решение задач на стек и скобочные последовательности
    1. Проверить на правильность, несколько типов скобок + найти парные скобки
    2. Отрезок с максимальной суммой: частичные суммы + частичные минимумы. Стек с минимумом.
    3. Ближайший слева меньший, ближайший справа меньший
    4. Массив положительных чисел, ищем отрезок: ∑ × min → max
    5. Ищем за O(wh) подпрямоугольник из нулей максимальной площади