Презентация на тему "Разбор задач 26.12.2016"

Содержание

• 
  Слайд 1

  Разбор задач 26.12.2016

• 
  Слайд 2

  Задача 1. Незнайка учиться считать

  Областная олимпиада 2005 года

• 
  Слайд 3

  Постановка задачи

  Дана строка, состоящая из цифр; Найти такую подстроку, которая представляет собой последовательность подряд идущих натуральных чисел и является самой длинной по количеству чисел.

• 
  Слайд 4

  Решение

  Перебираем начальную позицию, с которой начинается искомая последовательность; Перебираем длину начального числа; Прибавляем единицу к начальному числу и проверяем следующее; Проделываем тоже самое до тех пор пока строка не закончится либо число не будет удовлетворять последовательности; Сложность решения O(|S|3).

• 
  Слайд 5

  Трудности

  Прибавление единицы к длинному числу (представленному в виде массива); 0 не является натуральным числом;

• 
  Слайд 6

  Задача 2. Поврежденная карта

  Областная олимпиада 2005 года

• 
  Слайд 7

  Постановка задачи

  Дан двумерный массив, состоящий из нулей и единиц; Найти наибольший по площади квадратный подмассив, который состоит из единиц; Вычислить площадь найденного подмассива.

• 
  Слайд 8

  Решение

  Задача решается с помощью динамического программирования; Пусть A – исходный массив, D – массив состояний ДП; D[i][j] – максимальная площадь квадрата из единиц, правая нижняя вершина которого находится в точке (i, j); Если клетка (i, j) повреждена, то D[i][j] = 0; Если не повреждена D[i][j] = min(D[i – 1][j], D[i][j – 1], D[i – 1][j – 1]) + 1; Первая строка и первый столбец заполняются отдельно D[1][j] = A[1][j] и D[i][1] = A[i][1]; Сложность решения O(N * M);

• 
  Слайд 9

  Задача 3. Abracadabra

  Региональная олимпиада РФ за 2012 год

• 
  Слайд 10

  Постановка задачи

  Дан набор строк s1, s2, s3, …, sm; Для каждой из строк siопределить сколько слов из словаря t1, t2, …, tnимеют суффикс и префикс равный si; iй суффикс – это последние iсимволов строки t; iй префикс – это первые iсимволов строки t;

• 
  Слайд 11

  Решение

  Преобразуем каждую строку t, состоящую из n символовк виду: t0 tn-1t1 tn-2 … tn-2 t1tn-1 t0 Например слово table будет преобразовано в tealbblaet Отсортируем преобразованный словарь в лексикографическом порядке; Таким образом, все слова с одинаковым супрефиксом идут подряд;

• 
  Слайд 12

  Решение (1)

  Для каждой из строк s проделаем аналогичное преобразование; Двоичным поиском найдем самое левое вхождение (left) и самое правое вхождение (right); Тогда ответом для строки siбудет right – left + 1; Сложность решения O(n * Log(m));

• 
  Слайд 13

  Пример

  Пусть задан набор строк из примера задачи; Тогда строки будут преобразованы следующим образом: abacaba => aabbaaccaabbaa; abracadabra => aabrrbaacdaadcaabrrbaa; aa => aaaa; abra => aabrrbaa;

• 
  Слайд 14

  Пример (1)

  Отсортируем словарь в лексикографическом порядке: aaaa aabbaaccaabbaa aabrrbaacdaadcaabrrbaa aabrrbaa Для образца a (aa) left = 1, right = 4, ответ = 4; Для образца abra (aabrrbaa) left = 3, right = 4, ответ = 2; Для образца abac (acbaabca) left = -1, right = -1, ответ = 0;

• 
  Слайд 15

  Задача 4. Землетрясение

  USACO Open 2001

• 
  Слайд 16

  Постановка задачи

  Задан неориентированный граф из N вершин и M ребер; Каждое из ребер необходимо восстановить за время tи потратив на это cденежных единиц; Задача состоит в том, чтобы восстановить ребра таким образом, чтобы граф оказался связным; При этом обещано вознаграждение F за выполненную задачу; Требуется вычислить максимально возможную прибыльность (т.е. количество денег, которые можно заработать за час работы);

• 
  Слайд 17

  Решение

  Допустим, что нам известна прибыльность работv; Тогда очевидно, что мы можем вычислить стоимость каждого из ребер как t * v + c: первое слагаемое – полученная прибыть, второе – стоимость восстановления дороги; В этом случае мы можем построить минимальное остовное дерево и если его стоимость меньше вознаграждения F, то такая прибыльность нам подходит;

• 
  Слайд 18

  Решение (1)

  Заметим, что если увеличивать прибыльность v, то и стоимость дерева будет расти; Следовательно, cost(v) – возрастающая (монотонная функция); Таким образом, v можно перебирать двоичным поиском; Найденное оптимальное значение прибыли и будет ответом; Сложность решения O(Log(C * M) * M * Log(M));