luogu#P9719. [EC Final 2022] Minimum Suffix
[EC Final 2022] Minimum Suffix
题目描述
For a string of length , we define if is the minimum suffix of , for all . (A suffix is the minimum suffix of a string if it is lexicographically smaller than any other suffix of that string.)
You are to recover from . If there are multiple answers, find the lexicographically smallest one.
输入格式
The first line contains a single integer () representing the number of test cases.
For each test case, the first line contains a single integer () representing the length of . The next line contains integers ( for all ).
It is guaranteed that the sum of over all test cases does not exceed .
输出格式
For each test case, output one line. If there is no solution, output . Otherwise, output the lexicographically smallest . Characters of are represented by positive integers. Smaller integers represent smaller characters in the lexicographical order.
题目大意
【题目描述】
对于长度为 的字符串 ,如果 是 的最小后缀,则我们定义 ,其中 。(后缀是字符串的最小后缀,如果它在字典序上小于该字符串的任何其他后缀。)
你需要从 中恢复出 。如果存在多个答案,则找出字典序最小的那个。
【输入格式】
第一行包含一个整数 (),表示测试用例的数量。
对于每个测试用例,第一行包含一个整数 (),表示 的长度。接下来的一行包含 个整数 (,)。
保证所有测试用例中 的总和不超过 。
【输出格式】
对于每个测试用例,输出一行。如果没有解决方案,则输出 。否则,输出字典序最小的 。 中的字符由正整数表示。较小的整数表示字典序较小的字符。
【提示说明】
本题输入输出规模较大,建议使用快速的输入输出方式。
翻译来自于:ChatGPT。
6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3
1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1
提示
As the input/output can be huge, it is recommended to use fast input/output methods.