Лекция. LCA и немного задач. Z-функция

Философские вопросы

1. В разделе полезные ссылки появилась Алгоритмика
2. Решение задачек в теории затачивает ваш мозг. Реализация делает это еще эффективнее. Не пренебрегайте этим родом деятельности)
3. Вспомним, что было на прошлых лекциях.
4. Те, кто часто пишет раунды - напишите мне, я вас добавлю в наш локал чат.
5. Всем ли все понятно? Есть ли вопросы/предложения?

Гештальт

Задача на подпоследовательность в строке из предыдущего урока. Как избавиться от константы 27?

Задача - Вывести сколько вершин на каждом уровне дерева

vector<int> depth(n), depth_count(n);
vector<vector<int> > g(n, vector<ll> (0));

void dfs(int v, int d){
	depth[v] = d;
	depth_count[d]++;

	for(int i = 0; i<g[v].size(); i++){
		int to = g[v][i];
		if(!depth[to]) dfs(to, d+1);
	}
}

dfs(0, 1);

Задача - Как определить есть ли цикл в графе?

Эйлеров тур

Делаем dfs

Добавляем в массив вершину дважды - если входим в нее и если выходим

LCA - наименьший общий предок в дереве

Связь задачи LCA и static RMQ

Для большого класса задач требуется решить следующую вспомогательную задачу. Задача. Дано корневое дерево. Требуется отвечать на запросы нахождения наименьшего общего предка вершин $u_i$ и $v_i$, то есть вершины $w$, которая лежит на пути от корня до $u_i$, на пути от корня до $v_i$, и при этом самую глубокую (нижнюю) из всех таких.

ru.algorithmica.org

Реализация:

Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)

добавлено: 10 Jun 2008 22:30редактировано: 31 Dec 2011 1:58 Пусть дано дерево G. На вход поступают запросы вида (V1, V2), для каждого запроса требуется найти их наименьшего общего предка, т.е. вершину V, которая лежит на пути от корня до V1, на пути от корня до V2, и из всех таких вершин следует выбирать самую нижнюю.

e-maxx.ru

Задача о Ханойских башнях

Префикс функция

Префикс-функция

Определение. Префикс-функцией от строки $s$ называется массив $p$, где $p_i$ равно длине самого большого префикса строки $s_0 s_1 s_2 \ldots s_i$, который также является и суффиксом $i$-того префика (не считая весь $i$-й префикс). Например, самый большой префикс, который равен суффиксу для строки "aataataa" - это "aataa"; префикс-функция для этой строки равна $[0, 1, 0, 1, 2, 3, 4, 5]$.

ru.algorithmica.org