Codeforces Round #367 (Разбор)

Правка ru2, от NBAH, 2016-08-11 23:50:55

A

Научимся определять расстояние между точками. Далее, зная, что время — это расстояние делить на скорость, будем определять время для каждого таксиста, за которое он сможет доехать до Василия. Ответ это минимальное из времен.Не забудем про double.

Асимптотика O(n).

B

Пусть c[x] — количество магазинов в которых цена за напиток равна x. Посчитаем для этого массива префиксные суммы. Далее возможные следующие варианты: 1)Если текущее количество денег у Василия больше, чем размер массива с префиксными суммами то выводим n. 2)Иначе выводим префиксную сумму для количества денег, которое сейчас у Василия. Асимптотика O(q+n).

C

Будем решать задачу динамическим программированием. dp[i][j] — это минимальное количество энергии, которое надо потратить чтобы расположить первые i строк в алфавитном порядке и i-ая из них будет перевернута если j=1 и не перевернута если j=0. dp[i][j] обновляем через dp[i-1][0] и dp[i-1][1]. Остается проверить, что i-ая строка лексикографически больше (i-1)-ой(если j=1 то проверяем перевернутую i-ую строку, аналогично для i-1-ой). После чего обновляем dp[i][j]=min(dp[i][j],dp[i-1][0]+c[i]*j), dp[i][j]=min(dp[i][j],dp[i-1][1]+j*c[i]). Ответ это минимум из dp[n][0] и dp[n][1].

Асимптотика O(n+sum_length).

D

Каждое число из множества будем хранить в двоичной системе счисления(каждое число будет состоять из 32-х 0 или 1) в такой структуре данных как бор(рёбра — это будут биты 1 или 0, а вершины будут отвечать за то, можно ли пройти по текущему ребру). Чтобы ответить на запрос типа "? x" будем спускаться по бору от старших битов к младшим и смотреть можем ли мы сейчас ксором в i-м бите получить единицу, если можем, то переходим, иначе идём туда, куда можем идти.

Асимптотика O(q*log(10^9)).

E

Обнесем матрицу рамкой из фиктивных элементов. В каждом элементе матрицы и рамки храним значение элемента номер элемента соседнего справа и номер элемента соседнего снизу. Когда приходит запрос поменять местами прямоугольники надо поменять значения элементов только по периметру прямоугольников.

Асимптотика O(q*(n+m)).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru7 Русский NBAH 2016-08-12 14:14:05 49
ru6 Русский NBAH 2016-08-12 14:13:31 192
en7 Английский NBAH 2016-08-12 14:10:10 241
ru5 Русский NBAH 2016-08-12 14:01:30 340
en6 Английский NBAH 2016-08-12 14:00:03 345
ru4 Русский NBAH 2016-08-12 11:17:18 60
ru3 Русский NBAH 2016-08-12 11:15:17 6
en5 Английский NBAH 2016-08-12 11:13:36 4
en4 Английский NBAH 2016-08-12 11:13:14 54
en3 Английский NBAH 2016-08-12 11:07:57 4 Tiny change: ' can look RRF in the i-' -> ' can look XOR in the i-'
ru2 Русский NBAH 2016-08-11 23:50:55 8 Мелкая правка: 'оседнего слева. Когда пр' -> 'оседнего снизу. Когда пр'
en2 Английский NBAH 2016-08-11 23:50:19 541 (published)
en1 Английский NBAH 2016-08-11 23:45:01 2129 Initial revision for English translation (saved to drafts)
ru1 Русский NBAH 2016-08-11 22:31:18 2288 Первая редакция (опубликовано)