A15924 | Unique Palindromes
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
A palindrome is a string that reads the same backwards as forwards. For example, the string abcba is palindrome, while the string abca is not.
Let $p(t)$ be the number of unique palindromic substrings of string $t$ , i. e. the number of substrings $t[l \dots r]$ that are palindromes themselves. Even if some substring occurs in $t$ several times, it's counted exactly once. (The whole string $t$ is also counted as a substring of $t$ ).
For example, string $t$ $=$ abcbbcabcb has $p(t) = 6$ unique palindromic substrings: a, b, c, bb, bcb and cbbc.
Now, let's define $p(s, m) = p(t)$ where $t = s[1 \dots m]$ . In other words, $p(s, m)$ is the number of palindromic substrings in the prefix of $s$ of length $m$ . For example, $p($ abcbbcabcb $, 5)$ $=$ $p($ abcbb $) = 5$ .
You are given an integer $n$ and $k$ "conditions" ( $k \le 20$ ). Let's say that string $s$ , consisting of $n$ lowercase Latin letters, is good if all $k$ conditions are satisfied at the same time. A condition is a pair $(x_i, c_i)$ and have the following meaning:
- $p(s, x_i) = c_i$ , i. e. a prefix of $s$ of length $x_i$ contains exactly $c_i$ unique palindromic substrings.
Find a good string $s$ or report that such $s$ doesn't exist.Look in Notes if you need further clarifications.
Let $p(t)$ be the number of unique palindromic substrings of string $t$ , i. e. the number of substrings $t[l \dots r]$ that are palindromes themselves. Even if some substring occurs in $t$ several times, it's counted exactly once. (The whole string $t$ is also counted as a substring of $t$ ).
For example, string $t$ $=$ abcbbcabcb has $p(t) = 6$ unique palindromic substrings: a, b, c, bb, bcb and cbbc.
Now, let's define $p(s, m) = p(t)$ where $t = s[1 \dots m]$ . In other words, $p(s, m)$ is the number of palindromic substrings in the prefix of $s$ of length $m$ . For example, $p($ abcbbcabcb $, 5)$ $=$ $p($ abcbb $) = 5$ .
You are given an integer $n$ and $k$ "conditions" ( $k \le 20$ ). Let's say that string $s$ , consisting of $n$ lowercase Latin letters, is good if all $k$ conditions are satisfied at the same time. A condition is a pair $(x_i, c_i)$ and have the following meaning:
- $p(s, x_i) = c_i$ , i. e. a prefix of $s$ of length $x_i$ contains exactly $c_i$ unique palindromic substrings.
Find a good string $s$ or report that such $s$ doesn't exist.Look in Notes if you need further clarifications.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ( $3 \le n \le 2 \cdot 10^5$ ; $1 \le k \le 20$ ) — length of good string $s$ and number of conditions.
The second line of each test case contains $k$ integers $x_1, x_2, \dots, x_k$ ( $3 \le x_1 < x_2 < \dots < x_k = n$ ) where $x_i$ is the length of the prefix in the $i$ -th condition.
The third line of each test case contains $k$ integers $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)}$ ) where $c_i$ is the number of palindromic substrings in the $i$ -th condition.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$ .
The first line of each test case contains two integers $n$ and $k$ ( $3 \le n \le 2 \cdot 10^5$ ; $1 \le k \le 20$ ) — length of good string $s$ and number of conditions.
The second line of each test case contains $k$ integers $x_1, x_2, \dots, x_k$ ( $3 \le x_1 < x_2 < \dots < x_k = n$ ) where $x_i$ is the length of the prefix in the $i$ -th condition.
The third line of each test case contains $k$ integers $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)}$ ) where $c_i$ is the number of palindromic substrings in the $i$ -th condition.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$ .
输出格式
For each test case, if there is no good string $s$ of length $n$ that satisfies all conditions, print NO.
Otherwise, print YES and a string $s$ of length $n$ , consisting of lowercase Latin letters, that satisfies all conditions. If there are multiple answers, print any of them.
Otherwise, print YES and a string $s$ of length $n$ , consisting of lowercase Latin letters, that satisfies all conditions. If there are multiple answers, print any of them.
输入输出样例
输入 #1
7 10 2 5 10 5 6 3 1 3 3 4 2 3 4 3 3 4 2 3 4 3 4 4 1 4 5 10 3 4 6 10 4 5 8 10 4 4 6 7 10 4 5 7 8
输出 #1
YES abcbbcabcb YES foo YES ayda YES wada NO YES abcbcacbab NO
In the first test case, string $s$ $=$ abcbbcabcb satisfies $k = 2$ conditions:
- $p(s, x_1) = p(s, 5) =$ $p($ abcbb $) = 5 = s_1$ . Palindromic substrings are a, b, c, bb and bcb.
- $p(s, x_2) = p(s, 10) =$ $p($ abcbbcabcb $) = 6 = s_2$ . Palindromic substrings are the same as above, and one extra substring cbbc.
In the second test case, string foo satisfies $k = 1$ condition:
- $p($ foo $) = 3$ . Palindromic substrings are f, o and oo.
There are other possible answers.In the third test case, string ayda satisfies $k = 2$ conditions:
- $p($ ayd $) = 3$ . Palindromic substrings are a, y and d.
- $p($ ayda $) = 3$ . Palindromic substrings are the same.
In the fourth test case, string wada satisfies $k = 2$ conditions:
- $p($ wad $) = 3$ . Palindromic substrings are w, a and d.
- $p($ wada $) = 4$ . Palindromic substrings are the same, and one extra substring ada.
In the fifth test case, it can be proven that there is no string of length $4$ which has $5$ palindromic substrings.
In the sixth test case, string abcbcacbab satisfies $k = 3$ conditions:
- $p($ abcb $) = 4$ . Palindromic substrings are a, b, c and bcb.
- $p($ abcbca $) = 5$ . Palindromic substrings are the same, and one extra substring cbc.
- $p($ abcbcacbab $) = 8$ . Palindromic substrings are the same, and three extra substrings cac, bab and bcacb.
- $p(s, x_1) = p(s, 5) =$ $p($ abcbb $) = 5 = s_1$ . Palindromic substrings are a, b, c, bb and bcb.
- $p(s, x_2) = p(s, 10) =$ $p($ abcbbcabcb $) = 6 = s_2$ . Palindromic substrings are the same as above, and one extra substring cbbc.
In the second test case, string foo satisfies $k = 1$ condition:
- $p($ foo $) = 3$ . Palindromic substrings are f, o and oo.
There are other possible answers.In the third test case, string ayda satisfies $k = 2$ conditions:
- $p($ ayd $) = 3$ . Palindromic substrings are a, y and d.
- $p($ ayda $) = 3$ . Palindromic substrings are the same.
In the fourth test case, string wada satisfies $k = 2$ conditions:
- $p($ wad $) = 3$ . Palindromic substrings are w, a and d.
- $p($ wada $) = 4$ . Palindromic substrings are the same, and one extra substring ada.
In the fifth test case, it can be proven that there is no string of length $4$ which has $5$ palindromic substrings.
In the sixth test case, string abcbcacbab satisfies $k = 3$ conditions:
- $p($ abcb $) = 4$ . Palindromic substrings are a, b, c and bcb.
- $p($ abcbca $) = 5$ . Palindromic substrings are the same, and one extra substring cbc.
- $p($ abcbcacbab $) = 8$ . Palindromic substrings are the same, and three extra substrings cac, bab and bcacb.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted