Codeforces Round 868 (Div. 2) |
---|
Закончено |
Палиндром — это строка, которая читается одинаково с обеих сторон. Например, строка abcba — палиндром, а строка abca — нет.
Пусть $$$p(t)$$$ — это количество уникальных палиндромных подстрок строки $$$t$$$, т.е. количество подстрок $$$t[l \dots r]$$$, которые сами являются палиндромами. Даже если некоторые подстроки присутствуют в $$$t$$$ несколько раз, они учитываются ровно один раз. (Вся строка $$$t$$$ также является подстрокой $$$t$$$).
Например, строка $$$t$$$ $$$=$$$ abcbbcabcb имеет $$$p(t) = 6$$$ уникальных палиндромных подстрок: a, b, c, bb, bcb и cbbc.
Теперь определим $$$p(s, m) = p(t)$$$ где $$$t = s[1 \dots m]$$$. Другими словами, $$$p(s, m)$$$ это количество палиндромных подстрок префикса строки $$$s$$$ длины $$$m$$$. Например, $$$p($$$abcbbcabcb$$$, 5)$$$ $$$=$$$ $$$p($$$abcbb$$$) = 5$$$.
Вам даны целое число $$$n$$$ и $$$k$$$ «условий» ($$$k \le 20$$$). Назовем строку $$$s$$$, состоящую из $$$n$$$ строчных латинских букв, хорошей если все $$$k$$$ условий удовлетворены одновременно. Условие — это пара $$$(x_i, c_i)$$$, обозначающая что:
Изучите примечание, если вам нужны дополнительные пояснения.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 20$$$) — длина хорошей строки $$$s$$$ и количество условий.
Вторая строка каждого набора входных данных содержит $$$k$$$ целых чисел $$$x_1, x_2, \dots, x_k$$$ ($$$3 \le x_1 < x_2 < \dots < x_k = n$$$) где $$$x_i$$$ — это длина префикса в $$$i$$$-м условии.
Третья строка каждого набора входных данных содержит $$$k$$$ целых чисел $$$c_1, c_2, \dots, c_k$$$ ($$$3 \le c_1 \le c_2 \le \dots \le c_k \le \min{\left(10^9, \frac{(n + 1) n}{2} \right)}$$$) где $$$c_i$$$ — это количество палиндромных подстрок в $$$i$$$-м условии.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 5$$$.
Для каждого набора входных данных если нет хорошей строки $$$s$$$ длины $$$n$$$, которая удовлетворяет всем запросам, выведите NO.
Иначе, выведите YES и строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв, которая удовлетворяет всем запросам. Если есть несколько ответов, выведите любой из них.
710 25 105 63 1334 23 43 34 23 43 44 14510 34 6 104 5 810 44 6 7 104 5 7 8
YES abcbbcabcb YES foo YES ayda YES wada NO YES abcbcacbab NO
В первом наборе строка $$$s$$$ $$$=$$$ abcbbcabcb удовлетворяет $$$k = 2$$$ условиям:
Во втором наборе строка foo удовлетворяет $$$k = 1$$$ условию:
В третьем наборе строка ayda удовлетворяет $$$k = 2$$$ условиям:
В четвертом наборе строка wada удовлетворяет $$$k = 2$$$ условиям:
В пятом наборе можно доказать, что нет строки длины $$$4$$$ которая имеет $$$5$$$ палиндромных подстрок.
В шестом наборе строке abcbcacbab удовлетворяет $$$k = 3$$$ условиям:
Название |
---|