219.md (7940B)
1 Source: https://codeforces.com/blog/entry/5158 2 3 Итак, начнём разбор. 4 5 ### [219A - k-String](/contest/219/problem/A "Codeforces Round 135 (Div. 2)") 6 7 Давайте для каждой буквы *l* посчитаем, сколько раз она встретилась в строке --- массив *c*[*l*]. Подсчет осуществляется примерно так: `c[s[i]]++`. Если количество вхождений какой-то буквы не кратно *k*, то мы уже сразу понимаем, что составить нужную нам строку невозможно. Теперь построим строку *p*: добавим в неё  букв 'a',  букв 'b', и так далее. Выведем полученную строку *k* раз. 8 9 ### [219B - Special Offer! Super Price 999 Bourles!](/contest/219/problem/B "Codeforces Round 135 (Div. 2)") 10 11 Переберем количество девяток на конце числа от 1 до 18. Пусть эта величина равна *k*. В таком случае максимальное число не превосходящее заданное *p* можно получить так: 12 13 * сотрем последние *k* цифр числа *x*: = *p* / 10*k* 14 * добавим справа *k* девяток *y*: = *x*·10*k* + 10*k* - 1 15 * если значение *y* больше *p*, то уменьшим число *x* (то, что идет до *k* девяток) на 1 и к результату допишем *k* девяток *y*: = (*x* - 1)·10*k* + 10*k* - 1 16 17 Если получившееся *y* > = *p* - *d*, то обновим ответ значением *k*. 18 19 ### [219C - Color Stripe](/contest/219/problem/C "Codeforces Round 135 (Div. 2)") 20 21 Разберём 2 два случая: 22 23 1. *k* равно 2. Тогда нам подходят только две строки — чередующиеся буквы 'A' и 'B'. Выбираем из них тот, который требует меньшего числа перекрасок. 24 2. *k* больше 2. Возьмем самый левый блок из одинаковых букв. Пусть его длина равна *k*, тогда надо не менее *k* / 2 перекрашиваний, чтобы избавиться от соседних одинаковых клеток в этом блоке. Если *k* нечетно, то можно каждую вторую клетку в блоке перекрасить в любой из цветов, отличных от цвета блока. Если *k* четно, то можно делать тоже самое, но аккуратнее выбрать цвет: он должен отличаться не только от цвета блока, но и от цвета следующей клетки за блоком. Это всегда возможно сделать, так как количество цветов больше 2. 25 26 ### [219D - Choosing Capital for Treeland](/contest/219/problem/D "Codeforces Round 135 (Div. 2)") 27 28 Для того, чтобы решить эту задачу посчитаем для каждого города количество ребер, которые надо переориентировать, чтобы данный город стал столицей. 29 30 В задаче были достаточно большие ограничения, поэтому нельзя было просто посчитать все эти значения *n* обходами в глубину. Авторское решение запускает только два обхода в глубину. Первым обходом в глубину посчитаем ответ для города номер 1. Заметим, что если посчитан ответ для вершины *x*, то ответ для вершины *y*, которая соединена с *x*, можно посчитать за *O*(1). А именно, *ans*(*y*) = *ans*(*x*) - *direction*(*x*, *y*) + (1 - *direction*(*x*, *y*)), где *direction*(*x*, *y*) — равно 1, если ребро (*x*, *y*) ориентировано не так как во входных данных, и равно 0, иначе. 31 32 Пользуясь описанным фактом, можно посчитать все значения *ans*(*v*) одним обходом, зная *ans*(1). 33 34 Итоговая ассимптотика решения *O*(*n*). 35 36 ### [219E - Parking Lot](/contest/219/problem/E "Codeforces Round 135 (Div. 2)") 37 38 Будем поддерживать две структуры: множество отрезков свободных парковочных мест, в котором отрезки отсортированы по их началу, и множество отрезков свободных парковочных мест отсортированных по размеру. Такие структуры должны поддерживать операцию быстрого поиска первого больше либо равного элемента, удаление элемента и его вставку, нахождениe максимума и следующего по величине элемента. 39 40 В языке C++, авторское решение использовало set `<pair<int,int>>` и map `<int, set<int>>`. Set отрезков и Map из длины отрезка в набор отрезков с заданной длиной. Операция поиска больше либо равного элемента в этих структурах называется lower_bound. 41 42 Научимся поддерживать эти структуры от операции к операции. Для того, чтобы определить автомобилиста на стоянку, нужно взять свободный отрезок с максимальной длиной или с (максимальной длиной минус один), который не упирается в начало или конец стоянки, и попробовать определить автомобилиста на свободное парковочное место в середину этого отрезка (если точной середины нет, то в ближайшую к ней клетеку). Среди всех таких позиций нужно выбрать наилучшую (в смысле условия задачи). После нахождения лучшей позиции надо разрезать соотвествующий отрезок свободных позиций на два и обновить обе структуры (удалить старый отрезок и вставить два новых). 43 44 Чтобы удалить автомобилиста со стоянки нужно добавить новый отрезок свободных парковочных мест длины один в структуру. Предварительно нужно удалить смежные с этим отрезком отрезки в структуре. Соединить их с нашим отрезком и добавить один большой отрезок в структуру. 45 46 Отдельные случаи возникает при рассмотрении крайних отрезков. 47 48 Итоговая сложность решения *O*(*m* *log* *n*)