292.md (6290B)
1 Source: https://codeforces.com/blog/entry/7371 2 3 [292A - SMS-центр](/contest/292/problem/A "Чемпионат КРОК 2013 - Раунд 1") 4 5 Для каждого момента *i* времени запомним количество сообщений *z*[*i*], которое нужно отправить в момент времени *i*. Теперь пройдем по каждому моменту времени от 1 до 106, поддерживая текущий размер очереди *sz*. На каждой итерации попробуем уменьшить размер очереди на 1, то есть выполним *sz* = *max*(*sz* - 1, 0), затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним *sz* = *sz* + *z*[*i*]. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если *sz* > 0. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ. 6 7 [292B - Топология сети](/contest/292/problem/B "Чемпионат КРОК 2013 - Раунд 1") 8 9 В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку *n* > = 4, *m* > = 3 и граф связный, то ответ однозначный. 10 11 1) все степени 2 и у двух вершин степень 1 — шина. 12 2) все степени 2 — кольцо 13 3) все степени 1 и у одной степень > 2 — звезда 14 4) иначе неизвестно 15 16 [292C - Красивые IP-адреса](/contest/292/problem/C "Чемпионат КРОК 2013 - Раунд 1") 17 18 Задача решается перебором. Для начала переберем сколько цифр в каждом четверти мы возьмем, например *AAA*.*B*.*CC*.*DDD*. Теперь посчитаем количество символов в этой строке (*AAABCCDDD*) и переберем цифры на первой половине этой строки (поскольку строка должна быть палиндромом, то вторая половина однозначно восстанавливается). После этого проверим, что такой ip-адрес является корректным и содержит правильный набор цифр. Если ip-адрес удовлетворяет всем условиям задачи, то добавим его к ответу. 19 20 [292D - Компоненты связности](/contest/292/problem/D "Чемпионат КРОК 2013 - Раунд 1") 21 22 Ограничения в задаче были не слишком удачными и провоцировали писать решение за квадрат, мы постарались максимально не позволить таким решениям пройти. 23 24 У этой задачи много правильных решений. Изначально планировалось решение, которое предподсчитывает частичные *dsu* (структура данных disjoint set union) на префиксах и на суффиксах, то есть массивы *ldsu*[*M*][*N*] и *rdsu*[*M*][*N*]. После этого на запрос [*lf* ; *rg*] легко ответить за время *O*(*N*·*A*- 1), если объединить множества *ldsu*[*lf* - 1] и *rdsu*[*rg* + 1], где *A*- 1 -- обратная функция Аккермана (константа от dsu). 25 26 [292E - Копирование данных](/contest/292/problem/E "Чемпионат КРОК 2013 - Раунд 1") 27 28 У этой задачи много правильных решений. Изначально предполагалось решение, использующие корневую эвристику. Разобьем все запросы на *sqrt*(*m*) блоков. Будем поддерживать текущий массив *b* в виде отрезков в массиве *z*, который хранит четверки (*lf*, *rg*, *type*, *start*), где *lf*, *rg* — отрезок индексов массива *b*, *type* — 0 или 1, означающее из какого массива взяты числа для этого отрезка, *start* — позиция начала этого отрезка в массиве типа *type*. 29 30 На запросы будем отвечать в тупую, то есть честно пересчитывать как изменится массив *z* от запроса копирования и отвечать на запросы значения в позициях. Однако, каждые *sqrt*(*m*) запросов будем сливать данные из массива *z* в массив *b*, для того чтобы сам массив *z* сильно не разрастался. 31 32 Есть простое решение с деревом отрезков, которое умеет делать покраску на отрезке. Пусть пришел запрос копирования [*lf* ; *rg*], , тогда покрасим отрезок запроса [*lf* ; *rg*] в цвет, равный номеру запросу. Все запросы будем сохранять. Пусть пришел запрос значения в позиции *x*, тогда найдем цвет в дереве в этой позиции. Если такого цвета нет, значит мы находимся в исходном массиве *b* (выведем *b*[*x*]), иначе посчитаем смещение *dx* от начала этого запроса до нашей позиции *x* и выведем *a*[*x* + *dx*].