Будем сохранять имена людей в отдельном массиве names, а также двухмерный массив_(fl[l,r])_ типа boolean, в котором значение правда означает дружбу между l и r человеком. Каждый раз считывая строку, определяем номера людей, иначе если таких нет, прибавляем ети имена в массив имен. Теперь нам надо вести свой журнал, то-есть создать массив, где будет время отправления сообщения и номера людей. Теперь для каждной записи пробежим все предедущие записи, и если отправитель этой записи, это получатель одной из предедущих записей, то эсли время этих сообщений разные, проверяем их равенство, как сказано в условии, если оно правильное то fl[l,r]:=true;и количество друзей+1. тогда выводим количес тво друзей, и пробежавшись по массиву fl если fl[l,r]=1, то выводим names[l] и names[r]. Асимтотика этого алгоритма O(N(N-1)/2), N-количество записей в журнале.
B. На вкус и цвет фломастеры разные
Здесь нужно создать массив a[cl,r], он означает, сколько есть фломастером цветом сl и размером r. и еще массив b[r], количество фломастеров с размером r. При считки фломастеров с параметрами cl,r плюсуем a[cl,r] и b[r] Количество красиво-закрытых фломастеров будем хранить в ans, а просто закрытых в ans1. При считки колпачков с параметрами cl,r, если можем отнимаем 1 от a[cl,r] и от b[r], и плюсуем 1 до ans иначе если можем отнимаем 1 от b[r] и плюсуем 1 до ans1. Ответом будет два числа ans и ans+ans1. Асимтотока O(N+M+1000).
C. String Manipulation 1.0 Считываем строку. Заведем масив a[l,c] — количество символов с в строке под номером l. Подсчитаем все значения a[l,c] с параметрами l=1, c='a'..'z'. Заведем массив строк, где изначально все строки равны строке, которую мы считали, теперь для l=2..k a[l,c]=a[1,c]; А теперь начнем удалять. считаем Н(номер) и С(символ). Sum=0;i=0; А теперь пока sum<H будем плюсовать і, и додавть до суммы s[i,C]. После этого онимаем от Н сумму и бежим по строчке с номером i,и ищем Н-й символ с. и удаляем его. В конце выводим все К строк.
Асимптотика O(N(K+100)) , 100- макс. длинна строки.
Первое, что нужно сделать — найти все подпалиндромы в заданной строке. Для этого можно применить красивый алгоритм, описанный на сайте e-maxx.ru/algo. Вкратце, результатом работы этого алгоритма являются максимальные возможные длины подпалиндромов, центры которых находятся либо в позиции i строки, либо между позициями i и i + 1, для всех таких возможных позиций центра.
Найдём для каждой позиции i строки величину start_i, равную количеству подпалиндромов, начало которых находится в позиции i. Все эти значения можно найти за линейное время. Для этого заведём вспомогательный массив a_i. Если после обработки некоторой позиции выяснилось, что какие-то новые подпалиндромы начинаются в позициях i..j, то значение a_i увеличим на 1, а значение a_j + 1 уменьшим на 1. Теперь . Обоснование этого факта оставляется читателю в качестве упражнения :) Аналогичным образом можно вычислить finish_i — количество подпалиндромов, конец которых находится в позиции i. Найдём количество пар непересекающихся подпалиндромов. Заметим, что если два подпалиндрома не пересекаются, то один из них лежит в строке строго левее другого. Количество пар непересекающихся подпалиндромов можно подсчитать по формуле: finish_i(i=1..n)*start_j(j=i+1..n);
Эту сумму можно найти за линейное время, если значение при переходе от i к i + 1 пересчитывать добавлением finishi к уже накопленной сумме. Таким образом, сложность решения O(N).
Comments (0)
