Loading [MathJax]/jax/output/CommonHTML/jax.js

Розбір 3 дня літньої школи в Хусті 2024 | Статті

A. Найпростiшi запити

Для розвязання цієї задачі можна використати різноманісті структури даних і підходи, наприклад, дерево відрізків, дерево Фенвіка, коренева декомпозиції та інші.

B. Найнижчий спiльний предок

У даній задачі потрібно реалізувати двійкові підйоми і пошук нанижчого спільного предка.

Код розв’язку мовою C++

C. Квіти

Визначимо, що в день i буде в кожній вершині значення рівне xv+i, будемо підтримувати такий інваріант. Тоді для обрахунку кількості квітів на шляху нам достатньо порахувати суму значень xv і додати кількість вершин на шляху помножена на номер дня i. Запит першого типу змінює xv на i так аби підтримувати інваріант. Тому задача перетворюється до зміни значення в вершині і обрахунку суми на шляху.

Код розв’язку мовою C++

D. Складніші запити на дереві

Першочергово змінимо запити, збільшити значення вершин на шляху від a до b можна розкласти на збільшення значення на шляхах до кореня від вершин a, b та їх lca і окремо треба збільшити значення в lca.

Розглянемо запит суми в піддереві вершини x, нам треба порахувати по усіх запитах v,val з піддерева порахувати значення (d[v]d[x]+1)val=d[x](val)+(d[v]+1)val, де d[v] - глибина вершини. Ми можемо порахувати в піддереві суму val - нехай це буде k, також суму значень (d[v]+1)val - її позначемо як b. Для того аби порахувати відповідь нам треба порахувати формулу d[x]k+b.

Код розв’язку мовою C++

E. Війна

Розбір задачі доступний на сайті - Розбір районної 2022.

F. Найпростіші запити на дереві

Переформулювавши задачу на масиві можемо отримати таку задачу: додати значення усім числам на відрізку і знайти максимум на відрізку. Для цього можна використати дерево відрізків з обіцянками або лінивим оновленням.

Код розв’язку мовою C++

G. Колобок

Перетворимо рядки до маленьких букв і можна вставити ці рядки в множину (set) і вивести розмір цієї множини як відповідь.

H. Розробка вакцини

Розбір задачі доступний на сайті - Розбір районної 2021.

I. Колобок: факти та фікції

Розбір задачі доступний на сайті - Розбір обласної 2017.