CodeCraft-20 (Div. 2) B. String Modification (字符串,规律)

题意:有一个长度为\(n\)的字符串,你可以选取一个值\(k(1\le k \le n)\),然后遍历字符串,每次将区间长度为\(k\)的字符串反转,求反转后字典序最小的字符串,并输出\(k\)的值.
题解:这题我是打表找规律写的,观察样例不难发现,当区间长度为\(k\)时,答案字符串就是将前\(k-1\)个字符移到了尾部,并且,假如\(k\)的奇偶性和\(n\)相同,那么这前\(k-1\)个字符就要反转,所以我们只要遍历\(k\),然后模拟维护一个字典序最小的字符串即可.

代码:

 int t;

 int n;

 string s;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

  	cin>>t;

  	 while(t--){

  	 	cin>>n>>s;

  	 	string ans=s;

  	 	int cnt=1;

  	 	for(int i=1;i<=n;++i){

  	 		string tmp1=s.substr(i-1,n);

  	 		string tmp2=s.substr(0,i-1);

  	 		if(i%2==n%2)

  	 		reverse(tmp2.begin(),tmp2.end());

  	 		tmp1+=tmp2;

  	 		if(tmp1<ans){

  	 			ans=tmp1;

  	 			cnt=i;

  	 		}

  	 	}

  	 	cout<<ans<<endl;

  	 	cout<<cnt<<endl;

  	 }

    return 0;

}

巴特西

CodeCraft-20 (Div. 2) B. String Modification (字符串,规律)

最新文章

热门文章