Разбор квалификационного раунда VK Cup 2021
Автор tourist, 3 года назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

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

D ещё можно решать деревом отрезков

Состояние:

  • итоговая блокировка (lock/unlock/unknown)

  • итоговый цвет, если в начале было lock

  • итоговый цвет, если в начале было unlock

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я тоже через дерево отрезков сделал, но хуже) Состояния: c, u, l, uc, ucl, cu, cl — Здесь c — это некий цвет, u — unlock, l — lock.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Еще в D можно написать корневую декомпозицию, внутри блоков эмуляция как в задаче A, а каждый блок умеет отвечать на вопросы "если (не)было заблокировано, то что будет с цветом/блокировкой после этого блока".

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

В задаче C можно было не думать, а написать динаму за квадрат (см. функцию dyn) https://codeforces.com/contest/1531/submission/117814604

→ Ответить