Разбор задач 26.12.2016
Задача 1. Незнайка учиться считать
Постановка задачи
Решение
Трудности
Задача 2. Поврежденная карта
Постановка задачи
Решение
Задача 3. Abracadabra
Постановка задачи
Решение
Решение (1)
Пример
Пример (1)
Задача 4. Землетрясение
Постановка задачи
Решение
Решение (1)
73.96K
Category: mathematicsmathematics

Разбор задач

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

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

Областная олимпиада 2005 года
ЗАДАЧА 1. НЕЗНАЙКА УЧИТЬСЯ
СЧИТАТЬ

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

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

4. Решение

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

5. Трудности

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

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

Областная олимпиада 2005 года
ЗАДАЧА 2. ПОВРЕЖДЕННАЯ
КАРТА

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 год
ЗАДАЧА 3. ABRACADABRA

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

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

11. Решение

• Преобразуем каждую строку t, состоящую
из n символов к виду:
t0 tn-1 t1 tn-2 … tn-2 t1 tn-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
ЗАДАЧА 4. ЗЕМЛЕТРЯСЕНИЕ

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));
English     Русский Rules