String Modification （CodeCraft-20 (Div. 2)）

题意描述

Vasya has a string s of length n. He decides to make the following modification to the string: Pick an integer k, (1≤k≤n). For i from 1 to n−k+1, reverse the substring s[i:i+k−1] of s. For example, if string s is qwer and k=2, below is the series of transformations the string goes through: qwer (original string) wqer (after reversing the first substring of length 2) weqr (after reversing the second substring of length 2) werq (after reversing the last substring of length 2) Hence, the resulting string after modifying s with k=2 is werq. Vasya wants to choose a k such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of k. Among all such k, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help. A string a is lexicographically smaller than a string b if and only if one of the following holds: a is a prefix of b, but a≠b; in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤5000). The description of the test cases follows. The first line of each test case contains a single integer n (1≤n≤5000) — the length of the string s. The second line of each test case contains the string s of n lowercase latin letters. It is guaranteed that the sum of n over all test cases does not exceed 5000.

Output For each testcase output two lines:

In the first line output the lexicographically smallest string s′ achievable after the above-mentioned modification.

In the second line output the appropriate value of k (1≤k≤n) that you chose for performing the modification. If there are multiple values of k that give the lexicographically smallest string, output the smallest value of k among them.

Example

input 6 4 abab 6 qwerty 5 aaaaa 6 alaska 9 lfpbavjsm 1 p

output abab 1 ertyqw 3 aaaaa 1 aksala 6 avjsmbpfl 5 p 1

思路

还是一题选手，这道题一开始想的是暴力的做法，但数据范围太大，所以只能找规律，但找了很长时间，发现规律找错了，没有从奇偶方面下手。这道题的规律是，如果从k开始的字符串长度是奇数，就将k前的字符串翻转。（还是做题太少）

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<string>
#include<vector>
#include<map>
#define IOS ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
typedef pair<string,int> PII;
typedef long long ll;
const int N=5050;
const int INF=0x3f3f3f3f;
int main(){
	IOS;
	int T;
	cin>>T;
	while(T--){
		int n;
		string str;
		cin>>n>>str;
		PII t=make_pair(str,1);
		for(int i=2;i<=n;i++){
			string s=str.substr(i-1),u=str.substr(0,i-1);
			if((n-(i+1))%2){
				reverse(u.begin(),u.end());
			}
			t=min(make_pair(s+u,i),t);
		} 
		cout<<t.first<<endl<<t.second<<endl;
	}
	return 0;
}