本文共 3037 字,大约阅读时间需要 10 分钟。
Vasya has a string ss of length nn. He decides to make the following modification to the string:
Vasya wants to choose a kk such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of kk. Among all such kk, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.
A string aa is lexicographically smaller than a string bb if and only if one of the following holds:
Input
Each test contains multiple test cases.
The first line contains the number of test cases tt (1≤t≤50001≤t≤5000). The description of the test cases follows.
The first line of each test case contains a single integer nn (1≤n≤50001≤n≤5000) — the length of the string ss.
The second line of each test case contains the string ss of nn lowercase latin letters.
It is guaranteed that the sum of nn over all test cases does not exceed 50005000.
Output
For each testcase output two lines:
In the first line output the lexicographically smallest string s′s′ achievable after the above-mentioned modification.
In the second line output the appropriate value of kk (1≤k≤n1≤k≤n) that you chose for performing the modification. If there are multiple values of kk that give the lexicographically smallest string, output the smallest value of kk among them.
Example
input
Copy
64abab6qwerty5aaaaa6alaska9lfpbavjsm1p
output
Copy
abab1ertyqw3aaaaa1aksala6avjsmbpfl5p1
Note
In the first testcase of the first sample, the string modification results for the sample abab are as follows :
The lexicographically smallest string achievable through modification is abab for k=1k=1 and 33. Smallest value of kk needed to achieve is hence 11.
【题意】
每k个字串进行翻转,求最后字典序最小的字符串。
如果字典序有很多个最小,求k最小。
【思路】
首先定义一个结构体,定义一个字符串和k,,进行字典序最小排序,其次对k进行排序。
k从1开始最大为n-1,构造的字符串先从k到n开始拼接,后面就是从头开始,,如果k和n的奇偶性相同,就把前面的倒着遍历,否则正着遍历,(也是看到的结论,没找到规律)因为字符串从0开始,所以k=i+1。
#includeusing namespace std;struct node{ string s1; int k;}ans[5005];bool cmp(node a,node b){ if(a.s1==b.s1) return a.k >t; while(t--) { int n; string s; cin>>n>>s; ans[0].s1=s,ans[0].k=1; for(int i=1;i =0;j--) ss+=s[j]; } else { for(int j=0;j
转载地址:http://ctyzi.baihongyu.com/