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

Revision ru6, by NBAH, 2016-08-12 14:13:31

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)).

Решение

History

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