Правильные скобочные последовательности. Разбор задач
Разбираем задачи на правильные скобочные последовательности: от базовых идей и жадных решений до более продвинутых техник, включая разделяй и властвуй, работу с подотрезками, динамическое программирование и подробный разбор реализации на C++. В видео разбираются задачи о: - конкатенации пар строк в правильную скобочную последовательность; - поиске наибольшей правильной скобочной подпоследовательности; - замене символов для получения правильной скобочной последовательности; - нахождении наибольшей правильной скобочной подстроки; - подсчёте количества правильных скобочных последовательностей, содержащих заданную строку s как подстроку. Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/brackets Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 00:00:00 Введение. Обзор списка задач 00:01:20 Задача A. Конкатенация скобочных последовательностей 00:02:00 Наивный алгоритм решения за квадрат 00:03:20 Переход к эффективному алгоритму 00:12:10 Исходный код решения на C++ 00:14:25 Задача B. Правильная скобочная подпоследовательность 00:16:30 Жадный алгоритм решения задачи 00:20:40 Исходный код решения на C++ 00:21:55 Усложнённая версия задачи: запросы на подотрезках 00:24:22 Задача C. Почти правильная скобочная последовательность 00:25:30 Разбор примеров из условия 00:27:25 Алгоритм решения задачи 00:38:55 Исходный код решения на C++ 00:43:00 Вспоминаем геометрический смысл правильных скобочных последовательностей 00:46:55 Задача E. Наибольшая правильная скобочная подстрока 00:50:00 Алгоритм решения задачи 00:53:00 Решение через разделяй и властвуй 01:04:30 Исходный код решения на C++ 01:15:27 Читаем разбор задачи от авторов 01:19:40 Задача D. Фома Дор и скобки 01:22:00 Алгоритм решения задачи 01:29:20 Исходный код решения на C++ 01:35:35 Завершение занятия
Разбираем задачи на правильные скобочные последовательности: от базовых идей и жадных решений до более продвинутых техник, включая разделяй и властвуй, работу с подотрезками, динамическое программирование и подробный разбор реализации на C++. В видео разбираются задачи о: - конкатенации пар строк в правильную скобочную последовательность; - поиске наибольшей правильной скобочной подпоследовательности; - замене символов для получения правильной скобочной последовательности; - нахождении наибольшей правильной скобочной подстроки; - подсчёте количества правильных скобочных последовательностей, содержащих заданную строку s как подстроку. Материалы: https://github.com/dmkz/competitive-programming/tree/master/mirea/cources/middle/2026/brackets Наш Telegram-канал: https://t.me/mireacoding Тайм-коды: 00:00:00 Введение. Обзор списка задач 00:01:20 Задача A. Конкатенация скобочных последовательностей 00:02:00 Наивный алгоритм решения за квадрат 00:03:20 Переход к эффективному алгоритму 00:12:10 Исходный код решения на C++ 00:14:25 Задача B. Правильная скобочная подпоследовательность 00:16:30 Жадный алгоритм решения задачи 00:20:40 Исходный код решения на C++ 00:21:55 Усложнённая версия задачи: запросы на подотрезках 00:24:22 Задача C. Почти правильная скобочная последовательность 00:25:30 Разбор примеров из условия 00:27:25 Алгоритм решения задачи 00:38:55 Исходный код решения на C++ 00:43:00 Вспоминаем геометрический смысл правильных скобочных последовательностей 00:46:55 Задача E. Наибольшая правильная скобочная подстрока 00:50:00 Алгоритм решения задачи 00:53:00 Решение через разделяй и властвуй 01:04:30 Исходный код решения на C++ 01:15:27 Читаем разбор задачи от авторов 01:19:40 Задача D. Фома Дор и скобки 01:22:00 Алгоритм решения задачи 01:29:20 Исходный код решения на C++ 01:35:35 Завершение занятия