Очередная наша задача - 2593. Find Score of an Array After Marking All Elements. Ну и так как наша цель не просто решать, а показывать имплементацию разных техник, то воспользуемся-ка мы идеей битового множества (его в стандартную библиотеку Rust еще "не подвезли", так что и операции имплементируем сами).
Задача 🧩
Дан массив положительных целых чисел nums. Ваша цель — получить максимальное значение score, выполняя следующие действия:
- Выберите наименьший немаркированный элемент массива (при равенстве — элемент с меньшим индексом).
- Добавьте значение этого элемента к
score.
- Пометьте выбранный элемент и его двух соседей (если они существуют).
- Повторяйте, пока все элементы не будут помечены.
Необходимо вернуть итоговое значение score.
Идея 💡
В данной задаче нужно эффективно следовать указанным правилам. Чтобы сделать это:
- (а) Мы отсортируем индексы массива nums по значениям, чтобы обрабатывать элементы в правильном порядке, начиная с наименьших.
- (б) Используем битовое множество (
Vec<u128>) для компактного представления состояния "помечен" для элементов массива.
Подход 🚀
Читать дальше →
Описание задачи 📋
Дано неориентированное дерево с nn узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
- Запускаем DFS от корня.
- Для каждого узла вычисляем остаток от суммы поддерева (
sum%k) и проверяем, можно ли выделить текущую часть как отдельный компонент.
Читать дальше →