Разборы•6 дней назад

Educational Round #4 — Разборы

Вы собираетесь поджарить несколько тостов для предстоящей вечеринки. У вас есть сковорода, на которой одновременно можно жарить не более $k$ тостов. Поджаривание одной стороны тоста занимает $2$ минуты.

Предположим, что размещение тоста на сковороде, его переворачивание и снятие происходят мгновенно.

Напишите программу, которая определяет минимальное количество минут, необходимое для поджаривания $n$ тостов. Каждый тост должен быть поджарен с обеих сторон. Тосты нельзя снимать со сковороды раньше или позже $2$ минут, нужных для прожарки одной стороны.

Вход. Два целых числа $n$ и $k (0 \leq n \leq 1000, 1 \leq k \leq 50)$ — количество тостов и вместимость сковороды (в тостах).

Выход. Выведите минимальное время в минутах, необходимое для поджаривания всех $n$ тостов.

Открыть задачу

Если $n = 0$ , то ответ $0$ .

Если количество тостов $n$ не превышает вместимость сковороды $k (n \leq k)$ , то на поджаривание всех тостов с двух сторон потребуется $4$ минуты.

Так как каждый тост нужно поджарить с обеих сторон, всего требуется $⌈ 2 n / k ⌉$ прожарок. Каждая прожарка (одновременное расположение на сковороде до $k$ тостов) занимает $2$ минуты.

Следовательно, если $n > k$ , то минимальное время, необходимое для поджаривания всех тостов, равно $2 \cdot ⌈ 2 n / k ⌉$ минут.

Пример

Пусть имеется $n = 3$ тоста, и сковорода вмещает одновременно $k = 2$ тоста. Обозначим стороны тостов как $1 a, 1 b, 2 a, 2 b, 3 a, 3 b$ .

Тогда все $6$ сторон можно поджарить за $6$ минут следующим образом:

Первая прожарка: $1 a$ и $2 a - 2$ минуты;
Вторая прожарка: $1 b$ и $3 a - 2$ минуты;
Третья прожарка: $2 b$ и $3 b - 2$ минуты;

Итого: $3$ прожарки по $2$ минуты, то есть $6$ минут.

Читаем входные данные.

scanf("%d %d",&n,&k);

Если $n = 0$ , то ответ $0$ .

if (!n) res = 0; else

Если количество тостов не превышает вместимость сковороды, то на их поджаривание потребуется $4$ минуты.

if (n <= k) res = 4; else
{

Каждый тост необходимо поджарить с двух сторон, то есть всего нужно прожарить $⌈ 2 n / k ⌉$ сторон. При этом одна прожарка (независимо от количества тостов на сковороде, не превышающего её вместимость) занимает $2$ минуты.

  res = 2 * n / k;
  if (2 * n % k) res++;
  res *= 2;
}

Выводим ответ.

printf("%d\n",res);

В классе ADA School расположены $n \times m$ парт, образующих прямоугольную сетку из $n$ строк и $m$ столбцов. Каждая парта занята ровно одним учеником.

Перед началом занятия учитель решил немного перетасовать учеников. После перестановки должны быть выполнены два условия:

Каждый стол снова должен быть занят ровно одним учеником.
Каждый ученик должен пересесть за стол, примыкающий к его исходному месту, то есть расположенный непосредственно слева, справа, сверху или снизу.

Можно ли выполнить перестановку учеников, соблюдая оба условия?

Вход. Первая строка содержит количество тестов $t$ . Каждая из следующих $t$ строк содержит два целых числа $n$ и $m (2 \leq n, m \leq 1000)$ .

Выход. Для каждого теста выведите "YES", если перестановку учеников можно выполнить, и "NO" в противном случае.

Открыть задачу

Рассмотрим случай, когда одна из размерностей сетки четная. Пусть, например, $n$ (количество строк) — четное. В этом случае перестановку учеников можно выполнить следующим образом:

Если $n$ и $m$ нечётные, то выполнить перестановку невозможно.

Рассмотрим сетку, раскрашенную в шахматном порядке: одни клетки — белые, другие — чёрные. При перемещении парта, стоявшая на чёрной клетке, должна перейти на белую, и наоборот. Чтобы перестановка всех парт была возможна, количество белых и чёрных клеток должно быть одинаковым. Следовательно, общее число парт должно быть чётным.

Однако при нечётных $n$ и $m$ общее количество парт $n \times m$ является нечётным числом, что делает перестановку невозможной.

Агент Джонни Инглиш снова в деле!

На этот раз бесстрашному агенту и его помощнику Бофу поручено проследить за порядком на благотворительном мероприятии. Войдя в зал и осмотревшись, Инглиш понял, что для полной картины происходящего ему придётся немного прогуляться по залу, перекинуться парой слов с гостями и понаблюдать за официантами. Закончив разведку, Инглиш, уверенный в успехе, решил встретиться с Бофом и блеснуть перед ним своими невероятными аналитическими способностями. К сожалению, бедняга Боф на светских мероприятиях совершенно теряется, поэтому просто медленно следует за указаниями старшего агента.

Зал представляет собой квадрат на координатной плоскости со сторонами длиной $1 0^{6}$ , параллельными координатным осям. Вход находится в левом нижнем углу квадрата, в точке $O (0, 0)$ . Агент Инглиш собирается выбрать несколько гостей, расположенных в точках с целыми координатами, и поздороваться с каждым по очереди. Он не будет здороваться с одним и тем же гостем подряд, но иногда может ошибиться и вернуться к гостю, с которым уже здоровался. Тренированный агент движется со скоростью $p$ , а здоровается с гостями мгновенно. В это время Боф, двигаясь со скоростью $q$ , направляется напрямую к финальной точке маршрута, намеченного Инглишем.

Чтобы не вызывать подозрений, агент Инглиш хочет найти такой маршрут, при котором они с Бофом прибудут в точку встречи одновременно. К сожалению, у агента нет времени продумывать детали своего гениального плана, поэтому этим предстоит заняться Вам.

По заданным скоростям $q$ и $p$ найдите любой маршрут, начинающийся в точке $(0, 0)$ и состоящий из точек с неотрицательными координатами, не превосходящими $1 0^{6}$ . При этом время прохождения маршрута со скоростью $q$ должно совпадать с временем прохождения того же маршрута со скоростью $p$ .

Вход. В одной строке заданы два натуральных числа $q$ и $p (1 \leq q \leq p \leq 1 0^{5})$ — скорости Бофа и агента Инглиша соответственно.

Выход. В первой строке выведите число $n (2 \leq n \leq 100)$ — количество точек в маршруте. В следующих $n$ строках выведите пары целых чисел $x$ и $y (0 \leq x, y \leq 1 0^{6})$ — координаты точек в порядке обхода. Первой обязательно должна быть выведена точка $(0, 0)$ . Точки могут повторяться, однако в маршруте не должно быть двух одинаковых точек подряд.

Открыть задачу

Джонни Инглиш и Боф достигают конечной точки одновременно за время $t$ . Джонни Инглиш преодолевает расстояние $s_{1} = p \cdot t$ , а Боф $s_{2} = q \cdot t$ . Отношение пройденных расстояний равно отношению скоростей: $s_{1} / s_{2} = p / q$ .

Построим такие пути конструктивно. Рассмотрим, например, маршрут из $4$ точек: $(0, 0) \to (2 q, 0) \to (2 q, p - q) \to (2 q, 0)$ . Здесь выбрана координата $p - q$ , чтобы ее значение было неотрицательным (по условию задачи $q \leq p$ ).

Длина пути Джонни Инглиша равна $2 q + 2 * (p - q) = 2 p$ .
Длина пути Бофа равна $2 q$ .

Если скорости Джонни Инглиша и Бофа одинаковы, то точки $(2 q, 0)$ и $(2 q, p - q)$ совпадают, а по условию задачи на маршруте не может быть двух одинаковых точек подряд. В этом случае в качестве решения можно выбрать, например, следующий маршрут: $(0, 0) \to (1, 0)$ .

Фермер Джон не умеет выполнять несколько задач одновременно. Он часто отвлекается, что затрудняет работу над долгосрочными проектами. Сейчас он пытается покрасить одну сторону своего коровника, но постоянно отвлекается на уход за коровами. В результате некоторые участки стены покрываются краской в несколько слоев, тогда как другие остаются менее окрашенными.

Сторону коровника можно представить в виде двумерной плоскости размером $x \times y$ , где фермер Джон последовательно наносит краску в виде $n$ прямоугольных областей со сторонами, параллельными осям координат. Каждый прямоугольник задается координатами его нижнего левого и верхнего правого углов.

Фермер Джон хочет добиться равномерного покрытия стены, чтобы в ближайшее время не пришлось её перекрашивать. Однако он также не хочет тратить лишнюю краску. Оптимальным количеством слоев считается $k$ . Ваша задача — определить площадь участка стены, который покрыт ровно k слоями краски после нанесения всех прямоугольников.

Вход. Первая строка содержит два целых числа $n$ и $k (1 \leq k \leq n \leq 1 0^{5})$ — количество прямоугольников и требуемое число слоев покрытия.

Каждая из следующих $n$ строк содержит четыре целых числа $x_{1}, y_{1}, x_{2}, y_{2}$ , задающих прямоугольник с нижним левым углом в точке $(x_{1}, y_{1})$ и верхним правым углом в точке $(x_{2}, y_{2})$ .

Все координаты $x$ и $y$ находятся в диапазоне от $0$ до $1000$ . Все заданные прямоугольники имеют положительную площадь.

Выход. Выведите одно число — площадь участка стены, покрытого ровно $k$ слоями краски.

Открыть задачу

Сначала рассмотрим одномерный вариант задачи. Пусть на числовой прямой задано $n$ отрезков $[a_{i}, b_{i}]$ , где $0 \leq a_{i}, b_{i} \leq 1000$ . Необходимо определить, сколькими отрезками покрывается каждое целое число на этой прямой.

Объявим целочисленный массив $d p$ , инициализируем его нулями. Затем для каждого отрезка $[a_{i}, b_{i}]$ выполним две операции:

d p [a_{i}] + +; d p [b_{i} + 1] - -;

Далее вычислим префиксные суммы в массиве $d p$ . Значение $d p [i]$ равно количеству отрезков, содержащих число $i$ .

Например, пусть даны следующие отрезки: $[3; 7], [6; 9], [1; 4], [3; 8], [2; 5]$ . Инициализируем массив $d p$ :

Для каждого отрезка $[a_{i}, b_{i}]$ выполним две операции: $d p [a_{i}] + +; d p [b_{i} + 1] - -$ .

Теперь рассмотрим двумерный вариант задачи. На плоскости задано $n$ прямоугольников с координатами $(x_{1}, y_{1}) - (x_{2}, y_{2}) (0 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 1000)$ . Требуется определить, сколькими прямоугольниками покрывается каждая клетка плоскости.

Объявим целочисленный двумерный массив $d p$ , инициализируем его нулями. Затем для каждого прямоугольника $(x_{1}, y_{1}) - (x_{2}, y_{2})$ выполним четыре операции:

d p [x_{1}] [y_{1}] + +; d p [x_{1}] [y_{2} + 1] - -; d p [x_{2} + 1] [y_{1}] - -; d p [x_{2} + 1] [y_{2} + 1] + +;

После этого вычислим префиксные суммы в массиве $d p$ . Значение $d p [i] [j]$ будет равно числу прямоугольников, содержащих клетку $(i, j)$ .

Рассмотрим, например, прямоугольник $(2, 2) - (4, 5)$ .

Пример

Рассмотрим приведенный пример, содержащий три прямоугольника.

$k = 2$ слоями краски покрыто $8$ квадратов.

Объявим двумерный массив $d p$ .

#define MAX 1001
int dp[MAX][MAX];

Читаем входные данные.

scanf("%d %d", &n, &k);
while (n--)
{

Для каждого прямоугольника $(a, b) - (c, d)$ выполним четыре операции.

  scanf("%d %d %d %d", &a, &b, &c, &d);
  dp[a][b]++;
  dp[a][d]--;
  dp[c][b]--;
  dp[c][d]++;
}

В переменной $res$ подсчитываем количество клеток стены, покрытых ровно $k$ слоями краски.

res = 0;

Вычисляем префиксные суммы в массиве $d p$ .

for (i = 0; i < MAX; i++)
  for (j = 0; j < MAX; j++)
  {
    if (i) dp[i][j] += dp[i - 1][j];
    if (j) dp[i][j] += dp[i][j - 1];
    if (i && j) dp[i][j] -= dp[i - 1][j - 1];

Если клетка $(i, j)$ покрыта $k$ слоями краски, то увеличиваем $res$ на $1$ ,

    if (dp[i][j] == k) res++;
  }

Выводим ответ.

printf("%d\n", res);

Разделение строки называется палиндромным разбиением, если каждая подстрока в этом разбиении является палиндромом. Например, строка "ababbbabbababa" может быть разделена как "aba|b|bbabb|a|b|aba" — это пример палиндромного разбиения.

Определите наименьшее количество разрезов, необходимых для палиндромного разбиения заданной строки. Например:

для строки " $ababbbabbababa$ " требуется минимум $3$ разреза, которые образуют разбиение " $a ∣ babbbab ∣ b ∣ ababa$ ";
если строка уже является палиндромом, то потребуется $0$ разрезов;
если все символы строки длины n различны, то минимальное количество разрезов равно $n - 1$ .

Вход. Одна строка $s$ длины не более $1000$ .

Выход. Выведите минимальное количество разрезов, необходимых для палиндромного разбиения строки $s$ .

Открыть задачу

Пусть $s$ — входная строка. Подстрока $s_{i} ... s_{j}$ является палиндромом, если выполняется одно из следующих условий:

$i \geq j$ (подстрока пустая или состоит из одного символа);
$s_{i} = s_{j}$ и подстрока $s_{i + 1} ... s_{j - 1}$ является палиндромом;

Пусть функция $I s P a l (i, j)$ возвращает $1$ , если $s_{i} ... s_{j}$ является палиндромом, и $0$ в противном случае. Значения $I s P a l (i, j)$ сохраняем в ячейках $p a l [i] [j]$ .

Пусть функция $f (i, j)$ возвращает минимальное количество разрезов, необходимых для палиндромного разбиения строки $s_{i} ... s_{j}$ . Значения этой функции будем сохранять в ячейках массива $d p [i] [j]$ . Тогда ответом на задачу будет значение $f (0, s . s i ze () - 1)$ .

Отметим, что $f (i, i) = 0$ , так как строка из одной буквы уже является палиндромом.

Для вычисления $f (i, j)$ разрежем подстроку $s_{i} ... s_{j}$ на две части: $s_{i} ... s_{k}$ и $s_{k + 1} ... s_{j} (i \leq k < j)$ . Рекурсивно решаем задачи на строках $s_{i} ... s_{k}$ и $s_{k + 1} ... s_{j}$ . Ищем такое значение $k (i \leq k < j)$ , для которого сумма $f (i, k) + f (k + 1, j) + 1$ будет минимальной. Слагаемое $1$ в сумме означает, что мы совершаем один разрез между символами $s_{k}$ и $s_{k + 1}$ . Таким образом, получаем следующее рекуррентное соотношение:

f (i, j) = i \leq k < j min (f (i, k) + f (k + 1, j) + 1)

Пример

Например, для строки " $abab cc b$ " из $7$ символов имеем:

f (1, 7) = 1 \leq k < 7 min (f (1, k) + f (k + 1, 7) + 1)

Сумма принимает наименьшее значения при $k = 3$ :

f (1, 7) = f (1, 3) + f (4, 7) + 1 = 0 + 0 + 1 = 1

Так как строки " $aba$ " и " $b cc b$ " являются палиндромами, то $f (1, 3) = f (4, 7) = 0$ .

Объявим константы, входную строку $s$ и рабочие массивы.

#define MAX 1001
#define INF 0x3F3F3F3F
int dp[MAX][MAX], pal[MAX][MAX];
string s;

Функция $I s P a l (i, j)$ проверяет, является ли подстрока $s_{i} ... s_{j}$ палиндромом. Подстрока $s_{i} ... s_{j}$ является палиндромом, если $s_{i} = s_{j}$ и $s_{i + 1} ... s_{j - 1}$ является палиндромом. Значения $I s P a l (i, j)$ сохраняем в ячейках массива $p a l [i] [j]$ .

int IsPal(int i, int j)
{
  if (i >= j) return pal[i][j] = 1;
  if (pal[i][j] != -1) return pal[i][j];
  return pal[i][j] = (s[i] == s[j]) && IsPal(i + 1, j - 1);
}

Функция $f (i, j)$ возвращает минимальное количество разрезов, необходимых для палиндромного разбиения подстроки $s_{i} ... s_{j}$ .

int f(int i, int j)
{

Если $i = j$ , подстрока $s_{i} ... s_{j}$ состоит из одного символа, и резать её нет смысла. Если $i > j$ , подстрока $s_{i} ... s_{j}$ считается пустой, и разрезы также не требуются.

  if (i >= j) return 0;

Если значение $f (i, j)$ уже было вычислено ранее, возвращаем сохранённое значение из массива $d p [i] [j]$ .

  if (dp[i][j] != INF) return dp[i][j];

Если подстрока $s_{i} ... s_{j} (i < j)$ является палиндромом, то резать ее смысла нет. В этом случае минимальное количество разрезов равно $0$ .

  if (IsPal(i, j)) return dp[i][j] = 0;

Разрежем подстроку $s_{i} ... s_{j}$ на две части: $s_{i} ... s_{k} (i \leq k)$ и $s_{k + 1} ... s_{j} (k + 1 \leq j)$ . Далее рекурсивно решаем задачи для обеих частей: $s_{i} ... s_{k}$ и $s_{k + 1} ... s_{j}$ . Ищем такое значение $k (i \leq k < j)$ , для которого сумма $f (i, k) + f (k + 1, j) + 1$ наименьшая.

  for (int k = i; k < j; k++)
    dp[i][j] = min(dp[i][j], f(i, k) + f(k + 1, j) + 1);

Возвращаем ответ $d p [i] [j] = f (i, j)$ .

  return dp[i][j];
}

Основная часть программы. Читаем входную строку.

cin >> s;

Инициализируем массивы.

memset(dp, 0x3F, sizeof(dp));
memset(pal, -1, sizeof(pal));

Вычисляем и выводим ответ.

res = f(0, s.size() - 1);
cout << res << endl;

Заданы $n$ зданий с высотами $h_{1}, h_{2}, \dots, h_{n}$ . Сделайте так, чтобы все здания имели одинаковую высоту. Для этого разрешается как удалять кирпичи из зданий, так и добавлять их. Каждое добавление или удаление одного кирпича требует определённой платы, которая задаётся для каждого здания отдельно.

Найдите минимальную общую стоимость реконструкции, при которой все здания будут иметь одинаковую высоту $k$ (где $k$ — любое целое неотрицательное число), то есть выполняется условие $h_{1} = h_{2} = ... = h_{n} = k$ .

Для простоты будем считать, что каждое здание представляет собой вертикальную колонну из одинаковых кирпичей.

Вход. Первая строка содержит одно целое число $n (n \leq 1 0^{5})$ — количество зданий.

Вторая строка содержит $n$ целых чисел — высоты зданий $h_{1}, h_{2}, \dots, h_{n} (0 \leq h_{i} \leq 1 0^{4})$ .

Третья строка содержит $n$ целых чисел $c_{1}, c_{2}, \dots, c_{n} (0 \leq c_{i} \leq 1 0^{4})$ — стоимость добавления или удаления одного кирпича для соответствующего здания.

Выход. Выведите одно целое число — минимальную суммарную стоимость, за которую все здания можно сделать одинаковой высоты.

Открыть задачу

Отсортируем здания по их высотам так, чтобы выполнялось неравенство: $h_{1} \leq h_{2} \leq ... \leq h_{n}$ . Если несколько зданий имеют одинаковую высоту, упорядочим их дополнительно по возрастанию стоимости добавления или удаления кирпича.

Рассмотрим стоимость, необходимую для того, чтобы привести все здания к высоте $h_{x} (1 \leq x \leq n)$ . Она равна

f (x) = i = 1 \sum n ∣ h_{i} - h_{x} ∣ \cdot c_{i}

Функция $f (x)$ , описывающая эту стоимость, является вогнутой и имеет глобальный минимум, который можно найти с помощью тернарного поиска.

Пример

Рассмотрим первый пример. Отсортируем здания по их высотам:

Найдём значения функции $f (x)$ для всех возможных высот зданий:

$f (1) = (1 - 1) \cdot 30 + (2 - 1) \cdot 10 + (3 - 1) \cdot 20 + (4 - 1) \cdot 40 = 170$ ,
$f (2) = (2 - 1) \cdot 30 + (2 - 2) \cdot 10 + (3 - 2) \cdot 20 + (4 - 2) \cdot 40 = 130$ ,
$f (3) = (3 - 1) \cdot 30 + (3 - 2) \cdot 10 + (3 - 3) \cdot 20 + (4 - 3) \cdot 40 = 110$ ,
$f (4) = (4 - 1) \cdot 30 + (4 - 2) \cdot 10 + (4 - 3) \cdot 20 + (4 - 4) \cdot 40 = 130$

Минимальное значение функции $f (x)$ достигается при $x = 3$ ; в этом случае $f (3) = 110$ .

Каждое здание имеет высоту $h$ и стоимость $cos t$ добавления или удаления одного этажа. Информация о зданиях хранится в массиве $b$ .

#define MAX 100001
struct Building
{
  int h, cost;
};
Building b[MAX];

Функция cmp является компаратором для сортировки зданий. Сначала здания сортируются по возрастанию высоты, а при равных высотах — по возрастанию стоимости.

int cmp(Building a, Building b)
{
  if (a.h == b.h)
    return a.cost < b.cost;
  return a.h < b.h;
}

Функция f вычисляет стоимость, необходимую для того, чтобы сделать все постройки одинаковой высоты с высотой здания номер $x$ .

long long f(int x)
{
  long long ret = 0;
  for (int i = 1; i <= n; i++)
    ret += 1LL * abs(b[x].h - b[i].h) * b[i].cost;
  return ret;
}

Функция ternary_search при помощи тернарного поиска ищет такое значение $x \in [l e f t; r i g h t]$ , при котором $f (x)$ минимально. Изначально границы диапазона заданы как $[l e f t; r i g h t] = [1; n]$ .

long long ternarySearch(int left, int right)
{
  while (right - left >= 3)
  {
    int a = left + (right - left) / 3;
    int b = left + 2 * (right - left) / 3;
    if (f(a) > f(b))
      left = a;
    else
     right = b;
  }

Разность между $l e f t$ и $r i g h t$ не превышает $3$ . В этом случае минимальное значение $f (x)$ на отрезке $[l e f t; r i g h t]$ находим полным перебором.

  long long res = f(left++);
  while (left <= right)
    res = min(res, f(left++));
  return res;
}

Основная часть программы. Читаем входные данные.

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].h);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].cost);

Сортируем здания.

sort(b + 1, b + n + 1, cmp);

Вычисляем и выводим ответ. Здания нумеруются от $1$ до $n$ .

printf("%lld\n", ternarySearch(1, n));

С домино можно придумать множество развлечений. Например, дети любят выстраивать костяшки домино в линию, располагая их рядом друг с другом. Если толкнуть одну костяшку, она упадет и собьет соседнюю, та, в свою очередь, собьет следующую, и так далее, пока цепная реакция не прекратится. Однако могут существовать такие расстановки, при которых не все костяшки упадут. В этом случае необходимо дополнительно толкнуть еще одну костяшку, чтобы цепная реакция продолжилась.

По заданной расстановке домино определите минимальное количество костяшек, которые необходимо толкнуть рукой, чтобы все домино упали.

Вход. Первая строка содержит два целых числа $n$ и $m (1 \leq n, m \leq 1 0^{5})$ , где $n$ — количество костяшек домино, а $m$ — количество строк, описывающих их взаимодействие. Костяшки пронумерованы числами от $1$ до $n$ .

Каждая из следующих $m$ строк содержит два числа $x$ и $y$ , которые означают, что если костяшка с номером $x$ упадет, то она собьет костяшку с номером $y$ .

Выход. Выведите одно число — минимальное количество костяшек, которые нужно толкнуть, чтобы все домино упали.

Открыть задачу

Рассмотрим задачу нахождения сильных компонент связности в ориентированном графе. Каждую вершину графа из одной сильно связной компоненты окрасим в один и тот же цвет. Пусть $co l or [i]$ обозначает цвет $i$ -й вершины. Число различных цветов окраски будет равно числу компонент сильной связности.

Очевидно, что если толкнуть одну костяшку домино, то обязательно упадут все костяшки, принадлежащие той же сильной компоненте связности. Обозначим через $c n t$ количество сильных компонент связности.

Объявим массив $u se d$ длины $c n t$ , где $u se d [i] = 1$ , если необходимо толкнуть домино из $i$ -й компоненты связности. Теперь определим, для каких значений $u se d [i]$ следует установить равным $0$ .

Переберем все ребра графа. Нас интересуют только те ребра, которые соединяют разные компоненты связности. Если такое ребро имеет вид $i \to j$ (где $co l or [i] \neq = co l or [j]$ ), то установим $u se d [co l or [j]] = 0$ . Это означает, что нет необходимости толкать домино из компоненты цвета $co l or [j]$ , так как, толкнув домино из компоненты цвета $co l or [i]$ , мы гарантированно столкнем все домино из компоненты цвета $co l or [j]$ .

После обработки всех ребер остается подсчитать количество единиц в массиве $u se d$ . Это и будет минимальное количество костяшек, которые следует толкнуть.

Пример

Графы, приведенные в примерах, имеют следующий вид:

В первом примере достаточно столкнуть домино номер $1$ .
Во втором примере необходимо столкнуть домино с номерами $1$ и $5$ .

Граф из первого примера имеет $3$ сильно связные компоненты.

поскольку существует ребро $(1, 2)$ , нет необходимости толкать домино номер $2$ ;
поскольку существует ребро $(2, 3)$ , нет необходимости толкать домино номер $3$ ;

Входной граф храним в списке смежности $g$ .

Обратный граф (граф, в котором изменены все направления ребер) храним списке смежности $g r$ .

vector<vector<int> > g, gr;
vector<int> used, top, color;

Функция dfs1 выполняет поиск в глубину на входном графе. В массив $t o p$ заносим вершины в порядке завершения их обработки в процессе поиска в глубину.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

Функция dfs2 выполняет поиск в глубину на обратном графе. Все вершины, которые посещаются в ходе рекурсивного вызова функции $df s 2$ , принадлежат одной компоненте сильной связности. Каждую из таких вершин окрашиваем в цвет $c$ .

void dfs2(int v, int c)
{
  color[v] = c;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, c);
}

Основная часть программы. Читаем входные данные. Строим обратный граф.

scanf("%d %d",&n,&m);
g.resize(n+1);
gr.resize(n+1);
cnt = 0;
for(i = 0; i < m; i++)
{
  scanf("%d %d",&a,&b);
  g[a].push_back(b); 
  gr[b].push_back(a);
}

Запускаем поиск в глубину на входном графе. Порядок завершения обработки вершин сохраняем в массиве $t o p$ .

used.resize(n+1);
for(i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

Затем выполняем поиск в глубину на обратном графе. Вершины обратного графа обрабатываются в порядке, в котором они находятся в массиве $t o p$ , начиная с конца (справа налево). Вершины, принадлежащие одной компоненте сильной связности, окрашиваются в один цвет. Текущий цвет раскраски содержится в переменной $c$ .

Для удобства дальнейшей обработки обернем массив $t o p$ , после чего будем обрабатывать вершины в нем слева направо.

color.assign(n+1,-1);
reverse(top.begin(), top.end());
c = 0;
for (int v : top)
  if (color[v] == -1) dfs2(v, c++);

Переменная $c$ содержит количество компонент сильной связности.

used.assign(c,1);
for (i = 1; i < g.size(); i++)
  for (int to : g[i])

Перебираем все ребра графа $(i, t o)$ . Проверяем, находятся ли вершины $i$ и $t o$ в разных сильно связных компонентах. Это так, если они окрашены в разные цвета. В таком случае, если столкнуть любое домино из компоненты сильной связности, которой принадлежит вершина $i$ , то обязательно упадет и домино $t o$ . Это означает, что нет смысла сталкивать домино цвета $co l or [t o]$ . Поэтому устанавливаем $u se d [co l or [t o]] = 0$ .

    if (color[i] != color[to]) used[color[to]] = 0;

В переменной $c$ подсчитываем количество домино, которые следует столкнуть. Если для какого-либо цвета $i$ выполняется условие $u se d [i] = 1$ , это означает, что никакое домино цвета $i$ не упадет, независимо от того, какое домино другого цвета мы столкнем. В этом случае обязательно придется столкнуть хотя бы одно домино цвета $i$ .

c = 0;
for(i = 0; i < used.size(); i++)
  if (used[i]) c++;

Выводим ответ.

printf("%d\n",c);

Задан ориентированный граф $G$ с $n$ вершинами и $m$ ребрами. Вершины пронумерованы от $1$ до $n$ . Для каждого $i (1 \leq i \leq m)$ задано направленное ребро из вершины $x_{i}$ в вершину $у_{i}$ .

Граф $G$ не содержит направленных циклов.

Найдите длину самого длинного направленного пути в $G$ . Под длиной пути понимается количество рёбер в этом пути.

Вход. Первая строка содержит два целых числа: количество вершин $n (2 \leq n \leq 1 0^{5})$ и количество ребер $m (1 \leq m \leq 1 0^{5})$ графа. Каждая из следующих $m$ строк содержит два целых числа $x_{i}, y_{i} (1 \leq x_{i}, y_{i} \leq n)$ , описывающих ориентированное ребро из вершины $x_{i}$ в вершину $у_{i}$ .

Выход. Выведите длину самого длинного направленного пути в графе $G$ .

Открыть задачу

Найдем топологическую сортировку графа. Обозначим через $d p [u]$ максимальное количество городов, которое можно посетить по пути, начиная из вершины $u$ .

Рассмотрим вершины в порядке топологической сортировки. Пусть $u$ — текущая вершина. Обозначим через $v_{1}, v_{2}, ..., v_{k}$ вершины, в которые ведут ребра из $u$ . Тогда обновим значение:

d p [u] = ma x (d p [v_{i}] + 1), 1 \leq i \leq k

Изначально установим $d p [u] = 0 (1 \leq u \leq n)$ .

После обработки всех вершин находим наибольшее значение в массиве $d p$ . Оно равно длине максимального пути в графе.

Пример

Слева приведен граф из первого примера. Справа — из второго. Самые длинные пути выделены.

В первом примере самый длинный путь равен $d p_{1} = 3$ .

Во втором примере самый длинный путь равен $d p_{4} = 2$ .

Объявим список смежности графа $g$ .

vector<vector<int> > g;

Функция dfs выполняет поиск в глубину, начиная с вершины $v$ . Сортируем вершины графа топологически и записываем их в массив $t o p$ .

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (used[to] == 0) dfs(to);
  top.push_back(v);
}

Основная часть программы. Читаем входные данные. Строим список смежности ориентированного графа.

scanf("%d %d", &n, &m);
g.resize(n + 1);
while (m--)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
}

Запускаем поиск в глубину на несвязном графе.

used.resize(n + 1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Перебираем вершины графа в порядке, обратном их топологической сортировке, то есть перебираем вершины массива $t o p$ слева направо.

dp.resize(n + 1);
for (int u : top)
{

Путь из вершины $u$ в саму себя имеет длину $0$ (инициализация).

  dp[u] = 0;

Перебираем вершины $v$ , смежные с $u$ . Рассматриваем ребро $(u, v)$ .

  for (int v : g[u])

Для всех таких вершин $v$ ищем максимум среди значений $d p [v] + 1$ .

    dp[u] = max(dp[u], dp[v] + 1);
}

Находим и выводим наибольший элемент в массиве $d p$ . Он соответствует длине самого длинного пути в графе.

res = *max_element(dp.begin(), dp.end());
printf("%d\n", res);

Вам дана строка $S$ длины $n$ и $q$ запросов. Каждый запрос имеет формат $i, j, k$ , означающий что необходимо отсортировать подстроку, состоящую из символов на позициях $i$ до $j$ включительно, в неубывающем порядке, если $k = 1$ , или в невозрастающем порядке, если $k = 0$ .

После выполнения всех запросов выведите полученную итоговую строку.

Вход. В первой строке заданы два целых числа $n$ и $q (1 \leq n \leq 1 0^{5}, 0 \leq q \leq 50000)$ — длина строки и количество запросов соответственно.

Во второй строке содержится строка $S$ , состоящая только из строчных латинских букв.

Каждая из следующих $q$ строк содержит три целых числа $i, j$ и $k (1 \leq i \leq j \leq n, k = 0$ или $k = 1)$ , описывающих запрос.

Выход. Выведите строку $S$ после выполнения всех запросов.

Открыть задачу

Создадим $26$ деревьев отрезков для подсчёта сумм — по одному для каждой буквы от ' $a$ ' до ' $z$ '. Каждое дерево должно поддерживать множественные модификации.

Например, для буквы ' $a$ ' и строки " $aba c d ab c d a$ " соответствующее дерево отрезков будет выглядеть так:

С помощью такого дерева можно за логарифмическое время определить, сколько раз заданная буква встречается на отрезке $[l; r]$ .

Выполнение запроса на отрезке $[l; r]$ сводится к сортировке подсчётом. Сначала в массиве $c n t$ подсчитывается, сколько раз каждая буква встречается на данном отрезке.

Далее, в зависимости от значения $k$ , мы "пересобираем" этот участок строки:

если $k = 1$ , то символы располагаются в неубывающем порядке — то есть буквы от ' $a$ ' к ' $z$ ';
если $k = 0$ , то в невозрастающем порядке, от ' $z$ ' к ' $a$ '.

Для этого на всём отрезке $[l; r]$ для каждой буквы ' $a$ ' + $j$ , количество которой известно из массива cnt, мы выставляем в дереве отрезков соответствующее количество единиц, начиная с позиции $l$ (если сортируем по возрастанию) или с позиции $r$ (если по убыванию).

Например, пусть на позициях $[10; 17]$ находится подстрока " $a c b d b c ab$ ". Подсчитаем количество каждой буквы на этом интервале:

Буква ' $a$ ' встречается $2$ раза;
Буква ' $b$ ' встречается $3$ раза;
Буква ' $c$ ' встречается $2$ раза;
Буква ' $d$ ' встречается $1$ раз;

Чтобы отсортировать буквы на отрезке по возрастанию, необходимо для дерева отрезков каждой буквы сначала обнулить значения на интервале $[10; 17]$ , а затем выполнить следующие операции:

Для буквы ' $a$ ' на отрезке $[10; 11]$ каждому элементу присвоить $1$ ;
Для буквы ' $b$ ' на отрезке $[12; 14]$ каждому элементу присвоить $1$ ;
Для буквы ' $c$ ' на отрезке $[15; 16]$ каждому элементу присвоить $1$ ;
Для буквы ' $d$ ' на отрезке $[17; 17]$ каждому элементу присвоить $1$ ;

Такое "обновление" деревьев отрезков фактически моделирует перестановку символов на нужном участке без непосредственного изменения самой строки.

После обработки всех запросов итоговая строка восстанавливается из содержимого $26$ деревьев отрезков: для каждой буквы последовательно выполняется обход её дерева, и в тех позициях, где значение равно $1$ , в результирующую строку записывается соответствующий символ.

Для каждой буквы от ' $a$ ' до ' $z$ ' создадим собственное дерево отрезков. Таким образом, всего используется $A L P H A BET = 26$ деревьев, каждое из которых поддерживает операции суммирования и множественную модификацию.

#define MAX 100010
#define ALPHABET 26
struct node
{
  int sum, add;
} SegTree[4*MAX][ALPHABET];

Объявим массив для подсчета количества вхождений каждой буквы.

int cnt[ALPHABET];

Построим $26$ деревьев отрезков по строке $s$ — по одному для каждой буквы латинского алфавита.

void build(int v, int lpos, int rpos)
{
  if (lpos == rpos)
  {
    SegTree[v][s[lpos] - 'a'].sum = 1;
    for (int i = 0; i < ALPHABET; i++)
      SegTree[v][i].add = -1;
  }
  else
  {
    int mid = (lpos + rpos) / 2;
    build(v * 2, lpos, mid);
    build(v * 2 + 1, mid + 1, rpos);
    for (int i = 0; i < ALPHABET; i++)
    {
      SegTree[v][i].sum = 
             SegTree[v * 2][i].sum + SegTree[v * 2 + 1][i].sum;
      SegTree[v][i].add = -1;
    }
  }
}

Вершине $v$ соответствует отрезок $[lp os, r p os]$ , при этом $mi d = (lp os + r p os) /2$ . Выполним проталкивание этой вершины в дереве отрезков с номером $v er$ .

void Push(int v, int lpos, int mid, int rpos, int ver)
{
  if (SegTree[v][ver].add != -1)
  {
    SegTree[2 * v][ver].add = SegTree[v][ver].add;
    SegTree[2 * v][ver].sum = (mid - lpos + 1) * SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].add = SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].sum = (rpos - mid) * SegTree[v][ver].add;
    SegTree[v][ver].add = -1;
  }
}

Вершине $v$ соответствует отрезок $[lp os, r p os]$ . В дереве отрезков с номером $v er$ установим значение $v a l$ для всех элементов с индексами от $l e f t$ до $r i g h t$ .

void SetValue(int v, int lpos, int rpos, int left, int right, 
              int val, int ver)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v][ver].add = val;
    SegTree[v][ver].sum = (right - left + 1) * val;
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  SetValue(2 * v, lpos, mid, left, min(mid, right), val, ver);
  SetValue(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right, 
           val, ver);

  SegTree[v][ver].sum = 
         SegTree[2 * v][ver].sum + SegTree[2 * v + 1][ver].sum;
}

Вершине $v$ соответствует отрезок $[lp os, r p os]$ . Найдем сумму элементов на отрезке $[l e f t; r i g h t]$ в дереве отрезков с номером $v er$ .

int Summa(int v, int lpos, int rpos, int left, int right, int ver)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right)) return SegTree[v][ver].sum;

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  return Summa(2 * v, lpos, mid, left, min(mid, right), ver) +
    Summa(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right, ver);
}

Выполним проталкивание во всех вершинах дерева отрезков с номером $v er$ . Затем внесём букву $v er$ + ' $a$ ' во все позиции строки $s$ , где ее значение в дереве отрезков $v er$ равно $1$ .

void get(int v, int lpos, int rpos, int ver)
{
  if (SegTree[v][ver].sum == 0) return;
  if (lpos == rpos)
  {
    s[lpos] = ver + 'a';
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  get(2 * v, lpos, mid, ver);
  get(2 * v + 1, mid + 1, rpos, ver);
}

Основная часть программы. Читаем входные данные. По входной строке $s$ строим $26$ деревьев отрезков — по одному для каждой буквы латинского алфавита.

cin >> n >> q;
cin >> s;
s = " " + s;
build(1,1,n);

Последовательно обрабатываем $q$ запросов.

for (i = 0; i < q; i++)
{
  cin >> l >> r >> command;

Выполним сортировку подсчетом всех букв на отрезке $[l; r]$ . Для этого сначала подсчитаем количество вхождений каждой буквы ' $a$ ' + $j$ на данном интервале и запишем результат в $c n t [j]$ .

  for (j = 0; j < ALPHABET; j++)
    cnt[j] = Summa(1, 1, n, l, r, j);

Затем, начиная с позиции $p os$ , будем двигаться вправо или влево в зависимости от значения переменной $co mman d$ .

  pos = (command == 1) ? l : r;
  for (j = 0; j < ALPHABET; j++)
  {
    if (!cnt[j]) continue;
    SetValue(1, 1, n, l, r, 0, j);
    if (command)
    {
      SetValue(1, 1, n, pos, pos + cnt[j] - 1, 1, j);
      pos += cnt[j];
    }
    else
    {
      SetValue(1, 1, n, pos - cnt[j] + 1, pos, 1, j);
      pos -= cnt[j];
    }
  }
}

Генерация результирующей строки выполняется на основе содержимого деревьев отрезков. Функция $g e t (1, 1, n, i)$ , используя данные $i$ -го дерева отрезков, расставляет все буквы ' $a$ ' + $i$ на соответствующие позиции строки $s$ . Функция get выполняет полное проталкивание данных, проходя по всем вершинам дерева отрезков за время $O (n)$ .

for (i = 0; i < ALPHABET; i++)
  get(1, 1, n, i);

Выводим результирующую строку.

cout << s.substr(1);

Схема метро состоит из $n$ станций, расположенных на $l$ линиях. Каждая станция принадлежит одной или нескольким линиям (в этом случае на станции можно выполнить пересадку на любую из проходящих через неё линий). Каждая линия включает не менее двух станций и пересекается хотя бы с одной другой линией. Схема метро является связной.

Передвижение между двумя соседними станциями одной линии возможно в обоих направлениях и занимает $2$ минуты. Пересадка с одной линии на другую в пределах одной станции занимает $1$ минуту. Другими затратами времени можно пренебречь.

Определите минимальное время, необходимое менеджеру фирмы «Диез-продукт», чтобы добраться от станции $a$ до здания офиса компании, расположенного рядом со станцией $b$ .

Вход. В первой строке заданы два натуральных числа $n$ и $l (1 \leq l \leq 10)$ . В следующих $l$ строках указаны последовательные номера станций каждой из линий метро. В последней строке заданы номера и линии начальной и конечной станций. Все числа натуральные и не превышают $70$ .

Выход. Выведите минимальное время движения между указанными станциями.

Пример. В приведенном примере необходимо найти кратчайший маршрут от станции $2$ на линии $1$ до станции $7$ на линии $3$ .

Идём по линии $1$ от станции $2$ к станции $1$ : $2$ минуты.
Совершаем пересадку на станции $1$ с линии $1$ на линию $2$ : $1$ минута.
Идём по линии $2$ от станции $1$ к станции $5$ : $4$ минуты.
Совершаем пересадку на станции $5$ с линии $2$ на линию $3$ : $1$ минута.
Идём по линии $3$ от станции $5$ к станции $7$ : $2$ минуты.

Итого весь путь займет $2 + 1 + 4 + 1 + 2 = 10$ минут.

Открыть задачу

Кратчайшее расстояние от источника до вершины $v$ , принадлежащей линии $l$ , храним в $d i s t [v] [l]$ , где $1 \leq v \leq 70, 1 \leq l \leq 10$ . Граф представляется в виде списков смежности. Для каждого ребра, помимо направления и стоимости, дополнительно хранится номер линии метро, к которой принадлежит вершина, в которую это ребро ведёт.

Алгоритм начинается со станции $s$ , расположенной на линии $l in e 1$ . Искомое значение — минимальная стоимость пути, за которую можно добраться до станции $f$ , находящейся на линии $l in e 2$ .

При переходе между вершинами необходимо проверять, принадлежат ли они одной линии: если линии различаются, к стоимости добавляется $1$ (пересадка между линиями).

С помощью алгоритма Дейкстры находим кратчайшее расстояние из состояния $(s, l in e 1)$ в состояние $(f, l in e 2)$ .

Пример

В приведённом примере требуется найти кратчайший маршрут от станции $2$ на линии $1$ до станции $7$ на линии $3$ .

Идём по линии $1$ от станции $2$ к станции $1$ : $2$ минуты.
Совершаем пересадку на станции $1$ с линии $1$ на линию $2$ : $1$ минута.
Идём по линии $2$ от станции $1$ к станции $5$ : $4$ минуты.
Совершаем пересадку на станции $5$ с линии $2$ на линию $3$ : $1$ минута.
Идём по линии $3$ от станции $5$ к станции $7$ : $2$ минуты.

Итого весь путь займет $10$ минут.

Количество вершин в графе не более $M A X = 71$ . Количество линий не более $L I NES = 11$ .

#define MAX 71
#define LINES 11

Кратчайшее расстояние от источника до вершины $v$ , принадлежащей линии $l$ , храним в $d i s t [v] [l]$ . Объявим массив для хранения кратчайших расстояний.

int dist[MAX][LINES];

Структура node содержит информацию о ребре:

$t o$ — направление ребра;
$cos t$ — стоимость ребра;
$l in e$ — какой линии метро ребро принадлежит;

struct node
{
  int to, cost, line;
  node(int to, int cost, int line) : to(to), cost(cost), line(line) {}
};

Структура node также используется в очереди с приоритетами, где

$t o$ — текущая вершина;
$cos t$ — минимальная стоимость проезда до вершины $t o$ (на линии $l in e$ );
$l in e$ — номер линии метро, на которой находится вершина $t o$ ;

В очереди с приоритетами вершины упорядочиваются по возрастанию стоимости проезда.

bool operator< (node a, node b)
{
  return a.cost > b.cost;
}

Объявим список смежности для представления графа.

vector<vector<node> > g;

Основная часть программы. Читаем входные данные.

scanf("%d %d", &n, &l);
g.resize(n + 1);

Читаем $i$ -ую линию метро. Время движения между соседними станциями $u$ и $v$ равно $2$ .

for (i = 1; i <= l; i++)
{

Читаем станцию $u$ — первую станцию $i$ -ой линии метро. За станцией $u$ следует станция $v$ .

  scanf("%d ", &u);
  while (scanf("%d%c", &v, &ch))
  {

Движение между станциями возможно в обоих направлениях, при этом стоимость ребра равна $2$ .

    g[u].push_back(node(v, 2, i));
    g[v].push_back(node(u, 2, i));
    u = v;

Как только достигаем конца строки, завершаем чтение данных текущей линии метро.

    if (ch == '\n') break;
  }
}

Инициализируем массив для хранения кратчайших расстояний.

for (i = 1; i <= n; i++)
for (j = 1; j <= l; j++)
  dist[i][j] = 2000000000;

Читаем информацию о начальной и конечной станции. Для каждой станции задается линия, которой она принадлежит.

scanf("%d %d %d %d", &s, &line1, &f, &line2);

Стартуем со станции $s$ , находящейся на линии $l in e 1$ .

dist[s][line1] = 0;

Заносим в очередь структуру node, содержащую начальную вершину $s$ на линии $l in e 1$ . Стоимость достижения начальной вершины равна $0$ .

priority_queue<node, vector<node> > pq;
pq.push(node(s, 0, line1)); // (v, cost, line)
while (!pq.empty())
{

Извлекаем из очереди вершину $v$ с наименьшей стоимостью.

  int cost = pq.top().cost;
  int v = pq.top().to;
  int l1 = pq.top().line;
  pq.pop(); // dist[v][l1] = cost

Перебираем все вершины, смежные с $v$ .

  for (i = 0; i < g[v].size(); i++)
  {

Рассматриваем ребро $v \to t o$ со стоимостью $w$ , принадлежащее линии $l 2$ .

    int to = g[v][i].to;
    int w = g[v][i].cost;
    int l2 = g[v][i].line;

Если двигаться по ребру $v \to t o$ , то стоимость пути составит $cos t + w$ .

    int tot_cost = cost + w;

Если вершины $v$ и $t o$ принадлежат разным линиям, необходимо совершить пересадку с линии $l 1$ на линию $l 2$ .

    if (l1 != l2) tot_cost += 1;

Если движение по ребру $v \to t o$ улучшает текущее значение, обновляем $d i s t [t o] [l 2]$ и помещаем вершину $t o$ в очередь (стоимость ее достижения составляет $t o t_cos t$ и она находится на линии $l 2$ ).

    if (tot_cost < dist[to][l2])
    {
      dist[to][l2] = tot_cost;
      pq.push(node(to, tot_cost, l2));
    }
  }
}

Выводим ответ — минимальную стоимость пути до вершины $f$ на линии $l in e 2$ .

printf("%d\n", dist[f][line2]);

Комментарии

Пока что ничего

Будьте первым, кто начнет обсуждение!

Войти

Загрузка

Момент, получаем данные с сервера