Это сообщение в блоге началось с личного поиска такого сообщения. У меня через час собеседование по кодированию, и я искал хороший средний пост, который мог бы указать мне на некоторые основные концепции конкурентного кодирования, чтобы я мог вовремя освежиться.
Неспособность найти такой пост побудила меня написать его самому. Этот блог предназначен в основном для моего личного использования в будущем, и, возможно, название будет скорее причудливым, чем обобщающим. В любом случае, суть в том, что это сообщение, на которое стоит взглянуть непосредственно перед тем, как вы проведете соревнование по кодированию. Я постараюсь перечислить наиболее часто используемые стратегии для решения вопросов второго раунда Codeforces или аналогичного уровня, основываясь на моем опыте. Итак, вкратце, давайте поработаем руки каким-нибудь алгоритмом.
Итак, список,

  • Кратчайший путь Дейкстры: не так часто встречается в вопросе, но всегда полезно изучить обход графа и способы использования очереди с приоритетами. И Боже, Priority Queue - такой ангел, который появляется почти везде. Ссылка на реализацию.
  • GCD и Inverse Modular: опять же небольшой код, но множество вариантов использования. Ссылка даст вам краткий обзор. Если вы занимались СР (соревновательным программированием), вы снова увидите этого печально известного парня, появляющегося повсюду.
  • Динамическое программирование. Это похоже на стандартное программирование, о котором все время от времени любят спрашивать. Идея динамического программирования проста. Зачем что-то рассчитывать дважды? Если вы видите, что в постановке задачи можно избежать нескольких повторяющихся вычислений, высока вероятность, что DP даст вам желаемую сложность. Фибоначчи и Самый длинный палиндром помогут вам почувствовать вкус.
  • Жадный: я всегда думаю, что это интуитивный подход. В большинстве случаев при его использовании вы будете упускать несколько небольших угловых случаев и не получите правильный ответ. Тем не менее, всегда, по крайней мере, в течение первых 5 минут, думайте о возможном жадном подходе и тестируйте на истории некоторые тестовые примеры. Если вы хорошо разбираетесь в кодировании и внедрении, я предлагаю кодировать и загружать. Скрещенные пальцы.
  • Двоичный поиск: чаще всего вас просят найти минимальное или максимальное число, удовлетворяющее определенному свойству. Скорее всего, это свойство имеет свойство последовательности. f (x) = ›f (x + 1), но f (x + 1) не влечет f (x). Лучше всего использовать двоичный поиск. Простая реализация: -

- - - - 1. Преобразуйте все входные данные в глобальную переменную.

- - - - 2. Создайте функцию проверки для свойства f.

- - - - 3. Функция Бинарный поиск для поиска ответа

  • Сортировка, сито Эратосфена…. : Просто несколько случайных совпадений, которые появляются много раз. Я попрошу читателей прокомментировать здесь некоторые из наблюдаемых ими личных фаворитов.
  • Стек: Как уже могло быть ясно, я не специалист в этой области, я скорее хакер. И я просто знаю, что этот стек может иногда отвечать на вопросы. Я не знаю, когда и много раз я получаю неправильный ответ.
  • LONG LONG INT: Это кажется глупым, но в некоторых случаях я просто умножаю два целых числа, которые выходят за пределы допустимого диапазона и получают неправильные ответы. Итак, ребята, если нет предела памяти, ВСЕГДА используйте Long Long int.
  • C ++ 14: Это просто. Никакой перепроданности, но этот парень гото. Если ваш вопрос не связан со строками, ответом будет python. Я знаю, что это будет медленно, но это удобное место для начала, и кто знает, установщик вопросов легко справился с тестовыми примерами.
  • BFS и DFS: один из самых простых способов обхода дерева, и если вы много раз сохраняете правильные переменные, вы получите ответ быстрее, чем вы думаете.
  • Снова часть для дальнейших комментариев и дополнений.

Некоторые дополнительные темы, которые могут быть полезны, но не всегда, но кто знает,

  • Мин. Резка, макс. Расход
  • Гранди номер
  • Сегментное дерево
  • Union Find: Специально для количества подключенных компонентов.

Да прибудет с тобой сила.

P.S . Пожалуйста, просмотрите комментарии, чтобы увидеть ссылки на другие хорошие сообщения о соревновательном программировании 101.