Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 47 48 49 50 51 52 53 >> Отображать по:
#113575
Галактический апокалипсис
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Галактический апокалипсис ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:

1. A и B - различные планеты.

2. В действующей сети межпланетных магистралей существует путь между A и B .

3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.

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

Входные данные

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).

Выходные данные

Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.

Примечание

Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.

Примеры
Входные данные
2
1 2 0
1
Выходные данные
1
0
Входные данные
3
1 2 4
2 3 4
1 2
Выходные данные
1
0
0
Входные данные
4
1 2 0
2 3 0
2 4 0
3 1 2
Выходные данные
6
3
1
0
#113580
Маленький Матеж и большие проблемы
  
Темы: [Хеш]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Маленький Матеж и большие проблемы ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.

Входные данные

В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.

Выходные данные

Выведите Q строк: в каждой ответ для соответствующего шаблона.

Система оценки

40 баллов: 1 ≤ N , Q ≤ 1000

Примеры
Входные данные
3 3
aaa
abc
aba
a*a
aaa*
*aaa
Выходные данные
2
1
1
Входные данные
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c
Выходные данные
5
0
2
#113581
Массивы, числа, три хеша
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Массивы, числа, три хеша ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .

Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s )  =  ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.

Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .

Входные данные

В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).

Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).

Гарантируется, что во всех тестах K ≤ 2 N - 1 .

Выходные данные

Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .

Примечание

Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.

Примеры
Входные данные
2 3 1 5
1 2
Выходные данные
1 1
3 2
2 1
Входные данные
3 4 2 3
1 3 1
Выходные данные
1 1
1 1
0 2
2 2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1 1
25 2
25 2
577 3
274 4
578 3
#113597
Тяжелые палиндромы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

Палиндром - это слово, которое читается справа налево также, как слева направо. Например, "a", "abba", "anavolimilovana" - палиндромы.

Весом строки, состоящей из строчных латинских символов будем называть количество ее подстрок (слов), являющихся палиндромами (при этом каждое вхождение подстроки считается отдельно). Формально, пусть W - строка длины N . Слово w a , b - подстрока W , состоящая из символов на позициях с индексами с a по b включительно. Вес строки W - это количество пар целых чисел a , b ( 1 ≤ a , b ≤ N ) таких, что w a , b является палиндромом.

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

Входные данные

Первая строка содержит одну строку W ( 1 ≤ | W | ≤ 100000 ), состоящую из строчных латинских символов.

Выходные данные

Выведите одно целое число - максимально возможный вес.

Примечание

Решения, работающие при | W | ≤ 100 , будут оцениваться в 17 баллов.
Решения, работающие при | W | ≤ 5000 , будут оцениваться еще в 37 баллов.

Примеры
Входные данные
aaaa
Выходные данные
10
Входные данные
baccb
Выходные данные
9
Входные данные
slavko
Выходные данные
7
#113598
Сдвигай, считай, и снова
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Пусть дан строчный латинский символ c . Тогда операция shift ( c ) превращает c в следующий по порядку символ в алфавите. Например, shift (a) = b, shift (e) = f, shift (z) = a.

Дана строка S , состоящая из N строчных латинских символов (индексация с 0). Необходимо обработать Q запросов 2 типов:

"1 i j t": ко всем элементам строки с индексами в отрезке [i:j] применить t раз операцию shift .

"2 i j": найдите количество непустых подмножеств символов строки { c 1 , c 2 , ... , c k }, где i ≤ index c 1 < index c 2 < ... < index c k ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 9 + 7 .

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

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

Входные данные

Первая строка содержит два целых числа N и Q ( 1 ≤ N , Q ≤ 10 5 ) - длину строки и количество запросов соответственно. Вторая строка содержит одну строку S длины N , состоящую из строчных латинских символов. Каждая из последующих Q строк содержит запрос в формате, описанном в условии.

Выходные данные

Для каждого запроса второго типа выведите одно целое число - ответ на данный запрос.

Примечание

Решения, работающие при N ≤ 500 и Q ≤ 500 , будут оцениваться в 20 баллов.

Решения, работающие при условии, что все запросы являются запросами второго типа, оцениваются еще в 30 баллов.

Примеры
Входные данные
3 5
aba
2 0 2
2 0 0
2 1 2
1 0 1 1
2 0 2
Выходные данные
5
1
2
3
Входные данные
5 7
acdec
2 0 3
1 3 4 36
1 2 3 81
1 1 4 11
2 3 3
2 2 3
2 1 2
Выходные данные
4
1
2
2
Страница: << 47 48 49 50 51 52 53 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест