Almaty Code Cup

Задача A: Особенные пары --- буквально соответствующие пары скобок в последовательности. Построим дерево (лес) вложенности этих пар скобок (достаточно один раз пройти стеком по строке). Заметим, что удаление какой-то пары скобок никак не влияет на то кто с кем остается в паре. Заметим, что удаление пары скобок на дереве значит удаление какой-то вершины и переподвешивание её детей к предку удалаяемой вершины. Ответом на задачу является количество деревьев в лесу, что то же самое, что количество корней в лесу. Для удобства заменим s = "(" + s + ")" чтобы у нас было ровно одно дерево и неудаляемый корень, при этом ответом будет количество его детей. Сделаем ДП вида dp[v][k] --- максимальное количество корней которое мы можем получить в поддереве вершины v удалив ровно k вершин. Это можно легко пересчитывать как dp[v][k] = max(dp[x][k1] + dp[y][k - k1]). Остается заметить что это ДП работает за O(n^2), потому что каждая пара вершин в дереве внесет константу действий в пересчет этой дпшки ровно когда мы будем обрабатывать их LCA.

Задача B1: Для получения максимального значения нам не выгодно включать бит у которого знак '-' и выгодно включать бит где знак '+'. Для получения минимального значения наоборот.

Задача B2: Переведем входные данные в обычные битовые строки и сохраним их в боре от больших битов к меньшим. Чтобы для числа x найти максимальное значение max(x ^ y) надо спускаться по бору и проверять: если текущий знак бита это '+', то можно ли включить бит в числе (x ^ y), если же это '-', то можно ли этот бит наоборот выключить. P.S. вместо бора можно просто делать lower_bound'ы на массиве.

Задача C: Покажем, что при оптимальной стратегии либо Пладислав выиграет за не более чем два своих хода, либо он точно проиграет. Для того чтобы Пладу победить он должен какую-то из скобок сделать равной нулю. Если изначально есть скобка с одинаковыми символами ((a|a) или (!b|!b) например), то он может первым же ходом её занулить. Допустим что таких скобок нет. Если есть символ, который встречается с одинаковым знаком с двумя разными другими переменными ({(a|b)&(a|d)} или {(!a|x)&(!a|!x)} например), то Плад также победит занулив сначала этот символ в обоих скобках и вторым своим ходом занулит один из оставшихся символов (либо Жнри это сделает за Плада как во втором примере). В противном случае все символы разбиваются на пары и Жнри просто будет доделывать каждую скобку за Пладом до единицы. Это значит, что достаточно проверить существование первого хода Плада для которого при любом ходе Жнри он сможет его победить своим вторым ходом.

Задача D: Для каждого отрезка спроецируем его на прямую Ox найдя формулы для образов точек через подобие треугольников. После этого можно либо сделать scanline включая и выключая отрезки, либо отсортировать полученные проекции, объеденить в непересекающиеся и посчитать ответ. Важно считывать входные данные в целочисленные типы данных, потому что числа с плавающей точкой медленно считываются (ТЛ53).

Задача E: Считаем все запросы заранее и решим задачу оффлайн. Для каждого значения z запомним у каких запросов было это значение x == z и какие элементы массива a[i] == z. Создадим дерево отрезков на операцию ксора и проинициализируем его нулями. Пойдем по значениям z от 1 до 10^6. Для очередного z пройдем по всем i таким что a[i] == z и обновим в ДО tree.update(pos = i, val = a[i]). После этого ответим на все запросы с x == z просто запросом tree.get(l, r), потому что все элементы a[j] > x в нем сейчас занулены и ответ посчитается корректно.

Задача F: Так как массивы a[] и b[] равноправны, то предположим, что в a[] инверсий меньше чем в b[]. Заметим, что если в b[] есть хотя бы одна инверсия, то в нем найдется пара соседних элементов b[i] = 1 и b[i + 1] = 0. Если поменять их местами, то количество инверсий уменьшится на один, при этом переставление любой пары соседних элементов может изменить количество инверсий не более чем на один. Отсюда ответ это модуль разности количества инверсий в b[] и a[].

❤2🥰1

1.14K views16:04