ВКОШП-2011. Разбор задач презентация
Содержание
- 4. Постановка задачи Дано n чисел и число d Надо найти какой-нибудь
- 5. Как решать? Взять все числа, которые делятся на d Теперь взять
- 6. Обоснование Пусть есть какой-то другой набор, который удовлетворяет нас Все элементы
- 9. Постановка задачи Дан многоугольник P Точка называется защищённой, если любой луч
- 10. Как решать? Если из какой-то точки луч уходит на бесконечность, продлим
- 11. Как решать? Утверждение: если сделать такую операцию для каждой точки, для
- 12. Как решать? (продолжение) Проведем лучи для всех пар вершин Для всех
- 13. Как решать? (продолжение) Утверждается, что освещённый отрезок на стороне ограничен самой
- 14. Как решать? (продолжение) Осталось восстановить ответ Утверждение: вершины нашего нового многоугольника
- 17. Постановка задачи Дан телефонный номер – последовательность чисел, разделенных дефисами Необходимо
- 18. Как решать? Найдем последовательность слов, которые используются при произношении данного номера
- 19. Как решать? (продолжение) Нужно перебрать всевозможные расстановки дефисов между словами и
- 20. Обоснование Количество слов в тестах меньше 100 (так как цифр не
- 23. Постановка задачи Дано число n Надо его разложить на сумму двоек
- 24. Как решать? Понятно, что нам не имеет смысла иметь в сумме
- 27. Постановка задачи Есть последовательность из n чисел Надо разбить их на
- 28. Как решать? Будем считать динамику less[i] и greater[i] Разбиение чисел хорошее
- 29. Как решать? (продолжение) В какой последовательности находится i-ый элемент: В убывающей,
- 30. Как решать? (продолжение) В возрастающей, greater[i] равен максимуму из последних элементов
- 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])
- 32. Как решать? (продолжение) Если мы не смогли посчитать less[n] или greater[n],
- 35. Постановка задачи Дано n стоимостей товаров и известно, что k-ый бесплатно
- 36. Как решать? Отсортируем все цены в порядке убывания Разобьём их на
- 39. Постановка задачи Дано 5 чисел Максимальная скорость автомобиля - v Длина
- 40. Как решать? Заметим, что ситуация с разгоном и ситуация с торможением
- 41. Как решать? (продолжение) Понятно, что нам надо сразу разгоняться с ускорением
- 44. Постановка задачи Дан чайник объёма V и мощностью N, температура воды
- 45. Как решать? Отсортируем членов жюри по временам прихода И просто нужно
- 46. Подводные камни Нужно не забывать, что минимальная температура воды в чайнике
- 49. Постановка задачи Дана перестановка чисел 1, 1, 2, 2, …, n,
- 50. Как решать? Заметим, что нам подходят только перестановки, что расстояние между
- 51. Как решать? (продолжение) Построим полный двудольный граф и на ребре из
- 54. Постановка задачи Найти k-ую в лексикографическом порядке последовательность, которую можно отсортировать
- 55. Как решать? Заметим, что количество таких перестановок из n элементов равно
- 56. Как решать? (продолжение) Если мы на первое место поставим число i,
- 57. Как решать? (продолжение) Теперь просто решаем стандартную задачу о восстановлении k-ого
- 60. Постановка задачи Дано подвешенное дерево из n вершин Дано m запросов,
- 61. Как решать? Обойдём dfs-ом вершины, и отметим для каждой времена
- 62. Как решать? (продолжение) Обрабатываем запрос: Пусть h[v] – высота вершины v
- 64. Скачать презентацию
Слайды и текст этой презентации