Блог пользователя el_sanchez

Автор el_sanchez, история, 8 лет назад, По-русски

Традиционный пост от snarknews запаздывает, поэтому создам свой.

Итак, позавчера закончился четвёртый этап SNSS-2016.

Как решать задачу A? Есть ли какой-нибудь простой жадный алгоритм для задачи D?

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

A: Скажем, что R это 1, L это 0, тогда мы делаем ксор двух соседних чисел. Не очень удобно, что мы считаем ксор предыдущего и следующего числа. Давайте считать ксор текущего и числа на две позиции дальше, а потом в конце нужное количество раз перемотаем массив вправо. Заметим, что через 2^k шагов, число a[i] будет проксорено с a[i+2*2^k]. Просто разложим количество шагов на степени двоек и сделаем соответствующие действия.

D: Просто берем самую часто встречаемую левую половину и дополняем её как можно большим количеством самых встречаемых правых половинок. Довольно легко делается сетом пар <количество, половина билета> .