467.md (9453B)
1 Source: https://codeforces.com/blog/entry/13870 2 3 [467A - George and Accommodation](/contest/467/problem/A "Codeforces Round 267 (Div. 2)") 4 5 В этой задаче нужно было просто посчитать количество пар, у которых *q**i* - *p**i* ≤ 2 6 7 Асимптотика: *O*(*N*) 8 9 [467B - Fedor and New Game](/contest/467/problem/B "Codeforces Round 267 (Div. 2)") 10 11 В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа *X* и *Y*, то количество различных битов равнялось бы количеству единиц в числе *X* *xor* *Y*, где *xor* — операция исключающего или. 12 13 Асимптотика *O*(*M*·*N*) 14 15 [467C - George and Job](/contest/467/problem/C "Codeforces Round 267 (Div. 2)") 16 17 Решение этой задачи — динамическое программирование. Изначально нужно посчитать *psum**R*, где *psum**R* — сумма на префиксе массива *p* длиной *R*. 18 19 Обозначим *dp**i*, *j* — максимальная прибыль которую может получить Юра, если мы уже выбрали *i* последовательностей и последний элемент в *i*-ой последовательности имеет индекс *j*. 20 21 Очевидно, что если *i*·*m* > *j*, то *dp**i*, *j* = 0. Иначе *dp**i*, *j* = *max*(*dp**i*, *j* - 1, *dp**i* - 1, *j* - *m* + *psum**j* - *psum**j* - *m*) Ответом будет *dp**k*, *n*. 22 23 Ещё нужно было не забыть использовать **long long** при вычислениях. 24 25 Асимптотика: *O*(*N*·*K*) 26 27 [467D - Fedor and Essay](/contest/467/problem/D "Codeforces Round 267 (Div. 2)") 28 29 Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые. 30 31 Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов *X* и *Y* — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «*R*». Будем использовать номера, данные словам, для построения графа. 32 33 После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать *dp**ver* — пара, отвечающая за минимальное количество букв «*R*» и минимальную длину слова с минимальным количеством букв «*R*», которым можно заменить слово, за которое отвечает вершина *ver*. 34 35 Пересчет очевиден — *dp**ver* = *max*(*dp**nextVev*, *dp**ver*), где *nextVer* — все вершины, в которые можно пойти из *ver*. Максимум из двух пар берется как у pair в C++. 36 37 Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это *ver*. Тогда к ответу нужно прибавить *dp**ver*. 38 39 Также, важно было не забыть использовать **long long** при вычислениях. 40 41 Асимптотика: , где *w* — множество всех слов, которые есть в тексте и в словаре. 42 43 [467E - Alex and Complicated Task](/contest/467/problem/E "Codeforces Round 267 (Div. 2)") 44 45 Данная задача решалась жадно. 46 47 Алгоритм решения такой: 48 49 Набираем числа из массива *a* по очереди, пока в последовательности набранных чисел(далее *G*) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [*c*1, *c*2, *c*3, *c*4] = [*x*, *y*, *x*, *y*]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем *G* и *v* (далее будет описано, что такое *v*). 50 51 Очевидно, что этот алгоритм оптимален. 52 53 Для удобности сжимаем числа в массиве *a*. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива *a*. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка *O*(*N*). Теперь как быстро узнать, что в *G* найдется нужная нам четверка. 54 55 Давайте для каждого уникального числа *X* хранить список его позиций в *G*. Назовем этот список *v**X*. Теперь просто можно обработать операцию добавления числа в *G*. Пусть добавляемое число — это *X*. Добавим число *X* в список *G*. Пусть *i* — позиция добавленного числа в список *G*. 56 57 Теперь давайте добавим позицию *i* в список *v**X*. 58 59 Можно заметить такой факт: 60 61 Если размер списка *v**x* равен 4, то мы нашли нужную нам четверку. 62 63 Можно заметить ещё один факт: 64 65 Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно *c*4. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа *c*2. Всего возможных позиций числа *c*2 не больше двух, так как всего позиций, на которых стоит число *c*2, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом *c*4. Итого остается максимум две позиции. Пусть мы проверяем, то что *c*2 имеет позицию *L*, а *c*4 имеет позицию *R*. Остается только проверить существование таких *c*1 и *c*3, что *c*1 = *c*3 и их позиции *P* и *Q* соответственно. *P* и *Q* должны удовлетворять следующим условиям: 1 < *P* < *L*, *L* < *Q* < *R*. Это очень легко проверить. Давайте заведем массив *T*. *T**i* = максимальное *j*, что *G**i* = *G**j*. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, *L* - 1] в массиве *T*. Пусть результат запроса равен *Z*. Если он удовлетворяет условию *L* < *Z* < *R*, то четверка существует. Этим запросом мы нашли позицию числа *c*3 в списке *G*. По этим данным мы можем восстановить четверку. 66 67 Чтобы найти максимум на отрезке за , можно воспользоваться деревом отрезков или деревом Фенвика. 68 69 Итоговая асимптотика: .