No.2893 Minahoshi (Hard)
タグ : / 解いたユーザー数 10
作問者 : 👑
seekworser
/ テスター :
👑 
amentorimaru
kemuniku
Story
Minahoshi: "I think I've figured out the LCP array!"
Minahoshi: "I solved the maximum case, so surely the minimum case is easy to solve too, right?"
Problem Statement
You are given a positive integer $N$. Construct a string of length $N$ consisting of a or b
such that the sum of the elements of its LCP array is minimized.
What is an LCP array?
For a string $S$ of length $N$, the array obtained by sorting the $N$ suffixes of $S$ in lexicographical order is called the suffix array of $S$.The array obtained by computing, for each $i = 1, 2, \dots, N-1$, the length of the longest common prefix of the $i$-th element and the $i+1$-th element of the suffix array of $S$ is called the LCP array (Longest Common Prefix Array) of $S$.
This problem has multiple test cases. Solve each of the $T$ test cases.
Input
$T$ $case_1$ $\vdots$ $case_T$
For $i = 1, 2, \dots, T$, $case_i$ is given in the following format.
$N$
Constraints
- $1 \le T \le 600$
- $2 \le N \le 2 \times 10^5$
- The sum of $N$ over all test cases is at most $2 \times 10^5$.
- All input values are integers.
Output
Print $T$ lines. On the $i$-th line, for the $i$-th test case, print a string of length $N$ consisting of
a or b
such that the sum of the elements of its LCP array is minimized.
If multiple strings satisfy the condition for the given $N$, any of them will be accepted.
Sample
Sample 1
Input
3 2 3 4
Output
ab abb aabb
The LCP array of ab is $[ 0 ]$, and its sum is $0$.
The LCP array of abb is $[ 0,\ 1 ]$, and its sum is $1$.
The LCP array of aabb is $[ 1,\ 0,\ 1 ]$, and its sum is $2$.
Each of these is the minimum possible sum of the LCP array among strings of length $N$ consisting of a or b.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。