Перейти к содержанию

Олимпиадное программирование — заметки

Список статей

Олимпиадное программирование¶

Тут будут написаны статьи, что вы увидите в ближайшем будущем.

🟢 Часть I — Базовые техники¶

1. Введение¶

[v1] Языки программирования в олимпиадах
[v1] Ввод и вывод данных (I/O)
[v1] Работа с числами и типами данных
[v1] Сокращение кода
[v1] Математическая база для олимпиадника
[v1] Соревнования и ресурсы - в работе

2. Оценка сложности алгоритмов¶

3. Сортировки и бинарный поиск¶

4. Базовые структуры данных¶

5. Полный перебор¶

[v1] Генерация подмножеств --- Практикум
[v1] Генерация перестановок
[v1] Backtracking
[v1] Оптимизация перебора (pruning)
[v1] Meet in the Middle

6. Жадные алгоритмы¶

7. Динамическое программирование¶

8. Амортизированный анализ¶

9. Запросы на отрезках¶

[v1] Статические запросы
[v1] Дерево Фенвика (Binary Indexed Tree)
[v1] Segment Tree
[v1] Продвинутые техники

10. Битовые операции¶

🔵 Часть II — Алгоритмы на графах¶

11. Основы графов¶

12. Обход графа¶

13. Кратчайшие пути¶

14. Алгоритмы на деревьях¶

Отсюда проверить содержимое на косяки верстки

15. Остовные деревья¶

16. Ориентированные графы¶

17. Сильная связность¶

18. Запросы на деревьях¶

19. Пути и циклы¶

[ ] Эйлеровы пути и циклы — В разработке
[ ] Гамильтоновы пути — В разработке
[ ] Последовательности де Брёйна — В разработке
[ ] Тур коня — В разработке

20. Потоки и разрезы¶

[ ] Алгоритм Форда–Фалкерсона — В разработке
[ ] Edmonds–Karp — В разработке
[ ] Максимальное паросочетание — В разработке
[ ] Минимальный разрез — В разработке
[ ] Покрытия путями — В разработке

🟣 Часть III — Продвинутые темы¶

21. Теория чисел¶

[ ] Простые числа и решето Эратосфена — В разработке
[ ] Разложение на множители — В разработке
[ ] Модульная арифметика — В разработке
[ ] Быстрое возведение в степень — В разработке
[ ] Обратный элемент по модулю — В разработке
[ ] Китайская теорема об остатках — В разработке
[ ] Диофантовы уравнения — В разработке

22. Комбинаторика¶

[ ] Биномиальные коэффициенты — В разработке
[ ] Числа Каталана — В разработке
[ ] Принцип включений-исключений — В разработке
[ ] Лемма Бёрнсайда — В разработке
[ ] Формула Кэли — В разработке

23. Матрицы¶

[ ] Операции над матрицами — В разработке
[ ] Быстрое возведение матрицы в степень — В разработке
[ ] Линейные рекуррентности — В разработке
[ ] Связь графов и матриц — В разработке

24. Теория вероятностей¶

[ ] Основы вычисления вероятностей — В разработке
[ ] Случайные величины — В разработке
[ ] Математическое ожидание — В разработке
[ ] Марковские цепи — В разработке
[ ] Рандомизированные алгоритмы — В разработке

25. Теория игр¶

[ ] Игровые состояния — В разработке
[ ] Игра Ним — В разработке
[ ] Теорема Шпрага–Гранди — В разработке
[ ] Игры на графах — В разработке

26. Строковые алгоритмы¶

[ ] Термины и основы — В разработке
[ ] Trie — В разработке
[ ] Префикс-функция (KMP) — В разработке
[ ] Z-функция — В разработке
[ ] Хеширование строк — В разработке
[ ] Суффиксные массивы — В разработке

27. √-алгоритмы¶

[ ] Декомпозиция по блокам — В разработке
[ ] Алгоритм Мо — В разработке
[ ] Комбинирование техник — В разработке

28. Деревья отрезков (углубление)¶

[ ] Lazy propagation — В разработке
[ ] Динамические деревья — В разработке
[ ] Двумерные деревья — В разработке

29. Геометрия¶

[ ] Комплексные числа — В разработке
[ ] Точки и прямые — В разработке
[ ] Площадь многоугольника — В разработке
[ ] Расстояния и пересечения — В разработке
[ ] Выпуклая оболочка — В разработке

30. Sweep Line¶

[ ] Точки пересечения — В разработке
[ ] Ближайшая пара точек — В разработке
[ ] Задача о выпуклой оболочке — В разработке