codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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*: добавим в неё ![](https://espresso.codeforces.com/014997ce757f6eec0513c86c4dc1dacd3d6294de.png) букв 'a', ![](https://espresso.codeforces.com/459d21b3c039ce9baf26e26acf172a6eade53dbc.png) букв '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*)