| | | |
|
Сбалансированные подмножества
Динамическое программирование по подстрокам
Суффиксный массив
Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:
Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x1,y) (x2,y) (x1≤x2) есть часть подмножества, то все ячейки (x,y) с x1≤x≤x2 также часть подмножества.
Если ячейки (x,y1) and (x,y2) (y1≤y2) есть часть подмножества, то все ячейки (x,y) with y1≤y≤y2 также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 109+7.
Входные данные:
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.
Выходные данные:
Количество сбалансированных подмножеств по модулю 109+7.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
2
GG
GG |
13 |
Для этого теста все 4-связные подмножества сбалансированные.
G. .G .. .. GG .G .. G. GG .G G. GG GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG |
| 2 |
4
GGGG
GGGG
GG.G
GGGG |
|
642
Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию:
GG..
.G..
GG..
.... |
| |
|
|
Путешествие по строке
Дерево отрезков, RSQ, RMQ
sqrt декомпозиция
Хеш
Суффиксный массив
Динамическое программирование
Хеш
Скажем, что последовательность строк t1 , ..., tk является путешествием длины k , если для всех i > 1 ti является подстрокой ti - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t1 , ..., tk , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u1 , ..., uk + 1 , такие, что s = u1t1u2 t2 ... uk tk uk + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.
Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .
Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .
Во второй строке содержится строка s , состоящая из n строчных английских букв.
Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .
Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .
Во втором примере подходящим вариантом будет { bb , b } .
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
abcdbcc |
3 |
| 2 |
4
bbcb |
2 |
| |
|
|
Оптимальное подмножество строк - 2
Суффиксный массив
Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если:
- все строки в множестве различны;
- не существует такой пары различных строк, что одна строка является суффиксом другой.
Строка s называется суффиксом строки t, если длина строки s не больше длины строки t, а также для любого i i-й символ строки s, считая с конца, совпадает с i-м символом строки t, считая с конца.
Например, ab является суффиксом строк ab и cab, но не является суффиксом строк a и ac.
Петя же решил придумать что-то новое и ввёл новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое что:
- все строки в множестве различны;
- у любых двух различных строк наибольший общий суффикс имеет длину не больше
k.
Наибольшим общим суффиксом двух строк s и t называется наибольшая по длине строка, являющаяся суффиксом обеих строк.
Теперь по данному набору строк s1, s2, ..., sn и числу k Петя хочет найти в этом наборе k-бессуффиксный код, состоящий из максимально возможного количества строк.
Помогите ему — найдите этот код.
Входные данные
В первой строке содержатся два числа n и k — количество строк в наборе и максимальная длина общего суффикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100). В i-й из следующих n строк содержится строка si — i-е слово из набора (1 ≤ |si| ≤ 100). Все строки состоят из строчных латинских букв. Гарантируется, что суммарная длина всех строк не превосходит 106.
Выходные данные
В первой строке выведите число m — максимально возможное количество строк в k-бессуффиксном коде. В следующих m строках выведите элементы этого кода. Элементы можно выводить в любом порядке. Если существует несколько ответов с максимальным m, разрешается вывести любой.
Примечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.
| |
|
|
Standing Out from the Herd
Суффиксный массив
Коровы Фермера Джона хотят измерить уникальность своих имён.
Имя каждой коровы содержит некоторое количество подстрок.
Например, "amy" имеет подстроки {a, m, y, am, my, amy}, а "tommy"
имеет подстроки: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.
Имя коровы имеет "фактор уникальности" - количество подстрок, которых нет
у имён других коров. Например, если "amy" - единственная корова в стаде, её
фактор уникальности равен 6. Если "tommy" - единственная корова в стаде, её
фактор уникальности равен 1. Если в стаде 2 коровы "amy" и "tommy", то их
факторы уникальности будут соответственно 3 и 11.
По заданному стаду коров определите фактор уникальности каждой коровы.
ФОРМАТ ВВОДА (файл standingout.in):
Первая строка ввода содержит \(N\) (\(1 \le N \le 10^5\)). Каждая из следующих \(N\)
строк содержит имя коровы в стаде. Каждое имя содержит только маленькие латинские
буквы a-z. Общая длина всех имён не превысит \(10^5\).
ФОРМАТ ВЫВОДА (файл standingout.out):
Выведите \(N\) чисел, по одному в строке, описывающие фактор уникальности каждой
коровы.
| |
|
|
I. Deja vu
Суффиксный массив
строковые суфф. структуры
This is an unusual problem in an unusual contest, here is the announcement: http://cf.m27.workers.dev/blog/entry/73543 You run a string shop. During a day your customers want to buy strings of certain lengths and sometimes satisfying other properties. Today your first customer asked you if you have a string of length \(k\). In fact, you have a string of length \(n\) and can cut a string of length \(k\) starting at any position out of it. You wonder how many distinct values this string can equal. Please note that in your shop strings are over an alphabet of size \(2\). Output In the only line print the number of distinct substrings of length \(k\) of the string \(s\). Note The second sample test represents the de Bruijn sequence of order 3.
| |
|