题面
恭喜你,你被硕士援助中心录取了!但是,你在课堂上感到非常无聊,厌倦了无所事事,于是你给自己想了一个游戏。
给你一个字符串 s s s 和一个偶整数 n n n 。你可以对它进行两种运算:
- 将反向字符串 s s s 添加到字符串 s s s 的末尾(例如,如果 $s = $ cpm,那么在执行操作 $s = $ cpmmpc 之后)。
- 将当前字符串 s s s 倒转(例如,如果 $s = $ cpm,则在执行操作 $s = $ mpc后)。
需要确定在进行精确的 n n n 操作后,可以得到的词序最小的 † ^{\dagger} † 字符串。请注意,您可以按照任意顺序进行不同类型的运算,但必须总共进行 n n n 次运算。
† ^{\dagger} † 当且仅当以下条件之一成立时,字符串 a a a 在词法上比字符串 b b b 小:
- a a a 是 b b b 的前缀,但是 a ≠ b a \ne b a=b ;
- 在 a a a 和 b b b 不同的第一个位置上,字符串 a a a 的字母在字母表中出现的时间早于 b b b 中的相应字母。
输入
每个测试由多个测试用例组成。第一行包含一个整数 t t t ( 1 ≤ t ≤ 500 1 \leq t \leq 500 1≤t≤500 ) - 测试用例的个数。测试用例说明如下。
每个测试用例的第一行包含一个偶整数 n n n ( 2 ≤ n ≤ 1 0 9 2 \leq n \leq 10^9 2≤n≤109 ) - 对字符串 s s s 进行操作的次数。
每个测试用例的第二行包含一个字符串
s
s
s (
1
≤
∣
s
∣
≤
100
1 \leq |s| \leq 100
1≤∣s∣≤100 )(
1
≤
∣
s
∣
≤
100
1 \leq |s| \leq 100
1≤∣s∣≤100 ) - 对字符串
s
s
s 进行运算的字符串,由小写英文字母组成。
输出
对于每个测试用例,输出一行–在应用 n n n 次操作后可以得到的词典最小字符串。文章来源:https://www.toymoban.com/news/detail-839012.html
思路
求输出字典序最小,这就和字符串头尾第一个不同的字符有关系文章来源地址https://www.toymoban.com/news/detail-839012.html
#include<bits/stdc++.h>
using namespace std;
void run(){
int n;
cin>>n;
string s;
cin>>s;
int len = s.length();
int l = 0,r = len-1;
while(s[l]==s[r] && l<r)l++,r--;//找到第一对不同的下标
if(l>=r){
cout<<s<<endl;//找完了还没找到,意味着是个回文串,转不转都一样
}else{
if(s[l] < s[r]){
if(n%2==0){
cout<<s<<endl;
}else{
cout<<s;
reverse(s.begin(),s.end());
cout<<s<<endl;
}
}else if(s[l] > s[r]){
if(n%2==0){
string ss= s;
reverse(s.begin(),s.end());
cout<<s<<ss<<endl;
}else{
reverse(s.begin(),s.end());
cout<<s<<endl;
}
}
}
}
int main(){
int t;cin>>t;
while(t--)
run();
return 0;
}
到了这里,关于Codeforces Round 932 (Div. 2) A Entertainment in MAC的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!