<a href="http://mirror.codeforces.com/contest/570/problem/A" title="Codeforces Round 315 (Div. 2)">570А — Выборы </a>↵
↵
**Реализация**↵
↵
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.↵
↵
$O(n * m)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523729" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Простая игра </a>↵
↵
**Математика, разбор случаев**↵
↵
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором $|a – m| > 1$ так, как мы можем увеличить вероятность победы, если подвинем число a ближе кm$m$. ↵
↵
Таким образом, мы рассматриваем два варианта хода $a = c – 1$ и $a = c + 1$. Вероятность победы в первом случае $(c – 1) / n$, во втором $(n – c + 1) / n$. Выбираем наилучший вариант. Нужно помнить про случай $n = 1$.↵
↵
$O(1)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523744" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Замены</a>↵
↵
**Разбор случаев, (возможно) структуры**↵
↵
Рассмотрим, как происходят замены. Если был отрезок из точек длиныL$l$, то мы потратим L$l – 1$ операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков. ↵
↵
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. ↵
↵
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. ↵
↵
$O(n + m)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523751" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Деревянные запросы</a>↵
↵
**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)$ памяти↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523757" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Свинка и палиндромы</a>↵
↵
**ДП**↵
↵
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. ↵
↵
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Если у первой клетки координаты $(x1; y1)$, у последней $(x2; y2)$, то $x1 + y1 = n + m - x2 - y2$.↵
↵
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя.↵
$O(n^3)$ – времени и $O(n^2)$ — памяти↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523769" title="Codeforces Round 315 (Div. 2)">Решение</a>
↵
**Реализация**↵
↵
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.↵
↵
$O(n * m)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523729" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Простая игра </a>↵
↵
**Математика, разбор случаев**↵
↵
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором $|a – m| > 1$ так, как мы можем увеличить вероятность победы, если подвинем число a ближе к
↵
Таким образом, мы рассматриваем два варианта хода $a = c – 1$ и $a = c + 1$. Вероятность победы в первом случае $(c – 1) / n$, во втором $(n – c + 1) / n$. Выбираем наилучший вариант. Нужно помнить про случай $n = 1$.↵
↵
$O(1)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523744" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Замены</a>↵
↵
**Разбор случаев, (возможно) структуры**↵
↵
Рассмотрим, как происходят замены. Если был отрезок из точек длины
↵
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. ↵
↵
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. ↵
↵
$O(n + m)$↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523751" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Деревянные запросы</a>↵
↵
**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)$ памяти↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523757" title="Codeforces Round 315 (Div. 2)">Решение</a>↵
↵
<a href="http://mirror.codeforces.com/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Свинка и палиндромы</a>↵
↵
**ДП**↵
↵
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. ↵
↵
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Если у первой клетки координаты $(x1; y1)$, у последней $(x2; y2)$, то $x1 + y1 = n + m - x2 - y2$.↵
↵
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя.↵
$O(n^3)$ – времени и $O(n^2)$ — памяти↵
↵
<a href="http://mirror.codeforces.com/contest/570/submission/12523769" title="Codeforces Round 315 (Div. 2)">Решение</a>
