В этой задаче нужно было понять, что ответ это максимум из a[i] - a[i - 1] - c, для i = 2..n и не забыть, что ответ не может быть отрицательным, так как медведь может не занимать в долг бочонок меда.
В этой задаче нужно было написать решение оптимальней наивного. Для этого, например, можно перебирать первым циклом левый индекс l рассматриваемой подстроки, а вторым циклом правый индекс r рассматриваемой подстроки (l ≤ r). Если на какой-то позиции i нашлась подстрока "bear", значит все подстроки x(l, j) (i ≤ j), также содержат "bear" в качестве подстроки. Значит к ответу можно сразу прибавить |s| - j + 1 и выйти из второго цикла. Также требовалось понять, что если в строке x(l, j) не было подстроки "bear", тогда в строке x(l, j + 1) подстрока "bear" могла появиться только в последних четырех символах.
385C - Медведь и простые числа
В этой задаче нужно было решить несколько подзадач:
1) Посчитать количество вхождений каждого числа от 2 до 107 в данный в задаче набор чисел. Это можно делать быстро так. Завести массив count на 107 элементов и при считывании чисел прибавлять count[x]++.
2) Теперь научимся считать f(x).
Для начала нужно найти все простые числа до 107 и посчитать для каждого простого числа — f(x).
Как посчитать f(2)? Нужно сложить count[2],count[4],count[6],count[8],...
Как посчитать f(5)? Нужно сложить count[5],count[10],count[15],count[20],...
Как посчитать f(x)? Нужно сложить count[x],count[2·x],count[3·x],count[4·x],...
Можно заметить похожесть на алгоритм решета Эратосфена http://e-maxx.ru/algo/eratosthenes_sieve и немного видоизменить его. Также будем сохранять в массиве pre результаты этих вычислений. А именно pre[x] = f(x).
3) Теперь можно посчитать префиксные суммы на массиве pre. Это делается одним проходом слева направо, прибавляя pre[i - 1] к pre[i].
4) Зная префиксные суммы, можно отвечать за O(1) на запрос [l, r]. Это делается так pre[r] - pre[l - 1].
5) Теперь можно считывать запросы и сразу отвечать на них. При этом не стоит забывать, что правая граница в запросе может быть до 2·109, поэтому правую границу можно всегда уменьшать до 107, так как бОльших чисел в изначальном массиве все равно нет.
В этой задаче нужно было понять, что если дорога уже освещена расстоянием в dist, то следующим прожектором оптимально освещать так, чтобы левая точка освещения на оси X была равна l + dist.
Предположим, что сейчас дорога освещена с l до d. Как теперь найти самую правую точку на оси X, которая будет освещена следующим прожектором?
Для этого достаточно использовать понятие вектора и матрицы поворота.
Находим вектор (dx, dy) от прожектора до точки (d, 0). (dx, dy) = (d - x, 0 - y).
Далее этот вектор нужно повернуть на angle градусов. Для этого можно использовать матрицу поворота.
(dx, dy) = (dx·cos(angle) - dy·sin(angle), dx·sin(angle) + dy·cos(angle))
Далее этот вектор нужно домножить на k таким образом, чтобы dy стал равен единице.
Ну и теперь можно определить самую правую освещенную точку на оси X. Она равна x - y·dx.
Также не стоит забывать, что правая точка может находится где-то в бесконечности.
На этом геометрия в этой задаче закончилась.
Теперь нужно научиться быстро находить оптимальный порядок прожекторов.
Для этого стоит применить подход динамического программирования. А именно, хранить ответ для масок прожекторов.
dp[i] = оптимальный ответ для такой-то маски i. Обычно под масками подразумевают целое число, в строковой бинарной записи числа которого, стоят 0 и 1. Допустим на 2 позиции стоит 1 — это означает, что 2 прожектор уже был использован. Например, dp[6] — (6 — 1102) оптимальный ответ, если уже использованы 2 и 3 прожектора.
Идея теперь такая. Перебираем маски в динамике dp[i]. Перебираем в i маске неиспользованные прожекторы j и обновляем ответ для маски, где этот прожектор уже используется — dp[ i or 2j ] = max( dp[ i or 2j ], dp[ i ] + вычисление_самой_правой_точки()). Так как мы уже знаем как находить самую правую освещенную точку, то обновление ответа для новой маски не составит труда.
В этой задаче можно было заметить несколько вещей:
1) Заметить, что решение моделированием не проходит по времени, так как t ≤ 1018.
2) Далее можно убедиться, что задачу не решить отдельно по x и отдельно по y, так как x и y зависят друг от друга при вычислениях.
3) Также не проходит достаточно стандартный метод с поиском цикла (то есть мы попадаем в тоже самое состояние через некоторый небольшой промежуток времени). Такого может не произойти долгое время, так как ограничения на координаты большие.
Как тогда решать.
Пусть у нас есть матрица (xi, yi, dxi, dyi, ti, 1).
Умножив ее на такую матрицу long long base[6][6] = {
{2,1,1,1,0,0},
{1,2,1,1,0,0},
{1,0,1,0,0,0},
{0,1,0,1,0,0},
{0,0,1,1,1,0},
{0,0,2,2,1,1} };
мы получим значения на следующем шаге.
Откуда взялась эта матрица? Давайте распишем как меняются параметры с каждым шагом и увидим похожесть на матрицу.
x = 2·x + 1·y + 1·dx + 0·dy + 0·t + 0·1.
y = 1·x + 2·y + 0·dx + 1·dy + 0·t + 0·1.
dx = 1·x + 1·y + 1·dx + 0·dy + 1·t + 2·1.
dy = 1·x + 1·y + 0·dx + 1·dy + 1·t + 2·1.
t = 0·x + 0·y + 0·dx + 0·dy + 1·t + 1·1.
1 = 0·x + 0·y + 0·dx + 0·dy + 0·t + 1·1.
Таким образом, возведя матрицу base в степень t - 1, и потом умножив матрицу (sx, sy, dx, dy, t, 1) на base, получим значения в момент времени t.
Матрицу можно возводить в степень быстро по принципу быстрого возведения в степень по модулю. http://e-maxx.ru/algo/binary_pow
Перемножаются матрицы за куб. Итоговое количество операций 63·log(t)
