570А — Выборы Реализация
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя. O(n * m)
570B — Простая игра Математика, разбор случаев
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a – m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m. Таким образом, мы рассматриваем два варианта хода a = c – 1 и a = c + 1. Вероятность победы в первом случае (c – 1) / n, во втором (n – c + 1) / n. Выбираем наилучший вариант. Нужно помнить про случай n = 1. O(1)
570C — Замены Разбор случаев, (возможно) структуры
Рассмотрим, как происходят замены. Если был отрезок из точек длины L, то мы потратим L – 1 операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков. После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. O(n + m)
570D — Деревянные запросы DFS, бинарный поиск
Запишем вершины в порядке DFS от корня для вершин каждой глубины отдельно, храним время входа/выхода из вершины в DFS. Все вершины находящиеся в поддереве v, в такой записи представляют отрезок. Теперь мы умеем получать все вершины в v на высоте h, в виде отрезка, делая два бинарных поиска. Палиндром можно составить, если количество нечетных вхождений каждой буквы меньше 2. Эту функцию можно посчитать для каждого префикса в обходе на каждой глубине отдельно. Для экономии памяти можно воспользоваться битовым сжатием, поняв, что нас интересует только четность и функция – это xor.
O(m * (log n + 26) + n) – времени O(n * 26) — памяти, существует офлайн решение за O(m * 26 / 32 + n) и O(n * 26 / 8) памяти
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя. O(n^3) – времени и O(n^2) — памяти
