Факультет прикладной математики — процессов управления
Факультет прикладной математики — процессов управления
5️⃣

Лекция. 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

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

image

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

Реализация:

‣
Код
typedef vector < vector<int> > graph;
typedef vector<int>::const_iterator const_graph_iter;


vector<int> lca_h, lca_dfs_list, lca_first, lca_tree;
vector<char> lca_dfs_used;

void lca_dfs (const graph & g, int v, int h = 1)
{
	lca_dfs_used[v] = true;
	lca_h[v] = h;
	lca_dfs_list.push_back (v);
	for (const_graph_iter i = g[v].begin(); i != g[v].end(); ++i)
		if (!lca_dfs_used[*i])
		{
			lca_dfs (g, *i, h+1);
			lca_dfs_list.push_back (v);
		}
}

void lca_build_tree (int i, int l, int r)
{
	if (l == r)
		lca_tree[i] = lca_dfs_list[l];
	else
	{
		int m = (l + r) >> 1;
		lca_build_tree (i+i, l, m);
		lca_build_tree (i+i+1, m+1, r);
		if (lca_h[lca_tree[i+i]] < lca_h[lca_tree[i+i+1]])
			lca_tree[i] = lca_tree[i+i];
		else
			lca_tree[i] = lca_tree[i+i+1];
	}
}

void lca_prepare (const graph & g, int root)
{
	int n = (int) g.size();
	lca_h.resize (n);
	lca_dfs_list.reserve (n*2);
	lca_dfs_used.assign (n, 0);

	lca_dfs (g, root);

	int m = (int) lca_dfs_list.size();
	lca_tree.assign (lca_dfs_list.size() * 4 + 1, -1);
	lca_build_tree (1, 0, m-1);

	lca_first.assign (n, -1);
	for (int i = 0; i < m; ++i)
	{
		int v = lca_dfs_list[i];
		if (lca_first[v] == -1)
			lca_first[v] = i;
	}
}

int lca_tree_min (int i, int sl, int sr, int l, int r)
{
	if (sl == l && sr == r)
		return lca_tree[i];
	int sm = (sl + sr) >> 1;
	if (r <= sm)
		return lca_tree_min (i+i, sl, sm, l, r);
	if (l > sm)
		return lca_tree_min (i+i+1, sm+1, sr, l, r);
	int ans1 = lca_tree_min (i+i, sl, sm, l, sm);
	int ans2 = lca_tree_min (i+i+1, sm+1, sr, sm+1, r);
	return lca_h[ans1] < lca_h[ans2] ? ans1 : ans2;
}

int lca (int a, int b)
{
	int left = lca_first[a],
		right = lca_first[b];
	if (left > right)  swap (left, right);
	return lca_tree_min (1, 0, (int)lca_dfs_list.size()-1, left, right);
}

int main()
{
	graph g;
	int root;
	... чтение графа ...

	lca_prepare (g, root);

	for (;;)
	{
		int v1, v2; // поступил запрос
		int v = lca (v1, v2); // ответ на запрос
	}
}

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

image
‣
Код
def tower_of_hanoi(numbers, start, auxiliary, end):  
    if(1 == numbers):  
        print('Move disk 1 from rod {} to rod {}'.format(start, end))  
        return
    tower_of_hanoi(numbers - 1, start, end, auxiliary)  
    print('Move disk {} from rod {} to rod {}'.format(numbers, start, end))  
    tower_of_hanoi(numbers - 1, auxiliary, start, end)  
  
tower_of_hanoi(numbers, 'A', 'B', 'C')

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

©Леонид Романычев