Автор: admin
-
Python для быстрой разработки в контестах
Почему Python в CP? Python — отличный язык для быстрой разработки. Код получается короче, читаемее и проще в отладке. Минус — скорость выполнения. Плюсы и минусы Плюс Минус Короткий и читаемый код Медленнее C++ (в 10-50 раз) Встроенные структуры данных Не подходит для задач с жёстким лимитом времени Быстрая прототипировка Нет generics и шаблонов Отладка…
-
C++ STL для CP: контейнеры и алгоритмы
Стандартная библиотека C++ (STL) STL — это набор готовых контейнеров и алгоритмов, которые экономят часы при написании решений на C++. Основные контейнеры vector — динамический массив pair — пара значений set — уникальные элементы, отсортированные map — ассоциативный массив queue — очередь (FIFO) priority_queue — приоритетная очередь (куча) stack — стек (LIFO) deque — двусторонняя…
-
Как готовиться к ACM ICPC
Что такое ACM ICPC? ACM ICPC — Международная олимпиада по программированию, самая престижная в мире. Команда из трёх участников решает задачи за 5 часов. План подготовки на 6 месяцев Месяц Темы 1 Сортировки, массивы, строки, бинарный поиск 2 Графы: BFS, DFS, MST, кратчайшие пути 3 Динамическое программирование, жадные алгоритмы 4 Деревья, хэш-таблицы, структуры данных 5…
-
Чек-лист перед контестом
Прочитать разборы задач, которые не решили Решить задачи, которые пропустили Записать новые идеи в заметки Техническая подготовка Ноутбук заряжен или рядом с зарядкой IDE/редактор настроен (VS Code, CLion, Codeforces IDE) Интернет-соединение стабильное Кодовые шаблоны (snippets) готовы Шаблон решения скопирован (includes, fast I/O) Шаблон быстрой ввода/вывода для C++ Подготовка к решению Прочитать все задачи за 5…
-
LeetCode #1: Two Sum
Классическая задача для начала пути в спортивном программировании. Условие Дан массив целых чисел nums и число target. Найдите два индекса, сумма элементов на которых равна target. Решение на C++ Решение на Python Сложность Время: O(n) — один проход по массиву Память: O(n) — хэш-таблица для хранения элементов Альтернатива: можно отсортировать массив и использовать два указателя…
-
Codeforces 2161C — Loyalty (1200)
Сложность: 1200 | Теги: greedy, math, simulation Условие Вы — покупатель в магазине, который хочет купить n предметов. Цена каждого предмета i равна a[i], причем 1 ≤ a[i] ≤ X, где X — это фактор лояльности. Если после покупки предмета с ценой p ваш уровень лояльности увеличивается, вы получаете p бонусных очков. Ваша задача —…
-
Бинарное дерево поиска (BST)
Что такое BST? Бинарное дерево поиска (Binary Search Tree) — это дерево, где для каждого узла выполняется правило: все элементы в левом поддереве меньше, а в правом — больше. Пример кода на C++ Сложность Сбалансированное дерево: O(log n) для поиска, вставки, удаления Дегенерированное (как связный список): O(n) std::set и std::map в C++ STL используют сбалансированные…
-
Связные списки на C++
Что такое связный список? Связный список — это линейная структура данных, где каждый элемент (узел) содержит данные и указатель на следующий узел. В отличие от массива, элементы не хранятся в непрерывной памяти. Пример кода на C++ Преимущества и недостатки Плюсы: динамический размер, быстрая вставка/удаление в начале Минусы: нет прямого доступа к элементу по индексу, лишняя…
-
Динамическое программирование: задача о рюкзаке
Что такое динамическое программирование? Динамическое программирование (DP) — метод решения задач, которые можно разбить на перекрывающиеся подзадачи. Решения подзадач кэшируются, чтобы не пересчитывать их повторно. Пример кода на C++ Сложность Время: O(n × W) Память: O(n × W) Когда использовать? DP идеально подходит для задач оптимизации, где нужно найти максимальное или минимальное значение при определённых…
-
BFS и DFS: обход графов
Что такое обход графов? Обход графа — это процесс посещения всех вершин графа. Существует два основных метода: BFS (поиск в ширину) и DFS (поиск в глубину). BFS (Breadth-First Search) — поиск в ширину BFS исследует все вершины на текущем уровне, прежде чем перейти к следующему. Использует очередь (queue). Пример кода BFS на C++ DFS (Depth-First…