SM
или с QP?
Size: a a a
2020 July 24
BM
Битмасками проверить можно ли провести линию между двумя множеством из единиц и нулей, а потом аккуратненько смерджить
Что значит "смерджить"?
Ш
Что значит "смерджить"?
ну вроде каждая прямая делит на два множество
Ш
но нам нужно чтобы все точки отделились
Ш
то есть несколько прямых
Ш
думаю это имели ввиду
KK
а как сливать ?)
У тебя есть набор битмасок, a отделимо от b 1 прямой
KK
Соответственно, делаешьединые битмаски
KK
Ставишь a | b = 1
KK
Если там отделимо
KK
Во всех остальных случаях инициалайзишь +inf
KK
Теперь за 3^n перебираешь подмаски данной маски (пусть будет bm) и выбираешь min(ans[bm] + ans[~bm])
KK
Идешь, естественно, снизу
EZ
n^2 * 2^2n
Откуда 2n
KK
Откуда 2n
Ну у тебя n состояний + n состояний
KK
Меньше, естественно
EZ
Ну у тебя n состояний + n состояний
Ну типа перебираешь тернарные маски
EZ
1 отделимо от 2
EZ
Чяднт?