Поиск компонент связности
В цикле запускать dfs. Отмечать уже помеченные вершины.
Топологическая сортировка
Помечать “времена выхода” из вершины. Отсортировать в порядке убывания времен выхода.
Бинарный поиск
int l = 0, r = n;
// надо найти х
int x;
while(r - l > 1){
int mid = (r + l) / 2;
if(mid < x) l = mid;
else r = mid;
}
cout << l << "\n";vector<ll> a;
// бинарный поиск, возвращают итераторы
auto t = lower_bound(a.begin(), a.end(), to_find); //ищет больше или равный to_find
cout << *t;
upper_bound(a.begin(), a.end(), to_find); //большее значениеТернарный поиск
double l = ..., r = ..., EPS = ...; // входные данные
while (r - l > EPS) {
double m1 = l + (r - l) / 3,
m2 = r - (r - l) / 3;
if (f (m1) < f (m2))
l = m1;
else
r = m2;
}Диаметр дерева
Две наиболее удаленные друг от друга вершины
Алгоритм:
- DFS от какой-то вершины
- DFS от самой удаленной на предыдущем шаге
Топологическую сортировку
Фиксируем времена выхода. Сортируем вершины в порядке уменьшения времен выхода.
Бинарное возведение в степень
Если n четное
Если n нечетное
int binpow (int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow (a, n-1) * a;
else {
int b = binpow (a, n/2);
return b * b;
}
}НОД/НОК
int gcd (int a, int b) {
return b ? gcd (b, a % b) : a;
}
int lcm (int a, int b) {
return a / gcd (a, b) * b;
}Факторизация
def factorize(n):
divisor = 2
while divisor ** 2 <= n:
if n % divisor == 0:
n //= divisor
print(divisor)
else:
divisor += 1
if n != 1:
print(n)
n = int(input())
factorize(n)Динамическое программирование
Задача о кузнечике
Задача о черепашке
Задача о рюкзаке