EVELINПлатформа соревнований и практики

Главная Новости События Задачи Контесты Курсы

EVELINФСП Карелии · Спортивное программирование

О платформе Правила Политика конфиденциальности info@fsp-karelia.ru

EVELIN

C++ базовый/Олимпиадная задача: Доказательство корректностиПоложение

Содержание

Модуль 1. От задачи к работающей программе

●Программа и компьютер: Алгоритм, программа и исполнитель ●Как выполняется программа: Процессор, память, регистры и машинные команды ●Компиляция изнутри: Препроцессор, компилятор, ассемблер, объектный файл и линкер ◇Среда разработки: Создание, сборка и запуск проекта ●Первая программа: main, инструкции, комментарии и пространство имён ●Стандартный вывод: cout и точный формат результата ●Переменные: Объявление, присваивание и изменение значения ●Целые числа: int, long long и диапазоны типов ●Стандартный ввод: cin, токены и связь входа с переменными ●Выражения: Арифметические операции и порядок вычислений ●Целая арифметика: Деление, остаток и работа с цифрами ●Вещественные числа: double, округление и погрешность ●Логический тип: bool, сравнения и составные предикаты ●Символьный тип: char, литералы и коды символов ◇Диагностика программы: ошибки компиляции, выполнения и ответа ◇Расчётные программы: лабораторная работа по формулам и преобразованиям

Модуль 2. Управление выполнением и организация кода

●Логика управления: Предикат как условие выполнения ◇Условия: if, else и выбор одного из двух действий ◇Условия: Цепочки else if и несколько вариантов ответа ◇Условия: Составные и вложенные условия ◇Условия: Полный разбор случаев и граничные значения ◇Цикл for: Повторение действия известное число раз ◇Цикл for: Счётчики и суммы ◇Цикл for: Минимум, максимум и рекорды ◇Цикл while: Условие продолжения и прогресс ◇Цифры числа: Извлечение, удаление и накопление ◇Поток неизвестной длины: Маркер и вложенная обработка ◇Вложенные циклы: Решётки, таблицы и пары ◇Функции: Вызов, return и объявление ◇Функции: Параметры по значению и локальная область ◇Функции: Передача по ссылке и несколько результатов ◇Организация решения: Декомпозиция, отладка и лабораторная работа

Модуль 3. Последовательности, таблицы и текст

◇Массивы: Индексы, размер и размещение элементов ◇Векторы: Создание, изменение размера и добавление элементов ◇Последовательности: Обход и вычисление характеристик ◇Последовательности: Изменение, фильтрация и построение нового массива ◇Частотные массивы: Подсчёт значений и восстановление данных ◇Двумерные массивы: Строки, столбцы и обход таблицы ◇Клетчатые поля: Координаты, соседи и границы ◇Символы в последовательности: Классификация и преобразование регистра ◇Строки: Хранение, чтение и основные операции ◇Строки: Частоты символов и проверка состава ◇Строки: Палиндромы и анаграммы ◇Строки: Подстроки, поиск и лексикографический порядок ◇Строки: getline и разбор составной строки ◇Записи: struct и хранение объектов с несколькими полями ◇Табличные и текстовые данные: Лабораторная работа

Модуль 4. Эффективность и стандартные инструменты C++

●Сложность: Ограничения задачи и допустимое число операций ●Сложность: O(1), O(log n), O(n), O(n log n) и O(n²)●Сложность: Память программы и оценка структур данных ●Сортировка: sort и упорядочивание чисел ●Сортировка: pair, tuple и несколько ключей ●Сортировка: Компараторы, устойчивость и типичные ошибки ●Поиск: Линейный поиск и первое вхождение ●Бинарный поиск: Поиск элемента в отсортированном массиве ●Бинарный поиск: Первая и последняя подходящая позиция ●Бинарный поиск: lower_bound, upper_bound и equal_range ●Бинарный поиск: Поиск минимального допустимого ответа ●Множества: set и уникальные упорядоченные элементы ●Мультимножества: multiset и работа с повторениями ●Словари: map и unordered_map ●Стек: LIFO, операции и std::stack ●Стек: История состояний и проверка скобок ●Очередь: FIFO, операции и std::queue ●Очередь: Частичное обслуживание и суммарная сложность ●Deque: Два конца и std::deque ◇Линейные структуры: Выбор между stack, queue и deque ●Кольцевой буфер: Очередь без сдвига элементов ●Кольцевой буфер: Deque и операции с двух концов ●Очередь с приоритетом: priority_queue и составной ключ ◇STL и сложность: Лабораторная работа «Диспетчер заявок»

Модуль 5. Математика и полный перебор

●Делимость: Делители, кратные и свойства остатка ●Алгоритм Евклида: НОД, НОК и связанные задачи ●Простые числа: Проверка числа и оценка перебора ●Решето Эратосфена: Все простые числа на отрезке ●Факторизация: Простые множители и количество делителей ●Модульная арифметика: Сложение, умножение и нормализация остатка ●Быстрое возведение в степень: Двоичное разложение показателя ●Комбинаторика: Правила суммы и произведения ●Рекурсия: База, переход и стек вызовов ●Полный перебор: Вложенные циклы и систематический порядок ●Генерация: Последовательности и строки с ограничениями ●Генерация: Перестановки и сочетания ●Битовые маски: Подмножества, операции и подмаски ●Перебор с отсечениями: Доказанные границы ◇Математика и перебор: Лабораторная работа и контест

Модуль 6. Алгоритмы обработки последовательностей и диапазонов

●Префиксные суммы: Построение и смысл префикса ●Префиксные суммы: Сумма на произвольном отрезке ●Двумерные префиксы: Сумма в прямоугольнике ●Разностный массив: Массовые прибавления на отрезках ●Префиксные частоты: Запросы о количестве значений ●Сжатие координат: Сохранение порядка без больших индексов ●Два указателя: Поиск пары в отсортированной последовательности ●Два указателя: Границы подходящего подотрезка ●Скользящее окно: Подотрезки фиксированной длины ●Скользящее окно: Подотрезки с ограничением ●Жадный алгоритм: Локальный выбор и условия применимости ●Жадный алгоритм: Выбор непересекающихся интервалов ●Жадный алгоритм: Обменный аргумент и контрпримеры ◇Последовательности и диапазоны: Комбинированная лабораторная работа ◇Последовательности и диапазоны: Тематический контест

Модуль 7. Основы алгоритмов на графах

●Графы: Вершины, рёбра, степени, пути и циклы ●Графы: Матрица и список смежности ●DFS: Рекурсивный обход графа ●DFS: Компоненты связности ●DFS: Поиск цикла в неориентированном графе ●BFS: Послойный обход и расстояния ●BFS: Восстановление кратчайшего пути ●BFS: Несколько источников ●Графы на клетчатом поле: Лабиринты и распространение волны ●Двудольные графы: Раскраска и поиск нечётного цикла ●Ориентированные графы: Циклы и состояния вершин ●Топологическая сортировка: Порядок зависимостей ●Деревья: Корень, родитель, глубина и листья ●Деревья: Обход, размеры поддеревьев и высоты ◇Графы: Лабораторная работа ◇Основы графов: Тематический контест

Модуль 8. Основы динамического программирования

●Динамическое программирование: Состояние, переход и база ●Одномерная динамика: Число способов ●Одномерная динамика: Минимальная стоимость ●Одномерная динамика: Ограничения на последние действия ●Динамика по таблице: Количество путей ●Динамика по таблице: Препятствия и оптимальный путь ●Восстановление ответа: Предки состояний ●Рюкзак 0/1: Достижимый вес и максимальная стоимость ●Неограниченный рюкзак: Повторное использование предметов ●Subset sum: Восстановление выбранного набора ●Наибольшая возрастающая подпоследовательность: Решение за O(n²)●Динамика на DAG: Порядок вычисления по графу ●Оптимизация памяти: Хранение только необходимых слоёв ◇Динамическое программирование: Лабораторная работа ◇Основы динамического программирования: Тематический контест

Модуль 9. Олимпиадная практика муниципального уровня

●Олимпиадная задача: Формализация условия и модели данных ●Олимпиадная задача: Выбор алгоритма по ограничениям ●Олимпиадная задача: Доказательство корректности ●Тестирование: Граничные случаи и систематический набор тестов ●Контрпримеры: Проверка гипотезы и опровержение неверной идеи ●Реализация: План решения, инварианты кода и отладка ◇Практикум: Массивы, строки и сортировка ◇Практикум: Математика, перебор и жадные методы ◇Практикум: Графы и динамическое программирование ◇Пробный муниципальный тур: Вариант 1 ◇Пробный муниципальный тур: Вариант 2 ◇Итоговый разбор: Карта навыков и индивидуальные пробелы

Открываем урок