competitive_programming
1.0.0
Это мои решения C ++ некоторых конкурентных проблем программирования и различных упражнений. Подобные проблемы решаются с использованием различных алгоритмов и структур данных - иногда используя те, которые предоставляются стандартной библиотекой, иногда используя мои собственные.
Большинство решений находятся в C+11 из-за Ex-UVA Online-Smight Ligation. Некоторые из них после успешного представления были изменены для использования функций C ++ 14/7.
Проблемы Источник
| ИДЕНТИФИКАТОР | Заголовок | Категории |
|---|---|---|
| 001 08 | Максимальная сумма | Линейный поиск, максимальная сумма Subarray, алгоритм Кадана |
| 001 09 | Scud Busters | Выпуклый корпус |
| 001 12 | Суммирование дерева | Бинарное дерево |
| 001 20 | Стеки из лопаток | Стек, сортировка блинов |
| 001 22 | Деревья на уровне | Бинарное дерево, обход на уровне порядка, поиск по ширине |
| 001 40 | Пропускная способность | Перестановки, возврат |
| 001 47 | Доллары | Динамическое программирование, изменение монеты |
| 001 64 | Строковый компьютер | Динамическое программирование, редактирование расстояния |
| 002 00 | Редкий заказ | Топологическая сортировка, поиск по глубине |
| 002 16 | Встать в очередь | Динамическое программирование, гамильтонианский путь, битовые маски |
| 002 18 | Эрадикация моли | Выпуклый корпус |
| 002 22 | Бюджетное путешествие | |
| 002 40 | Кодировка переменной Radix Huffman | Huffman Tree, поиск по глубине |
| 002 59 | Распределение программного обеспечения | |
| 002 64 | Рассчитывать на Кантор | |
| 002 70 | Выстраиваясь в очередь | |
| 002 94 | Делители | |
| 003 34 | Определение одновременных событий | |
| 003 48 | Оптимальный массив Mult. последовательность | Динамическое программирование, умножение матричной цепи |
| 003 50 | Псевдо случайные числа | |
| 003 53 | Надоедливые палиндромы | Полиномиальная хош, обработка струн |
| 003 57 | Считайте пути | |
| 003 61 | Полицейские и грабители | |
| 003 72 | Whatfix natation | Двоичное дерево, преобразование преобразования |
| 003 74 | Большой мод | Бинарное экспонент, модульное экспонент |
| 004 29 | Преобразование слова | |
| 004 37 | Башня Вавилона | |
| 004 39 | Рыцарь движется | Поиск по ширине |
| 004 54 | Анаграммы | |
| 004 55 | Периодические строки | Строки, Алгоритм Кнут -Моррис -Пратт |
| 004 59 | График подключения | Disecoint-Set/Union-Find, компоненты подключенных к графику |
| 004 69 | Водно -болотные угодья Флориды | |
| 004 81 | Что идет вверх | Самое длительное увеличение последующего, двоичный поиск |
| 004 82 | Перестановки массивы | |
| 005 01 | Черный ящик | Avl Tree, бинарное итератор дерева |
| 005 07 | Джилл снова едет | Линейный поиск, максимальная сумма Subarray, алгоритм Кадана |
| 005 16 | Главная земля | |
| 005 26 | Струнный расстояние | Динамическое программирование, редактирование расстояния |
| 005 36 | Восстановление деревьев | Двоичное дерево, преобразование преобразования |
| 005 40 | Командная очередь | |
| 005 43 | ГОЛДБАХ ГПИОО | Главные числа |
| 005 48 | Дерево | |
| 005 51 | Гнездовая куча кронштейнов | |
| 005 58 | Червоводы | |
| 005 62 | Разделительные монеты | |
| 005 68 | Просто факты | Фактор, рецидивовые отношения |
| 005 74 | Суммируйте это | |
| 005 82 | Случайно проводные нейронные сети | Поиск по глубине, компонент с графом биковой связи |
| 005 83 | Главные факторы | |
| 006 12 | Сортировка ДНК | Сорт -сортировка, подсчет инверсий |
| 006 23 | 500! | Фактор, большое целое число |
| 006 30 | Анаграммы | |
| 006 39 | Не поднимайтесь | |
| 006 74 | Изменение монеты | |
| 006 79 | Сбрасывая шары | |
| 006 84 | Интегральный детерминант | Гауссовое устранение, евклидовый алгоритм |
| 006 86 | ГОЛДБАХ ГЛАБИЙСКА II | Главные числа |
| 007 01 | Дилемма археологов | Логарифм |
| 007 14 | Копирование книг | Линейное разделение, неявный бинарный поиск |
| 007 19 | Стеклянные бусинки | Лексикографически минимальное вращение, алгоритм Дювана |
| 007 27 | Уравнение | Расположение выражения, алгоритм шунтирования двора |
| 007 29 | Проблема расстояния в хэмингах | Возврат |
| 007 50 | Восемь шахматных проблем королев | Возврат |
| 007 87 | Максимальный продукт подключения | Максимальный продукт subarray, большое целое число |
| 007 93 | Сетевые соединения | |
| 007 96 | Критические ссылки | Глубина-первый поиск, графический мост |
| 008 20 | Пропускная способность интернета | |
| 008 33 | Вода водопад | |
| 008 68 | Числовой лабиринт | Возврат |
| 008 72 | Заказывающий | |
| 009 08 | Вновь подключение компьютерных сайтов | |
| 009 29 | Номер лабиринт | |
| 009 42 | Циклические числа | Рациональное число, десятичная доля, хэш -таблица |
| 009 90 | Дайвинг для золота | |
| 009 91 | Безопасные приветствия | Комбинаторика, рецидивовые отношения, каталонские числа |
| 011 21 | Последующая | Скользящее окно |
| 011 75 | Дамский выбор | Стабильная проблема сопоставления, алгоритм шторма-шапли |
| 012 10 | Сумма последовательных основных чисел | Главные числа |
| 012 52 | Двадцать вопросов | |
| 012 60 | Продажа | |
| 012 93 | Символический вывод | Расположение экспрессии, алгоритм шунтирующего двора, символическая оценка. |
| 013 72 | Бревно прыжок | |
| 016 50 | Номер строки | Комбинаторика, отношения рецидивов |
| 100 03 | Резка палки | |
| 100 04 | Биколоринг | |
| 100 18 | Обратный и добавить | Целые числа, 196-Альгоритм |
| 100 61 | Сколько нулей и цифр? | Факторные, основные числа, факторизация, логарифм |
| 100 79 | Пицца | Комбинаторика, центральные многоугольные числа |
| 101 07 | Что такое медиана | Приоритетная очередь, онлайн -алгоритмы |
| 101 71 | Встреча проф. Мигель | |
| 101 93 | Все, что тебе нужно - это любовь | Величайший общий делитель |
| 102 20 | Я люблю большие числа! | Фактор, большое целое число |
| 102 23 | Сколько узлов | Комбинаторика, рецидивовые отношения, каталонские числа |
| 102 29 | Модульный Фибоначчи | Числа Фибоначчи, модульное экспонент |
| 102 45 | Самая близкая проблема пары | 2D ближайшая пара очков |
| 102 68 | 498-бис | Правило Хорнера |
| 102 82 | Бабельфиш | Хэш -таблица |
| 102 98 | Силовые струны | |
| 103 05 | Заказание задач | |
| 103 11 | Голдбах и Эйлер | Главные числа |
| 103 19 | Манхэттен | |
| 103 27 | Перевернуть сортировку | AVL Tree |
| 103 41 | Решите это | Числовые, метод Ньютона |
| 103 64 | Квадрат | Отступить, бит маски |
| 103 82 | Поливная трава | Жадное, интервальное покрытие |
| 104 28 | Корни | Нахождение корней, метод попоклонения |
| 104 54 | Трексера | Расположение выражения, алгоритм шунтирования, каталонские номера |
| 104 96 | Сборщики | |
| 105 33 | Цифровые простые числа | |
| 105 67 | Помогая заполнить Бейтс | |
| 105 70 | Встреча с инопланетянами | Перестановка, подсчет свопов, подсчет циклов |
| 105 76 | Y2k Accounting Bug | |
| 105 86 | Полиномиальные останки | |
| 106 00 | Конкурс ACM и отключение отключения | |
| 106 04 | Химическая реакция | |
| 106 51 | Пасьянс | |
| 106 55 | Созерцание! Алгебра | Рецидивное отношение, модульное экспонент |
| 106 64 | Багаж | |
| 106 84 | Джекпот | |
| 106 99 | Считайте факторы | Главные числа, главное разложение |
| 107 23 | Киборгские гены | |
| 107 38 | Риман против Мертенса | Прайские числа, функция Möbius, функция Mertens |
| 108 01 | Поднять прыжок | |
| 108 10 | Ultra Quicksort | Сорт слияния/вставки, подсчет инверсий |
| 108 55 | Поворотные квадраты | Матричное вращение, матричная транспозиция |
| 108 70 | Рецидивы | |
| 109 20 | Спиральный кран | Аналитическое выражение |
| 109 31 | Паритет | |
| 109 34 | Сбрасывая воздушные шары | |
| 109 35 | Выбрасывая карты | Очередь, по отдельности |
| 109 38 | Блохский цирк | |
| 109 54 | Добавить все | Куча |
| 109 57 | Su Doku Checker | Отправление, бит маска |
| 109 94 | Простое дополнение | Аналитическое выражение |
| 110 57 | Точная сумма | |
| 110 60 | Напитки | |
| 110 77 | Найдите перестановки | Комбинаторика, рецидивовые отношения, числа Стерлинга |
| 111 37 | История кабины | |
| 111 51 | Самый длинный палиндром | Динамическое программирование, обработка строк |
| 111 71 | SMS | Динамическое программирование, обработка строк, Trie |
| 111 95 | Еще N проблема | Отправление, бит маска |
| 112 27 | Серебряная пуля | |
| 112 35 | Частые значения | |
| 112 36 | Продуктовый магазин | |
| 112 57 | Новый маркетинговый план | Полигон, вписанный радиус круга, очередь приоритетов |
| 112 58 | Строковый раздел | Динамическое программирование |
| 112 60 | Странная корневая сумма | Аналитическое выражение, импл. бинарный поиск, модульная арифметика |
| 112 71 | Решетка резисторов | Отношение рецидивов, асимптотическое расширение |
| 112 83 | Играя в богле | Возврат |
| 112 97 | Перепись | 2D разложение SQRT |
| 113 62 | Телефон Список | Три, префикс сопоставление |
| 114 13 | Заполните контейнеры | |
| 114 20 | Комод | Комбинаторика, отношения рецидивов |
| 114 56 | Trainsorting | |
| 114 61 | Квадратные номера | Неявный бинарный поиск |
| 114 62 | Возраст | Считайте сортировку |
| 114 63 | Коммандос | |
| 114 75 | Распространяться на палиндром | |
| 115 17 | Точное изменение | |
| 115 36 | Наименьшая поджала | Скользящее окно |
| 115 72 | Уникальные снежинки | Линейный поиск, хэш -таблица |
| 115 84 | Разделение по палиндроме | |
| 116 21 | Небольшие факторы | Логарифм |
| 116 34 | Генерировать случайные числа | |
| 116 36 | Привет, мир! | Аналитическое выражение, логарифм |
| 116 58 | Лучшие коалиции | |
| 116 86 | Поднимите палки | |
| 116 91 | Тест на аллергию | |
| 117 03 | SQRT, log, грех | Рецидивовое отношение |
| 117 14 | Слепая сортировка | Статистика заказа (2 -й самый большой) |
| 117 33 | Аэропорты | |
| 119 02 | Доминатор | |
| 119 91 | Легкая проблема от Руджии Лю? | Сортировка, бинарный поиск |
| 119 97 | K самые маленькие суммы | |
| 120 86 | Потенциометры | Дерево Фенвика |
| 121 05 | Больше лучше (1) | |
| 121 05 | Больше лучше (2) | |
| 121 92 | Виноградная лоза | Бинарный поиск |
| 122 38 | Муравьи Колония | |
| 123 47 | Дерево бинарного поиска | Дерево бинарного поиска, прохождение до/после порядка |
| 124 55 | Батончики | Полный поиск, возврат |
| 124 58 | О, мои деревья! | |
| 124 62 | Прямоугольник | Линейный поиск, стек, битовая маска |
| 124 94 | Отдельная подстрока | Лексик Минимальное вращение, алгоритм Дювана, хэш -таблица |
| 125 04 | Обновление словаря | Быстрый сортировка |
| 126 40 | Самая большая игра | Линейный поиск, максимальная сумма Subarray, алгоритм Кадана |
| 126 97 | Минимальная длина субара | Линейный поиск, максимальная сумма Subarray, алгоритм Кадана |
| 127 02 | Дилатация | Бинарная морфология, бинарное расширение изображений |
| 129 11 | Подмножество сумма | Подмножество сумма, полный поиск, встречая в среднем |
| 130 50 | Обнаружение путей | Комбинаторика, отношения рецидивов |
| 132 82 | Cake McCakeface (1) | Сортировка, линейный поиск |
| 132 82 | Cake McCakeface (2) | Бит маска, ведение |
Проблемы Источник
| ИДЕНТИФИКАТОР | Заголовок | Категории |
|---|---|---|
| C2 | Получите изображение | Fractal, Mandelbrot set, mpi, std::thread |
Разные проблемы из разных онлайн -источников.
| Заголовок | Категории |
|---|---|
| Массив до двоичного дерева поиска | Дерево бинарного поиска |
| Массив с единицей прил. разница в поиске | Линейный поиск |
| Бинарная точка перехода сортированного массива | Бинарный поиск |
| Бинарный диаметр дерева | Бинарное дерево, первая глубина |
| Бинарный вид верха дерева | Бинарное дерево, проход |
| Поиск битунического массива | Бинарный поиск |
| Общие элементы в трех массивах | Линейный поиск |
| Точка подключения в Y-образных связанных списках | Связанный список |
| Подсчитайте подстроки Anagram | Хэш -стол, скользящее окно |
| Считайте меньшие элементы справа | AVL Tree |
| Считайте квадраты в почтовых кодах | Аналитическое выражение |
| Считайте триплеты | Линейный поиск, пара Sum Search |
| Разделение в бинарном потоке | Модульная арифметика, разделимость |
| Равновесная точка | Линейный поиск |
| Генерировать скобки (1) | Комбинаторика, возврат |
| Имеет подмножество с суммой | Динамическое программирование |
| Это связанный список палиндром | Связанный список |
| Это поддерево (1) | Бинарное дерево, первая глубина |
| K-й элемент в матрице сортировки Row-Column | Куча |
| Наибольшее число с k -свопами | Возврат |
| Самый большой прямоугольник в гистограмме | Линейный поиск, стек |
| Самая большая квадрат логическая матрица | Динамическое программирование, самая большая квадратная поддудка |
| Последние две цифры Фибоначчи | Числа Фибоначчи, модульная арифметическая, бинарная экспонентация |
| Список слияния | Связанный список |
| Список слияния сортировки | Связанный по отдельности, сортировка слияния |
| Самая длинная подстрока с различным характером | Линейный поиск |
| Самая длинная подстрока палиндромной суммы | Линейный поиск |
| Большинство элемент | Алгоритм голосования большинства Бойера - Мур |
| Сделать массив строго увеличиваясь | Самое длительное увеличение последующего, двоичный поиск |
| Матричное вращение | Матричное вращение, матричная транспозиция |
| Максимальное расстояние между сортированными элементами | Линейный поиск |
| Максимальное числовое значение в строке | Линейный поиск, лексикографическое сравнение |
| Максимум каждого субрай (1) | Раздвижное окно, сбалансированное бинарное дерево |
| Максимум каждого субрай (1) | Раздвижное окно, дек |
| Максимальный продукт 3 элементов | Линейный поиск |
| Мин-стек | Куча |
| Минимальный элемент в отсортированном вращаемом массиве | Бинарный поиск |
| Минимальное количество прыжков (1) | Динамическое программирование |
| Минимальное количество прыжков (2) | Линейный поиск |
| Почти отсортировано | Сорта, вставка |
| Следующее большее элемент | Линейный поиск, стек |
| Узлы на расстоянии k в бинарном дереве | Бинарное дерево, первая глубина |
| Количество путей в сетке | Комбинаторика |
| Разделение ровно и нечетные узлы | Связанный список |
| Очередь как два стека | Очередь, стек |
| Удалить дубликаты узлов | Связанный список |
| Удалить средний узел | Связанный список |
| Восстановить алфавит из словаря | Топологическая сортировка, алгоритм Кана |
| Обратить в одиночку список | Связанный список |
| Обратные слова в строке | Линейный поиск |
| Поверните однозначный список | Связанный список |
| Повернутый массив поиск | Бинарный поиск, линейный поиск |
| Второй по величине | Статистика заказа, второй по величине элемент, двоичный счетчик |
| Установить строку и столбец, если | Линейный поиск |
| Наименьшее число в перестановке | Линейный поиск |
| Отсортирована последующая размер 3 | Линейный поиск |
| Отсортирована последующая размер 4 | Линейный поиск |
| Квадратный корень | Неявный бинарный поиск |
| Subarray с данной суммой | Линейный поиск |
| Трехсторонний раздел | Массив перегородка |
| Два элемента с данной суммой | Линейный поиск, хэш -таблица |
| Неупорядоченные равные массивы | Последовательность, хэш -таблица |
| XOR LINDED LIST | Список вдвойне связанный |
| Нулевая сумма Subarray | Линейный поиск, хэш -таблица |
