Этот блог посвящён олимпиадному программированию.Если вы хотите узнать, что это такое и с чем его едят - милости просим.Если вы хотите чему-то научиться, что-то дополнить - добро пожаловать!
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
В данном блоге я буду стараться рассказать про особенности спортивного программирования.Также расскажу о различных типах задач и, конечно, алгоритмах.
Типы олимпиадных задач
| Здравствуйте!Сейчас я хотел бы рассказать о типах олимпиадных задач. Вообще, существует очень много типов олимпиадных задач, и конечно существует много алгоритмов их решения.Сейчас я расскажу, какие основные типы задач имеются: 1.Задачи на алгебру. 2.Задачи на графы. 3.Строковые задачи. 4.Задачи на ДП(динамическое программирование) 5.Симуляция 6.Задачи на геометрию 7.Игры. 8.Комбинаторика. 9.Задачи на сложные структуры данных. Не переживайте, если встретили много незнакомых слов.Со временем, мы всё это разберем. Теперь попытаемся дать краткую характеристику каждого типа задач: 1.Задачи на алгебру. Сюда входят задачи на поиск простых чисел, быстрое возведение чисел, длинная арифметика, проверка числа на простоту.Вариантов задач довольно много. 2. Задачи на графы. Задачи такого типа очень любят давать на олимпиадах.При решении таких задач используется математическая модель граф, с которой мы чуть позже разберемся.Алгоритмов на графы очень много, также как и задач. 3.Строковые задачи.Такие задачи подразумевают собой нейкую обработку текста или строки.Напрмер, найти все вхождения подстроки в строке, сжатие строки, вычисления значения выражения и т.д.Алгоритмов чуть меньше, но есть очень сложные для понимания(суффиксный автомат, например). 4.Задачи на ДП Динамическое программирование - это разбиение задач на более мелкие задачи, решение которых пирводит к нахождению ответа на главную задачу.Задачи такого плана тоже довольно часто попадаются на олимпиадах. напрмер, нахождение последовательности чисел Фибоначчи - типичное ДП.Также знаменитая задача "Рюкзак" - тоже ДП. 5.Симуляция - это решение, при котором мы как бы симулируем работу чего-то в своей программе.как будто это делаем мы, но только загоняем в программу.Такие задачи тоже попадаются. 6.Задачи на геометрию Мои нелюбимые задачи.Это задачи плана даны координаты прямоугольников, найти число пересечений и т.д. Алгоритомв хватает на них, но задачи такого плана - довольно редкие гости на олимпиадах.Но бывает, что и попадаются. 7.Игры. Это задачи по теории игр.Такие довольно редко попадаются. 8.Комбинаторика. Это больше идёт по теории чисел.Тут надо математику ещё знать.Это задачи плана - сколькими способами можно переставить цифры в числе 123, чтобы получились разные числа?Тут надо формулы знать=) 9.Задачи на сложные структуры данных. Это задачи, в которых используются сложные структуры данных(дерево отрезков, дерево Фенвика, корневая декомпозиция и т.д.).Область применения этих структур обширна, поэтому и задач на них много. Но не забыайте, одна задача может совмещать в себе сразу несколько типов.удачи! |
Всего комментариев 0
Комментарии
