Сегодня был 3 день интенсива Умника. На конкурсе я решил 4 задания — А, Ж, И, Н. И 1 задание было решено до конца — О.

Я оцениваю себя сегодня низко, так как я был неэффективен. В первой части конкурса я пропустил 2 простых задания — N и F. F было очень легко, но я боялся формулы в этой задаче.

На каждом шаге вы должны сначала найти и удалить i с d[i] ‹ k, а затем пересчитать это d[i]. Но если вы спокойно посмотрите на это уравнение, вы увидите, что вы можете перебирать i и пересчитывать это уравнение шаг за шагом за O(n).

Задача N также казалась сложной, потому что у вас есть 10⁵ ограничений такого типа:

Но, подумав пару минут, можно понять, что операция & очень полезна: вы получаете 1 только в том случае, если все аргументы равны 1. Это единственное, что вам нужно знать для решения этой задачи. O(n*30) раз. Легкий.

Заключение. ЕСЛИ ВЫ ВИДИТЕ В РАБОТЕ И В ПРОБЛЕМЕ — ЭТО МОЖЕТ БЫТЬ ОЧЕНЬ ЛЕГКО, КАК И ИМЕЕТ ОЧЕНЬ УДОБНОЕ СВОЙСТВО

Задача А была решена за 5 минут до окончания конкурса. Но я сделал подчинение в 1:15 от начала. У меня WA 9. Идея хорошая, но надо доработать. Задача: у вас есть функция f[X] = {d1, d2, …, dk}, где di — делители X. Если вы примените f к вектору чисел, он применит его к каждому числу. Вы должны применить эту операцию k ≤ 10¹⁸ раз. Каковы первые 10⁵ элементов результирующей последовательности?

Случай X = 1 тривиален. Результат всегда равен 1. Случай, когда X простое число, также тривиален. Результатом всегда будет 1, 1,..., 1, X. Но когда X не простое число, вы можете попытаться применить его напрямую. Итак, давайте эмулируем эту операцию прямо по определению f. Для каждого делителя f помните, что все его делители могут выполнять f. Сколько раз вы будете это делать? Давайте посмотрим на худший пример. Худший — самый медленный. Например, Х = 4.

k = 1: X = {1, 2, 4}

k = 2: X = {1, 1, 2, 1, 2, 4} + 3 к длине

k = 3: X = {1, 1, 1, 2, 1, 1, 2, 1, 2, 4} + 4 к длине

…

k = c: +=X = {1, 1, 1 …} + (c + 1) к длине

Итак, когда длина X будет равна 10⁵? Не более чем через √(10⁵) итераций. Хорошо, но нам нужно сделать k итераций. В моем первом представлении я забыл об этом и просто эмулировал f, пока длина X ‹ 10⁵, а затем распечатал результат. Да, я не очень умный. Следующая идея состоит в том, чтобы продолжить эмуляцию, пока X состоит только из простых чисел. Я не могу сделать какую-либо оценку, но я полагаю, что это также около O (√ (10⁵)) итераций. Поэтому, когда я остановился на X только с простыми числами и единицами, я должен посмотреть, что происходит дальше. Например:

1 1 2 1 1 3 ->

1 1 1 2 1 1 1 3 -> позиция 2 смещена на 1, 3 — на 2

1 1 1 1 2 1 1 1 1 3 -> позиция 2 сдвинута на 2, 3 — на 4

… -› позиция 2 смещена на k, 3 — на 2k и т. д.

Так что мне просто нужно применить некоторые сдвиги в O (10⁵), и все. AC (через множество глупых WA)

Следующие 2 проблемы - DP. Первый – это Я. У вас есть строка s размером ≤ 2000, t размером ≤ 500, для каждого количества возможных удалений символов s найдите максимальное количество непересекающиеся подстроки, равные t, которые можно найти в s после удаления. Напрямую dp[i ≤ n][j ≤ m][количество удалений] равно 2000*500*2000 с переходами O(1) в TL.

Поэтому я придумал dp[i≤n][j≤n] — минимальное количество удалений, где j — количество букв всех текущих фиксированных вхождений t. Переходы также O (1).

Решена вторая задача ДП О. У вас есть массив целых чисел. Разделите их на любое количество групп, в каждой группе найдите max — min и просуммируйте. Найдите максимальную сумму. п ≤ 10⁶. Так что речь должна идти о линейной сложности. Я придумал dp[n — префикс][2 — выбрал ли я максимум][2 — выбрал ли я минимум], поэтому dp[0][0] — начал новую группу, ничего не выбрал, dp[1][1] Я выбрал максимум и минимум, чтобы начать следующую группу. Получил переменный ток. Крутой ДП. Не тривиально.