Разбор задач

Август 4, 2022

Главная
Математика
Разбор задач

Содержание

2. ЗАДАЧА 1. НЕЗНАЙКА УЧИТЬСЯ СЧИТАТЬ Областная олимпиада 2005 года
3. Постановка задачи Дана строка, состоящая из цифр; Найти такую подстроку, которая представляет собой последовательность подряд идущих
4. Решение Перебираем начальную позицию, с которой начинается искомая последовательность; Перебираем длину начального числа; Прибавляем единицу к
5. Трудности Прибавление единицы к длинному числу (представленному в виде массива); 0 не является натуральным числом;
6. ЗАДАЧА 2. ПОВРЕЖДЕННАЯ КАРТА Областная олимпиада 2005 года
7. Постановка задачи Дан двумерный массив, состоящий из нулей и единиц; Найти наибольший по площади квадратный подмассив,
8. Решение Задача решается с помощью динамического программирования; Пусть A – исходный массив, D – массив состояний
9. ЗАДАЧА 3. ABRACADABRA Региональная олимпиада РФ за 2012 год
10. Постановка задачи Дан набор строк s1, s2, s3, …, sm; Для каждой из строк si определить
11. Решение Преобразуем каждую строку t, состоящую из n символов к виду: t0 tn-1 t1 tn-2 …
12. Решение (1) Для каждой из строк s проделаем аналогичное преобразование; Двоичным поиском найдем самое левое вхождение
13. Пример Пусть задан набор строк из примера задачи; Тогда строки будут преобразованы следующим образом: abacaba =>
14. Пример (1) Отсортируем словарь в лексикографическом порядке: aaaa aabbaaccaabbaa aabrrbaacdaadcaabrrbaa aabrrbaa Для образца a (aa) left
15. ЗАДАЧА 4. ЗЕМЛЕТРЯСЕНИЕ USACO Open 2001
16. Постановка задачи Задан неориентированный граф из N вершин и M ребер; Каждое из ребер необходимо восстановить
17. Решение Допустим, что нам известна прибыльность работ v; Тогда очевидно, что мы можем вычислить стоимость каждого
19. Скачать презентацию

Слайд 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-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

Слайд 16

Постановка задачи
Задан неориентированный граф из N вершин и M ребер;
Каждое из

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

Слайд 17

Решение
Допустим, что нам известна прибыльность работ v;
Тогда очевидно, что мы можем

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

Разбор задач

Содержание

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

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

РешениеПеребираем начальную позицию, с которой начинается искомая последовательность;Перебираем длину начального числа;Прибавляем

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

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

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

РешениеЗадача решается с помощью динамического программирования;Пусть A – исходный массив, D

ЗАДАЧА 3. ABRACADABRAРегиональная олимпиада РФ за 2012 год

Постановка задачиДан набор строк s1, s2, s3, …, sm;Для каждой из

РешениеПреобразуем каждую строку t, состоящую из n символов к виду:t0 tn-1

Решение (1)Для каждой из строк s проделаем аналогичное преобразование;Двоичным поиском найдем

ПримерПусть задан набор строк из примера задачи;Тогда строки будут преобразованы следующим

Пример (1)Отсортируем словарь в лексикографическом порядке:aaaaaabbaaccaabbaaaabrrbaacdaadcaabrrbaaaabrrbaaДля образца a (aa) left =

ЗАДАЧА 4. ЗЕМЛЕТРЯСЕНИЕUSACO Open 2001

Постановка задачиЗадан неориентированный граф из N вершин и M ребер;Каждое из

РешениеДопустим, что нам известна прибыльность работ v;Тогда очевидно, что мы можем

Похожие презентации