Задачи с codeforses на разные темы (ссылки для проверки приложенны к каждой задаче)

Тема: Алгоритмы на строках
1.
B. Поиск подстроки
ограничение по времени на тест1 секунда
ограничение по памяти на тест 256 мегабайт

Найти все вхождения строки T в строку S при условии, что строка S свёрнута в кольцо — то есть после её последнего символа снова идёт первый.

В первой строке входных данных записана строка S, во второй — строка T. Обе строки состоят только из строчных английских букв. Длины строк могут быть в диапазоне от 1 до 105 символов включительно.

Выведите все вхождения строки T в строку S в порядке возрастания. Нумерация позиций строк начинается с нуля.

входные данные
ababbabab
aba
выходные данные
0 5 7

входные данные
abab
ababab

выходные данные
0 2

ссылка для теста:https://codeforces.com/group/50U9rD7F6W/contest/32...


2. Количество различных подстрок
ограничение по времени на тест1 секунда
ограничение по памяти на тест 256 мегабайт

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


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

Выходные данные
Выведите одно целое число — количество различных подстрок строки S.

входные данные
abcde

выходные данные
15

входные данные
aaaaa

выходные данные
5

входные данные
abacabadabacaba

выходные данные
85
ссылка для теста:https://codeforces.com/group/50U9rD7F6W/contest/32...

Тема: Обходы графов

3. Слияние множеств
ограничение по времени на тест 2 секунды
ограничение по памяти на тест 256 мегабайт

Имеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.

Вам нужно выполнить M запросов. В каждом запросе даются целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если они уже в одном множестве, то ничего не делать).


Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).

В следующих M строках записаны по два целых числа – номера объектов, множества которых нужно объединить.

Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.

входные данные
6 5
1 2
3 4
6 5
2 3
3 1

выходные данные
2

Примечание
В примере останутся два множества – {1, 2, 3, 4} и {5, 6}.

ссылка для теста:https://codeforces.com/group/50U9rD7F6W/contest/37...

4. Объединения с отменами
ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт

Имеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.

Вам нужно выполнить M запросов двух типов.

Первый тип запроса – объединение двух множеств. Вам даются два целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если объекты уже в одном множестве, то ничего делать не нужно).

Второй тип запроса – отмена последнего выполненного запроса на объединение. Учитываются и те запросы, в которых реального объединения не происходило (при отмене таких запросов также делать ничего не надо).


Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).

В каждой из следующих M строк записаны по два целых числа u и v. Если u > 0, v > 0, то это запрос первого типа, и вам нужно выполнить объединение множеств, содержащих эти элементы. Если же u = v = 0, то это запрос второго типа, и нужно выполнить отмену последнего выполненного запроса на объединение.

Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.


входные данные
6 7
1 2
3 4
2 3
0 0
0 0
3 5
1 3
выходные данные
3

входные данные
3 5
1 2
2 3
3 1
0 0
0 0

выходные данные
2

Примечание
В первом примере останутся три множества – {1,2,3,5}, {4} и {6}.
Во втором примере останутся два множества – {1,2} и {3}.


ссылка для теста:https://codeforces.com/group/50U9rD7F6W/contest/37...


5.Михаил Густокашин против бюрократии
ограничение по времени на тест1 секунда
ограничение по памяти на тест 256 мегабайт

Задача классическая. Формулировка: Михаил Густокашин.

Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.

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

Закончилось тем, что я составил список, какому врачу нужны какие справки.


Входные данные
В первой строке моего списка содержится общее количество врачей (1 ≤ K ≤ 100). В следующих K строках описываются необходимые справки. Первое число (j) в i + 1 строке входных данных означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел – номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.

Выходные данные
Если подписи всех врачей собрать невозможно, то следует вывести "NO". Если же все справки собрать возможно, то в первой строке должно содержаться "YES", а в следующих K строках – последовательность, в которой нужно получать справки.


входные данные
4
1 2
0
2 1 4
1 1

выходные данные
YES
2
1
4
3

ссылка для теста:https://codeforces.com/group/50U9rD7F6W/contest/37...