Презентация, доклад ВКОШП-2011. Разбор задач
Вы можете изучить и скачать доклад-презентацию на
тему ВКОШП-2011. Разбор задач.
Презентация на заданную тему содержит 63 слайдов. Для просмотра воспользуйтесь
проигрывателем,
если материал оказался полезным для Вас - поделитесь им с друзьями с
помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
![Как решать?
Будем считать динамику less[i] и greater[i]
Разбиение чисел хорошее](/documents_3/67558311a7580367b7a94c3a42908c11/img27.jpg "Как решать?
Будем считать динамику less[i] и greater[i]
Разбиение чисел хорошее")
![Как решать? (продолжение)
В возрастающей, greater[i] равен максимуму из последних элементов](/documents_3/67558311a7580367b7a94c3a42908c11/img29.jpg "Как решать? (продолжение)
В возрастающей, greater[i] равен максимуму из последних элементов")
![Пересчёт
Less[i]
if a[i+1]<greater[i] then less[i+1]=a[i]
if a[i+1]<a[i] then less[i+1]=min(less[i+1], less[i])](/documents_3/67558311a7580367b7a94c3a42908c11/img30.jpg "Пересчёт
Less[i]
if a[i+1]<greater[i] then less[i+1]=a[i]
if a[i+1]<a[i] then less[i+1]=min(less[i+1], less[i])")
![Как решать? (продолжение)
Если мы не смогли посчитать less[n] или greater[n],](/documents_3/67558311a7580367b7a94c3a42908c11/img31.jpg "Как решать? (продолжение)
Если мы не смогли посчитать less[n] или greater[n],")
![Как решать? (продолжение)
Обрабатываем запрос:
Пусть h[v] – высота вершины v](/documents_3/67558311a7580367b7a94c3a42908c11/img61.jpg "Как решать? (продолжение)
Обрабатываем запрос:
Пусть h[v] – высота вершины v")
Слайды и текст этой презентации
Слайд 1
Описание слайда:
Слайд 2
Описание слайда:
Слайд 3
Описание слайда:
Слайд 4
Описание слайда:
Постановка задачи
Дано n чисел и число d
Надо найти какой-нибудь поднабор из чисел, такой что их наибольший общий делитель равен d
Слайд 5
Описание слайда:
Как решать?
Взять все числа, которые делятся на d
Теперь взять у них у всех наибольший общий делитель
Если он равен d, то выводим это множество, если нет, то вывести -1
Слайд 6
Описание слайда:
Обоснование
Пусть есть какой-то другой набор, который удовлетворяет нас
Все элементы из этого набора обязаны делиться на d, а, значит, этот набор является подмножеством нашего
Следовательно НОД этого набора может быть только больше, чем НОД нашего, а, значит, если наш набор не удовлетворяет, то и другой тоже
Слайд 7
Описание слайда:
Слайд 8
Описание слайда:
Слайд 9
Описание слайда:
Постановка задачи
Дан многоугольник P
Точка называется защищённой, если любой луч проведённый из него пересекается с многоугольником P
Надо найти многоугольник, состоящий из защищённых точек
Слайд 10
Описание слайда:
Как решать?
Если из какой-то точки луч уходит на бесконечность, продлим его в другую сторону до пересечения со стороной (будем считать такую точку на стороне освещённой)
Назовём такую операцию “освещением”
Слайд 11
Описание слайда:
Как решать?
Утверждение: если сделать такую операцию для каждой точки, для которой существует луч выходящий на бесконечность, то на каждой стороне может быть максимум 1 освещённый отрезок
Слайд 12
Описание слайда:
Как решать?
(продолжение)
Проведем лучи для всех пар вершин
Для всех таких лучей проведём нашу операцию “освещение”
На каждой стороне получили набор освещённых точек
Слайд 13
Описание слайда:
Как решать?
(продолжение)
Утверждается, что освещённый отрезок на стороне ограничен самой левой освещённой точкой на стороне и самой правой освещённой точкой стороне
Слайд 14
Описание слайда:
Как решать?
(продолжение)
Осталось восстановить ответ
Утверждение: вершины нашего нового многоугольника – концы невырожденных “освещённых” частей
Слайд 15
Описание слайда:
Слайд 16
Описание слайда:
Слайд 17
Описание слайда:
Постановка задачи
Дан телефонный номер – последовательность чисел, разделенных дефисами
Необходимо найти все телефонные номера, которые произносятся также как и данный
Слайд 18
Описание слайда:
Как решать?
Найдем последовательность слов, которые используются при произношении данного номера
Заметим, что слова «тысяча» и «миллион» (в разных формах) всегда употребляются вместе с предыдущим словом, поэтому форма этих слов не важна
Следовательно, каждое слово можно хранить как его числовое значение
Слайд 19
Описание слайда:
Как решать?
(продолжение)
Нужно перебрать всевозможные расстановки дефисов между словами и вывести все, которые являются корректными телефонными номерами
Для определения корректности записи нужно понимать можно ли «склеить» несколько слов в одно число
Слайд 20
Описание слайда:
Обоснование
Количество слов в тестах меньше 100 (так как цифр не больше 50)
Количество телефонных номеров в ответе не больше 100000
Следовательно, перебор будет работать быстро с отсечением – не перебирать дальше, если следующую группу слов нельзя «склеить» в одно число
Слайд 21
Описание слайда:
Слайд 22
Описание слайда:
Слайд 23
Описание слайда:
Постановка задачи
Дано число n
Надо его разложить на сумму двоек и троек с минимальным числом слагаемых
Слайд 24
Описание слайда:
Как решать?
Понятно, что нам не имеет смысла иметь в сумме больше двух двоек, так как 3 двойки = 2 тройки
Если n ≡ 0 (mod 3), то ответ (n/3, 0)
Если n ≡ 1 (mod 3), то ответ ((n-4)/3, 2)
Если n ≡ 2 (mod 3), то ответ ((n-2)/3, 1)
Слайд 25
Описание слайда:
Слайд 26
Описание слайда:
Слайд 27
Описание слайда:
Постановка задачи
Есть последовательность из n чисел
Надо разбить их на убывающую и возрастающую подпоследовательности
Слайд 28
Описание слайда:
Как решать?
Будем считать динамику less[i] и greater[i]
Разбиение чисел хорошее – разбиение чисел на возрастающую и убывающую подпоследовательности
Слайд 29
Описание слайда:
Как решать?
(продолжение)
В какой последовательности находится i-ый элемент:
В убывающей, less[i] равен минимальному из последних элементов всех возрастающих последовательностей во всех хороших разбиениях чисел с индексами от 1 до i-1
Слайд 30
Описание слайда:
Как решать?
(продолжение)
В возрастающей, greater[i] равен максимуму из последних элементов всех убывающих последовательностей во всех хороших разбиениях чисел с индексами от 1 до i-1
Слайд 31
Описание слайда:
Пересчёт
Less[i]
if a[i+1]<greater[i] then less[i+1]=a[i]
if a[i+1]<a[i] then less[i+1]=min(less[i+1], less[i])
Greater[i]
if a[i+1]>less[i] then greater[i+1]=a[i]
if a[i+1]>a[i] then greater[i+1]=
min(greater[i+1], greater[i])
Слайд 32
Описание слайда:
Как решать?
(продолжение)
Если мы не смогли посчитать less[n] или greater[n], то ответ – Impossible
А иначе, нужно просто восстановить ответ по этой динамике
Слайд 33
Описание слайда:
Слайд 34
Описание слайда:
Слайд 35
Описание слайда:
Постановка задачи
Дано n стоимостей товаров и известно, что k-ый бесплатно
Найти минимальное число денег, которое нужно потратить, чтобы купить все товары
Слайд 36
Описание слайда:
Как решать?
Отсортируем все цены в порядке убывания
Разобьём их на группы по k, начиная с первого, и из каждой группы, может быть кроме последней, можно не платить за минимальный элемент (то есть не платить за элемент, номер которого делится на k)
Корректность такого алгоритма понять несложно
Слайд 37
Описание слайда:
Слайд 38
Описание слайда:
Слайд 39
Описание слайда:
Постановка задачи
Дано 5 чисел
Максимальная скорость автомобиля - v
Длина первого отрезка трассы - x
Длина второго отрезка трассы - y
Максимальное ускорение при разгоне - a
Максимальное ускорение при торможении - b
Найти минимальное время за которое можно преодолеть трассу при условии, что скорость между двумя отрезками равна 0
Слайд 40
Описание слайда:
Как решать?
Заметим, что ситуация с разгоном и ситуация с торможением совершенно одинаковы, то есть при торможении мы считаем, что едем в другую сторону и ускоряемся
Задача свелась к:
Максимальная скорость машины – v
Максимальное ускорение машины – a
Длина отрезка - x
Слайд 41
Описание слайда:
Как решать?
(продолжение)
Понятно, что нам надо сразу разгоняться с ускорением a до скорости v, а далее ехать с постоянной скоростью
2 случая:
Успеваем разогнаться: , тогда ответ –
Не успеваем разогнаться: , тогда ответ –
Слайд 42
Описание слайда:
Слайд 43
Описание слайда:
Слайд 44
Описание слайда:
Постановка задачи
Дан чайник объёма V и мощностью N, температура воды в чайнике опускается не ниже 20 градусов и поднимается не выше 100, вода в чайнике остывает со скоростью k градусов в секунду
Дано m запросов, состоящих из двух чисел – время прихода члена жюри ti и объём его кружки ai , надо на каждый запрос вернуть время в секундах, когда член жюри начнёт пить чай
Слайд 45
Описание слайда:
Как решать?
Отсортируем членов жюри по временам прихода
И просто нужно запросы жюри обрабатывать в таком порядке прямо как написано в условии
Слайд 46
Описание слайда:
Подводные камни
Нужно не забывать, что минимальная температура воды в чайнике – 20 градусов
Изначально чайник был пуст
Слайд 47
Описание слайда:
Слайд 48
Описание слайда:
Слайд 49
Описание слайда:
Постановка задачи
Дана перестановка чисел 1, 1, 2, 2, …, n, n
Требуется найти такую перестановку, что минимальное расстояние между двумя одинаковыми элементами было максимально и сумма расстояний между старыми и новыми позициями минимальна
Слайд 50
Описание слайда:
Как решать?
Заметим, что нам подходят только перестановки, что расстояние между двумя одинаковыми ровно n, то есть теперь положение i в первой половине однозначно задаёт положение i во второй половине
Слайд 51
Описание слайда:
Как решать?
(продолжение)
Построим полный двудольный граф и на ребре из i в j напишем расстояние между положениями i в изначальной перестановке и когда они будут стоять на позициях j и j+n
Осталось просто на этом графе найти минимальное взвешенное полное парасочетание
Слайд 52
Описание слайда:
Слайд 53
Описание слайда:
Слайд 54
Описание слайда:
Постановка задачи
Найти k-ую в лексикографическом порядке последовательность, которую можно отсортировать стеком
Слайд 55
Описание слайда:
Как решать?
Заметим, что количество таких перестановок из n элементов равно числу Каталана, так как каждой такой перестановке можно взаимнооднозначно сопоставить правильную скобочную последовательность длины 2n
Слайд 56
Описание слайда:
Как решать?
(продолжение)
Если мы на первое место поставим число i, то последовательность выглядит следующим образом:
i(ХП[1..i-1])(ХП[i+1..n]), где ХП[a..b] –последовательность из чисел от a до b, которая сортируется стеком
Таким образом количество ХП[1..n], где на первом месте стоит i равно Ci-1*Cn-i+1, где Ci – i-ое число Каталана
Слайд 57
Описание слайда:
Как решать?
(продолжение)
Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного объекта, то есть ставим поочерёдно на первое место числа от 1 до n и проверяем, а потом запускаемся рекурсивно от частей
[1..i-1] и [1..n-i+1]
Слайд 58
Описание слайда:
Слайд 59
Описание слайда:
Слайд 60
Описание слайда:
Постановка задачи
Дано подвешенное дерево из n вершин
Дано m запросов, состоящих из 2 чисел – v и k
Для каждого запроса надо вывести количество потомков вершины v на расстоянии k
Слайд 61
Описание слайда:
Как решать?
Обойдём dfs-ом вершины, и отметим для каждой времена входа in[v] и выхода out[v], а также для каждой высоты будем хранить набор вершин, которые находятся на этой высоте
Слайд 62
Описание слайда:
Как решать?
(продолжение)
Обрабатываем запрос:
Пусть h[v] – высота вершины v
Рассмотрим набор вершин, находящихся на высоте h[v]+k
Среди них нужно найти количество таких, у которых времена входа от in[v] до out[v]
Бинарный поиск
Слайд 63
Описание слайда:
Скачать презентацию на тему ВКОШП-2011. Разбор задач можно ниже:
