Вопросы по алгоритмам

Техника программирования

  1. Структура типичной программы по программированию на С++
  2. Потоки вода и вывод в С++
  3. Ускорение ввода-вывода
  4. endl vs. '\n'
  5. Ввод-вывод функциями С
  6. Считывание строки с пробелами
  7. Считывание данных неизвестного объема
  8. Работа с файлами на олимпиаде
  9. Тип int
  10. Тип long long int
  11. Какая проблема здесь может быть: int a = … ; long long b = a*a; ? Решение проблемы.
  12. Тип __int128_t
  13. Основные свойства остатков. Вычисление n! по модулю
  14. Нахождение остатка при делении отрицательных чисел
  15. Числа с плавающей точкой. Вывод числа с некоторой точностью (С и С++)
  16. Сравнение чисел с плавающей точкой
  17. typedef (long long, vector , pair )
  18. #define
  19. Макрос с параметрами
  20. Порождение всех подмножеств множества из n элементов с помощью рекурсии
  21. Порождение перестановок с помощью рекурсии
  22. Функция next_permutation()
  23. Перебор с возратом
  24. Задача о n ферзях на доске n´n
  25. Преобразование двоичного представления числа в десятичное
  26. Получение противоположного числа с помощью дополнительного кода
  27. Безнаковые целое
  28. Связь между представлениями знаковым и безнаковым чисел
  29. Переполнение
  30. Операция И
  31. Проверка числа на четность
  32. Проверка числа на делимость на степень двойки
  33. Операция ИЛИ
  34. Операция ИСКЛЮЧАЮЩЕЕ ИЛИ
  35. Операция НЕ
  36. Связь числа противоположному данному и инвессией.
  37. Поразрядый сдвиг
  38. Умножение и деление на 2 с помощью поразрядных сдвигов
  39. Получение степеней двойки
  40. Битовая маска
  41. Напечатать двоичное представление некоторого целого числа
  42. Установить k-ый бит числа x в единицу
  43. Сбросить k-ый бит числа в нуль
  44. Инвертировать k-ый бит числа
  45. Сбросить последний единичный бит в нуль
  46. Сбросить в нуль все единичные биты, кроме последнего
  47. Инвертировать все биты после последнего единичного
  48. Проверка числа на степень двойки
  49. Создание битовой маски типа long long
  50. __builtin_clz() и __builtin_clzll()
  51. __builtin_ctz() и __builtin_ctzll()
  52. __builtin_popcount() и __builtin_popcountll()
  53. __builtin_parity() и __builtin_parityll()
  54. Запись подмножеств множества с помощью двоичного представления числа
  55. Реализация теоретико-множественных операций с помощью порозрядных
  56. Перебор подмножеств, содержащих ровно k элементов
  57. Пербор всех подмножеств множества
  58. Битовые множества С++

Эффективность

  1. Временная сложность алгоритма
  2. O нотация
  3. O(1)
  4. O(n)
  5. O(n 2 )
  6. O(n k )
  7. Общая временная сложность
  8. O(nm)
  9. Временная сложность рекурсивной
  10. 1+2+4+8+...+2n-1
  11. Часто встречающиеся оценки временной сложности
  12. Полиномиальный алгоритм
  13. NP-трудные задачи
  14. Оценка временной сложности по размеру входных данных
  15. Формальное определение времени работы алгоритма
  16. Нижняя граница времени работы алгоритма
  17. Точная граница времени работы алгоритма
  18. Максимальная сумма подмассивов. Решения за O(n3), O(n2). Алгоритм Кадане O(n)
  19. Задача о двух ферзях. Решения за O(n4), O(n2), O(n), O(1)
  20. Оптимизация кода
  21. Оптимизации компилятора
  22. Особенности процессора
  23. Кеши
  24. Распараллеливание

Сортировка и поиск

  1. Основная задача сортировки
  2. Пузырьковая сортировка. Временная сложность
  3. Инверсии
  4. Максимальное число инверсий
  5. Сортировка слиянием. Временная сложность
  6. Нижняя граница временной сложности сортировки
  7. Сортировка подсчетом
  8. sort() в С++
  9. Сортировка по убыванию в С++
  10. Сортировка массива
  11. Сортировка строки
  12. Сортировка строк
  13. Сортировка пар
  14. Сортировка кортежей
  15. Сортировка пользовательского класса. Функция operator<
  16. Функция сравнения(компаратор)
  17. Проверка всех элементов на уникальность
  18. Подсчет числа различных элементов
  19. Нахождение самого часто встречающегося элемента
  20. Нахождение двух элементов с минимальной разностью
  21. Алгоритмы заметающей прямой. Задача про рестаран
  22. Задача о составлении расписания
  23. Работы и сроки исполнения
  24. Двоичный поиск
  25. Методы реализации двоичного поиска
  26. Двоичный поиск по ответу
  27. Задача о k заданиях на n машинах

Структуры данных в C++

  1. Динамический массив
  2. Вектор
  3. Добавление элементов в вектор
  4. Доступ к элементам вектора
  5. Создание вектора с перечислением его элементов
  6. Создание векора с определенным числом элементов и с записанными значениями
  7. Число элементов вектора
  8. Обход вектора с помощью цикла (два варианта)
  9. Доступ к последнему элементу вектора
  10. Удаление последнего элемента вектора
  11. Итератор
  12. Итераторы begin() и end()
  13. Диапазоном
  14. Сортировка, разворот и перемешивание элементов вектора
  15. Обращение к элементу через итератор
  16. Функция lower_bound()
  17. Функция upper_bound()
  18. Применение итератора к функциям
  19. Метод .erase()
  20. Двусторонняя очередью (дек)
  21. Методы дека: push_back(), pop_back(), push_front() и pop_front()
  22. Стек. push(), pop(), top()
  23. Очередь. push(), pop(), front()
  24. Множество
  25. set
  26. unordered_set
  27. Методы множества: .insert(), .count(), .erase(), .finde()
  28. Перебор элементов множества
  29. Нахождение наибольшего и наименьшего значений в множестве
  30. Методы lower_bound(x) и upper_bound(x) в множестве
  31. Мультимножество. Методы
  32. Особенности удаления элемента из мультимножества
  33. Подсчет элементов в мультимножестве
  34. Отображение (ассоциативный массив)
  35. map и unordered_map
  36. Запрос к отображению на несуществующий ключ
  37. Проверка на наличие ключа в отображении
  38. Перебор ключ-значение в отображении
  39. Очередь с приоритетом
  40. В каких случаях лучше применять очередь с приоритетом?
  41. Основные операции очереди с приоритетом
  42. Создания очереди с приоритетом, поддерживающей поиск и удале- ние наименьшего элемента
  43. Структура данных indexed_set
  44. Сравнение множества и сортировки
  45. Сравнение отображения и массива

Графы

  1. Понятие графа. Вершины. Ребра
  2. Путь
  3. Длина пути
  4. Цикл
  5. Свзный граф
  6. Компоненты связности
  7. Дерево
  8. Ориентированный граф
  9. Взвешенный граф
  10. Путь во взвешенном графе
  11. Смежные вершины
  12. Степень вершины
  13. Сумма степеней всех вершин графа
  14. Регулярный граф
  15. Полный граф
  16. Полустепень захода
  17. Полустепень исхода
  18. Двудольный граф
  19. Свойство двудольного графа
  20. Списки смежности
  21. Матрица смежности
  22. Список ребер
  23. Поиск в глубину. Временная сложность
  24. Поиск в ширину. Временная сложность
  25. Проверка связности
  26. Обнаружение циклов
  27. Проверка графа на двудольность
  28. Алгоритм Беллмана-Форда. Нахождение отрицательных циклов
  29. Алгоритм Дейкстры
  30. Алгоритм Флойда-Уоршела
  31. Ориентированные ациклические графы
  32. Топологическая сортировка
  33. ДП в ориентированном ациклическом графе
  34. Графы приемников
  35. Нахождение приемников
  36. Обнаружение циклов в графе приемников
  37. Остовное дерево
  38. Вес остовного дерева
  39. Минимальное и максимальное остовные деревья
  40. Алгоритм Краскала
  41. Система непересекающихся множеств
  42. Алгоритм Прима