Старые задачи
Задача про стэки
Задача про дэки
Про dfs и bfs
Условие
Пример того, что должен делать dfs
Пример того, что должен делать bfs
dfs-решение
bfs-решение
Задачи на DFS и BFS
a) Посчитать число компонент связности неорграфа графа (за O(E))
b) Покраска вершин графа в 2 цвета таким образом, что ребра соединяют только вершины разных цветов (за O(E))
c) Поиск цикла в орграфе (за O(E))
d) Поиск кратчайшего пути между 2-мя вершинами в невзвешенном графе (за O(E))
e) Кратчайший путь между 2-мя вершинами во взвешенном графе (за O(VE))
f) Поиск самого короткого цикла в орграфе (за O(VE))
g) Проверка: является ли граф деревом? (за O(E))
h) Две максимально далекие друг от друга вершины в неорграфе (за O(VE))
i) Две максимально далекие друг от друга вершины в деревe за O(N)
Алгоритмы на графах [Тут можно прочитать про алгоритм Флойда]
a) Флойд за O(N^3) (Найти в для графе G матрицу расстояний D[a,b] - расстояния между всеми парами вершин)
Задачи на множества
a) N <= 20, M <= 20
b) Найти гамильтонов цикл в графе из N (3 <= N <= 20) вершин.
c) Транзитивное замыкание Флойда-Уоршелла за O(N^3/logN) (Найти в для графе G матрицу Is[a,b] - достижима ли вершина a из вершины b)
d) Еще одна задача про множества (можно решать сложную версию задачи: N <= 18)
Дерево отрезков
a) Научиться считать сумму (+ самопроверка)
b) 1028
с) 1316
d) Научиться красить (+ самопроверка)
Кодирование
a) 7-бит
b) ab --> 256
Z-функция [подсказака]
a) Поиск подстроки в строке.
b) Нахождение минимального периода строки.
Хэши
a) Найти все вхождения строки S в текст T за O(|S|+|T|)
b) Найти самый длинный подпалиндром строки S за O(|S|)
c) Найти самую длинную подстроку строки S, которая встречается в ней хотя бы 2 раза.
Бор
a) Найти число различных подстрок строки S. Длины строки S не больше 300.
b) См. (a) Длины строки S не больше 5000.
Bonus
a) Даны N (1 <= N <= 10^5) монет различной стоимости (натуральные числа).
Нужно найти минимальную стоимость, которую нельзя набрать этими монетами (каждую можно брать не более одного раза)
b) Даны 2 кучки монет, 2-е играют в игру - можно брать произвольное число камней из одной кучки,
или произвольное одинаковое число камней из обеих кучек. Кто берет последний - проиграл.
Изначальное число камней в кучках - X, Y (1 <= X, Y <= 100).
c) New! [продолжение (a)] Добавить к набору несколько чисел (как можно меньше) так, чтобы можно было набрать все возможные суммы от 1 до S (1 <= S <= 10^9).
Зачетные задания для младшей группы