Всем привет! Сегодня я сделал разбор задач, которые решил за сегодняшний день. Постараюсь сделать разбор ясным и кратким. Все задачи 1500 рейтинга и полезны для практики.
Идея решения: Обозначим f(x) — количество подмассивов с положительной суммой, если делаем индекс x положительным, а остальные остаются отрицательными.
Алгоритм:
- Перебираем индексы от n-1 до 1, находим такие, что сумма индексов равна k.
- Для этих индексов ставим положительные числа, остальные — -1.
- Считаем префиксные суммы, чтобы каждый элемент не был меньше префикса или суффикса.
- Если n > k, ставим a[k] = 1, остальные -1 и делаем аналогично.
Вывод: получаем массив, который гарантированно даёт сумму k.
Идея решения: Нужно определить, сколько прокрутов от x до 0 требуется.
Формула: (k * (k + 1) / 2 + x) % n == 0
Оптимизация: Так как каждые 2*n секторов цикл повторяется, достаточно рассматривать k от 1 до min(p, 2*n).
Идея решения: Последняя операция должна отсортировать массив: на первом месте — 1, на последнем — n, далее 2 и n-1 и так далее.
Алгоритм:
- Последняя операция: [1, n], предпоследняя: [2, n-1].
- Проверяем, отсортирован ли массив после операции, используя массив индексов pos[i] исходного массива.
- Если pos[i] <= pos[i+1] на отрезке, операция корректна.
- Для оптимизации используем бинарный поиск с границами l = 1, r = (n+1)/2 и ищем минимальный x, при котором операция проходит.
Вывод: получаем минимальный отрезок для сортировки.
Идея решения: Используем сегментное дерево.
Алгоритм:
- Если максимальный элемент на отрезке <= 9, пропускаем обновление (ничего не изменится).
- Храним массив mx[MXN] — максимальный элемент на отрезке для быстрого отслеживания условия.
- Если условие ложное, делаем апдейт на отрезке.
- Функция get возвращает a[pos].
Вывод: корректно обрабатываем обновления и запросы точки.
Идея решения: Эта задача требует очень много математики, которой у меня нет:) У нас есть p плюсов и m минусов. И значения а и б. Тогда мы выполняем какое то количество операции с плюсиком на элемент а и с минусиком с элементом а, назовем такие значения: k1, k2. Тогда для элемента б мы выполним (p-k1) операции с плюсом, и (m-k2) операции с минусом. Общая сумма должна быть равно 0, потому что так требует сама задача. Давайте так же обьявим total=p-m. То есть у нас останется как минимум total операции, чтобы сделать сумму нулевой. Так же пусть изначально k = k1-k2. Значит формула такая: (x*k1)-(x*k2)+(y*(p-k1)-y*(m-k2))= 0 Давайте упростим формулу: x(k1-k2)+y((p-k1)-(m-k2)) = 0 x(k1-k2)+y(p-k1-m+k2)=0 x(k1-k2)+y(p-m-k1+k2)=0 x(k1-k2)+y(total+(-k)) = 0 x(k) + y(total-k)=0 kx+totaly-ky=0 k(x-y)+total = 0 k(x-y) = -totaly k = -total*y/(x-y) k = (total*y)/(y-x) Так же определим границы, когда к может быть правдой. Минимальная граница: k = 0-m; Максимальная граница: k = p -0; Исходя из формулы граница у нас такая: [-m; p] Проверка:
- k должно быть целым числом.
- k должно быть в диапазоне [-m, p].
- Если total = 0, сразу ответ «Да».
- Если x = y, деление невозможно — ответ «Нет».
Вывод: проверяем формулу и границы — получаем решение задачи.
