Задача 4 «Поездка на каникулах»
Это самая сложная задача первого тура. Полное решение этой задачи требует нескольких идей.
Пусть для каждой станции i определена величина go1[i] – максимальный номер станции, до которой можно доехать от станции i, используя ровно 1 билет. Заметим, что нам не важно, на каком месте мы приедем на станцию, на которой мы делаем пересадку, поэтому выгодно от станции i всегда ехать либо до конечной станции маршрута, либо до станции go1[i].
Решим сначала задачу для одного варианта поездки, используя построенный массив go1. Начнем со станции f. Если go1[f] ≥ t, то достаточно одного билета. Иначе переместимся на станцию go1[f], найдем ответ для нее и прибавим 1. Следует также учесть, что если go1[i] = i, то от станции i нельзя поехать дальше, и если в процессе перемещения мы встречаем такую станцию, то ответ для рассматриваемого вариант «–1». Отметим, что время работы предложенного метода ответа на запрос есть O(n).
Посмотрим теперь, как построить массив go1.
Наивное построение, которое для каждой станции и каждого места находит, до какой станции можно доехать с использованием этого билета, и выбирает максимум, а также в сочетании с описанным методом по массиву go1 находит число билетов для одного варианта за время O(n), позволяет решить подзадачу 1.
Пример программы на PABC.
program trains;
const nmax=100;
var
fin, fout: text;
n, m, k: longint;{кол станций, кол билетов, кол мест}
l, r, p: longint;{откуда, куда, место}
i, j: longint;
field: array[1..nmax,1..nmax ] of boolean;{занятые места}
dist: array[1..nmax,1..nmax] of integer; {куда макс есть билет}
q, s, t: longint; {кол вариантов, откуда, куда}
pos, best, ans: longint;
begin
assign(fin, 'trains.in');
assign(fout, 'trains.out');
reset(fin);
rewrite(fout);
readln(fin, n,m,k);{ввод кол станц, билетов, мест}
for i:=1 to m do {для каждого билета}
begin
readln(fin, l, r, p);
for j:=l to r-1 do {отмечаем занятые места}
field[p,j]:=true
end;
for i:=1 to k do {вычисляем максим кол станций для своб билета}
for j:=n-1 downto 1 do
if field[i,j] then dist[i,j]:=0
else dist[i,j] := dist[i,j+1]+1;
{Обрабатываем варианты поездок}
readln(fin, q); {колич вариантов}
for i:=1 to q do
begin
readln(fin, s,t);
pos:=s; ans:=0;
while pos<t do
begin
best:=-1;
for j:=1 to k do
if best<dist[j,pos] then
best:=dist[j,pos];
if best=0 then break
else
begin
inc(ans);
inc(pos,best)
end
end;{while}
if pos>=t then writeln(fout, ans)
else writeln(fout,'-1')
end;
close(fout);
close(fin);
end.
Для решения подзадачи 2 требуется более совершенный способ построения массива go1.
Будем говорить, что место a свободно на протяжении отрезка [c, d], если никакой из проданных билетов не занимает это место на перегонах этого отрезка станций. Отсортировав введенные билеты по месту, а затем по начальной станции, легко построить все максимальные свободные отрезки станций.
Отсортируем свободные отрезки по начальной станции.
Будем рассматривать станции по очереди. Будем поддерживать множество «открытых» свободных отрезков, которые начинаются не позже рассматриваемой станции, в структуре данных, которая позволяет поиск максимума по ключу (двоичная куча, дерево отрезков или std::set подойдут). В качестве ключа будем использовать конец отрезка.
Рассматривая очередную станцию i, добавим все свободные отрезки, которые в ней начинаются, в множество открытых отрезков. Теперь go1[i] равно максимальному концу открытого отрезка, либо i, если множество открытых отрезков пусто, или все они заканчиваются до i.
Этот метод позволяет решить подзадачу 2.
Для решения подзадачи 3 требуется быстрее отвечать на запрос. Для этого используем метод «двоичных подъемов». Посчитаем величину go[j][i], которая равна максимальному номеру станции, до которого можно доехать от станции, используя не более 2j билетов.
Код, вычисляющий go[j][i] по go1[i] приведен ниже.
for (int i = 1; i <= sz; i++) {
for (int j = 0; j < n; j++) {
int u = go[i - 1][j];
go[i][j] = go[i - 1][u];
}
}
В качестве sz следует выбрать минимальную величину, такую что 2sz ≥ n.
Теперь для получения ответа на запрос будем делать все уменьшающиеся «прыжки» по степеням двойки. Код, который отвечает на запрос с использованием массива go
приведен ниже.
